Name of equation??
Peter Gunn
does anyone know the equation f(x) which
calculates the number of possible ways of
calculating x by summing positive integers <=x ???
For instance...
f(1) = 1 [1]
f(2) = 2 [2,1+1]
f(3) = 3 [3,2+1,1+1+1]
f(4) = 5 [4,3+1,2+2,2+1+1,1+1+1+1]
f(5) = 7 [5,4+1,3+2,3+1+1,2+1+1+1,1+1+1+1+1,2+2+1]
f(6) = 11 [6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+1,
2+1+1+1+1,1+1+1+1+1+1,2+2+2,2+2+1+1]
... and so on.
thanks,
PG.
spam...@nil.nil
> does anyone know the equation f(x) which
> calculates the number of possible ways of
> calculating x by summing positive integers <=x ???
> For instance...
> f(1) = 1 [1]
> f(2) = 2 [2,1+1]
The number of partitions of x ("partitions").
The coefficient of x^n in 1/f(x) where:
f(x)=(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)...
=PRODuct[(1-x^k): for k=1,2,3,4,...]
is the number of partitions of n.
Peter Gunn
Yes, but I was looking for a simple mechanism :-)
Ive just uncovered the Hardy-Ramanujan approximation...
f(n)=floor(0.5+exp(PI*sqrt(2n/3))/(4n*sqrt(3)))
and apparently the exact sequence was refined by
Rademacher to give...
1 d / e^(PI sqrt(2n/3 - 1/36)) \
f(n)= ----------- --( ------------------------- ) + O(e^(k sqrt(n))
2PI sqrt(2) dn \ sqrt(n - 1/24) /
which is nice, but unfortunately my mathemetical ability
is somewhat nonexistant, so could someone please help me turn
this into a 'C style' equation like the Hardy-Ramanujan
approximation??
Also, does anyone know a quick method of determining
n given f(n) without iteration or recursion, a way to
calculate f(xy) given f(x) and f(y), or a way to
calculate f(xy) given x and f(y)??
Thanks,
PG.
Josephine Michelle Draus and Lorraine Lee
Peter Gunn wrote in message <371B4E5...@NOSPAMhotmail.com>...
>spam...@nil.nil wrote:
>
>> Peter Gunn <pete...@NOSPAMhotmail.com> wrote:
>>
>> > does anyone know the equation f(x) which
>> > calculates the number of possible ways of
>> > calculating x by summing positive integers <=x ???
/0 (k>n)
p(k,n)={ 1 (k=n)
\p(k+1,n)+p(k,n-k) (k<n)
Number of partitions of n is p(1,n).
p(k,n) is number of partitions of n,
allowing only addends >=k.
Kurt Foster
: Yes, but I was looking for a simple mechanism :-)
: Ive just uncovered the Hardy-Ramanujan approximation...
Just out of curiosity, in which of the sources to which I referred you
did you "uncover" Hardy-Ramanujan, or Rademacher's formulation?
dr_a...@my-dejanews.com
Isn't the Hardy Ramanujan identities in Hardy's book :
Hardy and Wright : An introduction to number theory.
(i guess not, they found the results after that).
Barring that, the result is quoted, i am sure, in
Tom Apostol : Analytic Number Theory.
Cheers.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Peter Gunn
> In <371B4E5...@NOSPAMhotmail.com>, Peter Gunn said:
> : Yes, but I was looking for a simple mechanism :-)
> : Ive just uncovered the Hardy-Ramanujan approximation...
>
> Just out of curiosity, in which of the sources to which I referred you
> did you "uncover" Hardy-Ramanujan, or Rademacher's formulation?
Dont want to sound like a smart arse (coz Im not :-) but I
found this before I read your email...
http://www.seanet.com/~ksbrown/kmath266.htm
Its worth noting that I listed the Ramanujan and
Hardy-Ramanujan approximations and not the
Rademacher one, I think :-)
Thanks for the help anyway, I'll try and find an online
version of the texts you mentioned.
If you find the Rademacher info please email :-)
ttfn
PG.
Steve Monson
>
> Hi,
>
> does anyone know the equation f(x) which
> calculates the number of possible ways of
> calculating x by summing positive integers <=x ???
>
>
> f(1) = 1 [1]
> f(2) = 2 [2,1+1]
> f(4) = 5 [4,3+1,2+2,2+1+1,1+1+1+1]
> f(5) = 7 [5,4+1,3+2,3+1+1,2+1+1+1,1+1+1+1+1,2+2+1]
> f(6) = 11 [6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+1,
> 2+1+1+1+1,1+1+1+1+1+1,2+2+2,2+2+1+1]
Take a look at
http://www.seanet.com/~ksbrown/kmath266.htm
for an asymptotic formula for the number of partitions for N. It also
gives a reference for further study. I'm sure Sloane's Handbook of
Integer Sequences will also give you some further values.
http://www.seanet.com/~ksbrown/kmath383.htm
also discusses this a bit.
Steve Monson
Kurt Foster
by Abramowitz and Stegun. See Tom Apostol's books, "Introduction to
Analytic Number Theory" and the sequel (Modular Functions and Number
Theory?) for the derivations. I think it's also in a book by Rademacher
himself. And no doubt innumerable other sources.
FWIW, "Handbook" also lists the values of p(n) [unrestricted partitions]
and q(n) [partitions into distinct parts] for n = 1 to n = 500. It gives
p(500) = 2300165032574323995027
q(500) = 732986521245024