|
%I M0639 #77 Jan 28 2024 12:32:01
%S 1,2,3,5,7,9,12,15,18,23,28,33,40,47,54,63,72,81,93,105,117,132,147,
%T 162,180,198,216,239,262,285,313,341,369,402,435,468,508,548,588,635,
%U 682,729,783,837,891,954,1017,1080,1152,1224,1296,1377,1458,1539,1632
%N Number of partitions of 3n into powers of 3.
%C Infinite convolution product of [1,2,3,3,3,3,3,3,3,3] aerated A000244 - 1 times, i.e., [1,2,3,3,3,3,3,3,3,3] * [1,0,0,2,0,0,3,0,0,3] * [1,0,0,0,0,0,0,0,0,2] * ... [_Mats Granvik_, _Gary W. Adamson_, Aug 07 2009]
%D R. K. Guy, personal communication.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A005704/b005704.txt">Table of n, a(n) for n = 0..10000</a>
%H G. E. Andrews, <a href="http://dx.doi.org/10.1016/0022-314X(71)90051-5">Congruence properties of the m-ary partition function</a>, J. Number Theory 3 (1971), 104-110.
%H G. E. Andrews and J. A. Sellers, <a href="https://georgeandrews1.github.io/pdf/300.pdf">Characterizing the number of p-ary partitions modulo a prime p</a>, p. 2.
%H C. Banderier, H.-K. Hwang, V. Ravelomanana, and V. Zacharovas, <a href="http://140.109.74.92/hk/wp-content/files/2012/07/mis-n-to-the-logn.pdf">Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics</a>, 2012. - From _N. J. A. Sloane_, Dec 23 2012
%H R. K. Guy, <a href="/A000123/a000123_1.pdf">Letters to N. J. A. Sloane and J. W. Moon, 1988</a>
%H M. D. Hirschhorn and J. A. Sellers, <a href="https://ajc.maths.uq.edu.au/pdf/30/ajc_v30_p193.pdf">A different view of m-ary partitions</a>, Australasian J. Combin., 30 (2004), 193-196.
%H M. D. Hirschhorn and J. A. Sellers, <a href="http://www.math.psu.edu/sellersj/mike-m-ary.pdf">A different view of m-ary partitions</a>
%H D. Krenn, D. Ralaivaosaona, and S. Wagner, <a href="http://www.danielkrenn.at/downloads/multi-base-asy/multi-bases-asy-with-appendix-20140601.pdf">The Number of Multi-Base Representations of an Integer</a>, 2014.
%H D. Krenn, D. Ralaivaosaona, and S. Wagner, <a href="http://arxiv.org/abs/1503.08594">Multi-Base Representations of Integers: Asymptotic Enumeration and Central Limit Theorems</a>, arXiv:1503.08594 [math.NT], 2015. Also in <a href="https://doi.org/10.2298/AADM150917018K">Applicable Analysis and Discrete Mathematics</a> (2015) Vol. 9, Issue 2, 285-312.
%H M. Latapy, <a href="https://doi.org/10.46298/dmtcs.2279">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.
%H M. Latapy, <a href="/A005706/a005706.pdf">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]
%H O. J. Rodseth, <a href="http://dx.doi.org/10.1017/S0305004100046259">Some arithmetical properties of m-ary partitions</a>, Proc. Camb. Phil. Soc. 68 (1970), 447-453.
%H O. J. Rodseth and J. A. Sellers, <a href="http://dx.doi.org/10.1006/jnth.2000.2594">On m-ary partition function congruences: A fresh look at a past problem</a>, J. Number Theory 87 (2001), 270-281.
%H O. J. Rodseth and J. A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Sellers/sellers75.html">On a Restricted m-Non-Squashing Partition Function</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
%F a(n) = a(n-1)+a(floor(n/3)).
%F Coefficient of x^(3*n) in prod(k>=0, 1/(1-x^(3^k))). Also, coefficient of x^n in prod(k>=0, 1/(1-x^(3^k)))/(1-x). - _Benoit Cloitre_, Nov 28 2002
%F a(n) mod 3 = binomial(2n, n) mod 3. - _Benoit Cloitre_, Jan 04 2004
%F Let T(x) be the g.f., then T(x)=(1-x^3)/(1-x)^2*T(x^3). [_Joerg Arndt_, May 12 2010]
%t Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1, #1}]], #2]]] &, {1}, Range[2, 55]] (* _Birkas Gyorgy_, Apr 18 2011 *)
%t a[n_] := a[n] = If[n <= 2, n + 1, a[n - 1] + a[Floor[n/3]]]; Array[a, 101, 0] (* _T. D. Noe_, Apr 18 2011 *)
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A005704(n): return A005704(n-1)+A005704(n//3) if n else 1 # _Chai Wah Wu_, Sep 21 2022
%Y Cf. A000041, A000123, A005705, A005706, A018819.
%Y Cf. A006996.
%K nonn
%O 0,2
%A _N. J. A. Sloane_
%E Formula and more terms from _Henry Bottomley_, Apr 30 2001
|
