login
Number of partitions of n into cubes.
(Formerly M0209)
56

%I M0209 #99 Aug 01 2024 03:08:56

%S 1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,5,5,5,5,5,6,6,

%T 6,7,7,7,7,7,8,8,8,9,9,9,9,9,10,10,10,11,11,11,12,12,13,13,13,14,14,

%U 14,15,15,17,17,17,18,18,18,19,19,21,21,21,22,22,22,23,23,25,26,26,27,27,27,28

%N Number of partitions of n into cubes.

%C The g.f. 1/(z+1)/(z**2+1)/(z**4+1)/(z-1)**2 conjectured by _Simon Plouffe_ in his 1992 dissertation is wrong.

%D H. P. Robinson, Letter to N. J. A. Sloane, Jan 04 1974.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D F. Smarandache, Sequences of Numbers Involved in Unsolved Problems, Hexis, Phoenix, 2006.

%H T. D. Noe and Vaclav Kotesovec, <a href="/A003108/b003108.txt">Table of n, a(n) for n = 0..100000</a> (terms 0..1000 from T. D. Noe)

%H G. H. Hardy and S. Ramanujan, <a href="http://ramanujan.sirinudi.org/Volumes/published/ram33.html">Asymptotic formulae in combinatory analysis</a>, Proceedings of the London Mathematical Society, 2, XVI, 1917, p. 373.

%H F. Iacobescu, <a href="http://www.gallup.unm.edu/~smarandache/SN/ScArt5/SPartitionType.pdf">Smarandache Partition Type and Other Sequences</a>, Bull. Pure Appl. Sci. 16E, 237-240, 1997.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Herman P. Robinson, <a href="/A003105/a003105.pdf">Letter to N. J. A. Sloane, Jan 1974</a>.

%H F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/Sequences-book.pdf">Sequences of Numbers Involved in Unsolved Problems</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CubicNumber.html">Cubic Number</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Partition.html">Partition</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SmarandacheSequences.html">Smarandache Sequences</a>

%F G.f.: 1/Product_{j>=1} (1-x^(j^3)). - _Emeric Deutsch_, Mar 30 2006

%F G.f.: Sum_{n>=0} x^(n^3) / Product_{k=1..n} (1 - x^(k^3)). - _Paul D. Hanna_, Mar 09 2012

%F a(n) ~ exp(4 * (Gamma(1/3)*Zeta(4/3))^(3/4) * n^(1/4) / 3^(3/2)) * (Gamma(1/3)*Zeta(4/3))^(3/4) / (24*Pi^2*n^(5/4)) [Hardy & Ramanujan, 1917]. - _Vaclav Kotesovec_, Dec 29 2016

%e a(16) = 3 because we have [8,8], [8,1,1,1,1,1,1,1,1] and [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1].

%e G.f.: A(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + 2*x^8 +...

%e such that the g.f. A(x) satisfies the identity [Paul D. Hanna]:

%e A(x) = 1/((1-x)*(1-x^8)*(1-x^27)*(1-x^64)*(1-x^125)*...)

%e A(x) = 1 + x/(1-x) + x^8/((1-x)*(1-x^8)) + x^27/((1-x)*(1-x^8)*(1-x^27)) + x^64/((1-x)*(1-x^8)*(1-x^27)*(1-x^64)) +...

%p g:=1/product(1-x^(j^3),j=1..30): gser:=series(g,x=0,70): seq(coeff(gser,x,n),n=0..65); # _Emeric Deutsch_, Mar 30 2006

%t nmax = 100; CoefficientList[Series[Product[1/(1 - x^(k^3)), {k, 1, nmax^(1/3)}], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Aug 19 2015 *)

%t nmax = 60; cmax = nmax^(1/3);

%t s = Table[n^3, {n, cmax}];

%t Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* _Robert Price_, Jul 31 2020 *)

%o (PARI) {a(n)=polcoeff(1/prod(k=1, ceil(n^(1/3)), 1-x^(k^3)+x*O(x^n)), n)} /* _Paul D. Hanna_, Mar 09 2012 */

%o (PARI) {a(n)=polcoeff(1+sum(m=1, ceil(n^(1/3)), x^(m^3)/prod(k=1, m, 1-x^(k^3)+x*O(x^n))), n)} /* _Paul D. Hanna_, Mar 09 2012 */

%o (Haskell)

%o a003108 = p $ tail a000578_list where

%o p _ 0 = 1

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Oct 31 2012

%o (Magma) [#RestrictedPartitions(n,{d^3:d in [1..n]}): n in [0..150]]; // _Marius A. Burtea_, Jan 02 2019

%o (Python)

%o from functools import lru_cache

%o from sympy import integer_nthroot, divisors

%o @lru_cache(maxsize=None)

%o def A003108(n):

%o @lru_cache(maxsize=None)

%o def a(n): return integer_nthroot(n,3)[1]

%o @lru_cache(maxsize=None)

%o def c(n): return sum(d for d in divisors(n,generator=True) if a(d))

%o return (c(n)+sum(c(k)*A003108(n-k) for k in range(1,n)))//n if n else 1 # _Chai Wah Wu_, Jul 15 2024

%Y Cf. A000578, A068980, A131799, A218495, A226748, A279329, A280263.

%Y Cf. A001156, A046042.

%Y Cf. A037444, A259792, A259793.

%K nonn

%O 0,9

%A _N. J. A. Sloane_, _Herman P. Robinson_