Problems & Puzzles: Puzzles Puzzle 160. s(n) and p(n) Two weekends ago I was taking an overview to a book^{1} of my friend Enoch Haga when I saw, in the page 56, the following recursive formula to calculate s(n) the symbol for the sum of divisors of a number n : s(n) = s(n1)+s(n2)s(n5)s(n7)+s(n12)+s(n15)s(n22)s(n26)+s(n35)+s(n40) ... I remember that I almost jumped out of my seat saying "Oh heck!... Enoch made a mistake... This formula is not for the sum of the divisors of n, s(n), but for the partitions of n, p(n)". As maybe you know p(n) is the the symbol commonly used for the "partitions of n", that is to say, the "distinct number of ways that a number n can be expressed as a sum of other numbers, disregarding the order of them". I confirmed my guess opening my book "Mathematical Mysteries" by Calvin C. Clawson. There at the page 233 was the right formula: p(n) = p(n1)+p(n2)p(n5)p(n7)+p(n12)+p(n15)p(n22)p(n26)+p(n35)+p(n40) ... But... but the examples given by Enoch to calculate s(n) at the page 57 where absolutely correct, far beyond any doubt... so, the first formula is also a valid equation to calculate what is promised, s(n) ... I must say that I wrote to Enoch expressing not only my surprise for this strange (to me) fact but also with the little and secret hope that on return he accepted to have made some kind of typo. On the contrary he revealed to me that the origin of this issue in his book was the G. Polya's book "Mathematics and Plausible Reasoning", Vol 1. Polya on his turn  "was discussing Euler's French work, Opera Omnia, ser 1, vol 2, p.241253", commented Enoch. So, there is no doubt, s(n) and p(n) can be calculated by exactly the same recurrence formula, under the following conditions. When using any of these formulas:
*** Before making the final questions let's offer some examples.
*** Questions 1. Can you give a simple explanation of this strange fact: s(n) and p(n) can be calculated by exactly the same recurrence formula? 2. Is this indicative that we should have a function that relates directly s(n) to p(n)? Final comment: As probably you have already devised The Euler's recurrence formula applied successively to the natural numbers 2, 3, 4, 5, ... provides a recurrence method to produce the set of the prime numbers, being these prime numbers n such that s(n) = n+1. Despite to the fact that this is a method that consumes a lot of memory (in order to keep all the s(n) values produced and needed in further calculations), we can no doubt that we have here a strange way of producing the primes through the generalized pentagonal numbers and the Euler's recurrence formula, that is to say a method to produce the sequence of the prime numbers executing only elemental and regularrecursive operations... 3. Being this method to produce a list of prime, of scarce if any practical value, do you devise for it any theoretical/logical value ?
__________________________ Appendix A:
At first sight nothing exhibits a relationship between these two functions. On the contrary, the most striking fact against any kind of relationship between these two quantities is that p(n) increases monotonously while s(n) doesn't. Another striking fact is that s(n) keeps a close and direct relationship with the prime numbers ( s(p) = p+1 ) while p(n) doesn't. Solution: Daniel Gronau makes a challenging observation and adds a new question. The observation is that the same recursive function produce one or another concept (sum of divisors or partitions) entirely depending on the initial respective terms: {s(0)=n & s(1)=1} and {p(0)=1 & p(1)=1}. The question is: what would happen varying these initial conditions? Could it be produced the sequence of another numbertheory basic concept? *** Chris Nash makes an attempt to the question 1:
*** Another relationship between is s(n) and p(n) now reported by Marc Fonoll (1/12/2001):
***





