cp's OEIS Frontend

A062051 Number of partitions of n into powers of 3.

%I A062051 #93 Jan 28 2024 12:34:53
%S A062051 1,1,1,2,2,2,3,3,3,5,5,5,7,7,7,9,9,9,12,12,12,15,15,15,18,18,18,23,23,
%T A062051 23,28,28,28,33,33,33,40,40,40,47,47,47,54,54,54,63,63,63,72,72,72,81,
%U A062051 81,81,93,93,93,105,105,105,117,117,117,132,132,132,147,147,147,162
%N A062051 Number of partitions of n into powers of 3.
%C A062051 Number of different partial sums of 1+[1,*3]+[1,*3]+..., where [1,*3] means we can either add 1 or multiply by 3. E.g., a(6)=3 because we have 6=1+1+1+1+1+1=(1+1)*3=1*3+1+1+1. - _Jon Perry_, Jan 01 2004
%C A062051 Also number of partitions of n into distinct 3-smooth parts. E.g., a(10) = #{9+1, 8+2, 6+4, 6+3+1, 4+3+2+1} = #{9+1, 3+3+3+1, 3+3+1+1+1+1, 3+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1} = 5. - _Reinhard Zumkeller_, Apr 07 2005
%C A062051 Starts to differ from A008650 at a(81). - _R. J. Mathar_, Jul 31 2010
%C A062051 If m=ceiling(log_3(2k)) and n=(3^m+1)/2-k for k in the range (3^(m-1)+1)/2+(3^(m-2))<=k<=(3^m-1)/2, this sequence gives the number of "feasible" partitions described in the sequence A254296. For instance, the terms starting at 121st term of A254296 backwards to 68th term of A254296 provide the first 54 terms of this sequence. - _Md. Towhidul Islam_, Mar 01 2015
%C A062051 From _Gary W. Adamson_, Sep 03 2016: (Start)
%C A062051 Let M =
%C A062051   1, 0, 0, 0, 0, ...
%C A062051   1, 0, 0, 0, 0, ...
%C A062051   1, 0, 0, 0, 0, ...
%C A062051   1, 1, 0, 0, 0, ...
%C A062051   1, 1, 0, 0, 0, ...
%C A062051   1, 1, 0, 0, 0, ...
%C A062051   1, 1, 1, 0, 0, ...
%C A062051   1, 1, 1, 0, 0, ...
%C A062051   ..., where the leftmost column is all 1's, and all other columns are 1's shifted down thrice. Lim_{k=1..inf} M^k has a single nonzero column, which gives the sequence. (End)
%H A062051 Seiichi Manyama, <a href="/A062051/b062051.txt">Table of n, a(n) for n = 0..1000</a>
%H A062051 Vassil Dimitrov, Laurent Imbert, and Andrew Zakaluzny, <a href="http://www.lirmm.fr/~imbert/pdfs/constmult_arith18.pdf">Multiplication by a Constant is Sublinear</a>, 18th IEEE Symposium on Computer Arithmetic (2007). See Theorem 1.
%H A062051 Md Towhidul Islam and Md Shahidul Islam, <a href="http://arxiv.org/abs/1502.07730">Number of Partitions of an n-kilogram Stone into Minimum Number of Weights to Weigh All Integral Weights from 1 to n kg(s) on a Two-pan Balance</a>, arXiv:1502.07730 [math.CO], 2015.
%H A062051 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 A062051 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]
%F A062051 a(n) = A005704([n/3]).
%F A062051 G.f.: Product_{k>=0} 1/(1-x^(3^k)). - _R. J. Mathar_, Jul 31 2010
%F A062051 If m = ceiling(log_3(2k)), define n = (3^m + 1)/2 - k for k in the range (3^(m-1)+1)/2 + (3^(m-2)) <= k <= (3^m-1)/2. Then, a(n) = Sum_{s=ceiling((k-1)/3)..(3^(m-1)-1)/2} a(s). This gives the first 2(3^(m-1))/3 terms. - _Md. Towhidul Islam_, Mar 01 2015
%F A062051 G.f.: 1 + Sum_{i>=0} x^(3^i) / Product_{j=0..i} (1 - x^(3^j)). - _Ilya Gutkovskiy_, May 07 2017
%e A062051 a(4) = 2 and the partitions are 3+1, 1+1+1+1;
%e A062051 a(9) = 5 and the partitions are 9; 3+3+3; 3+3+1+1+1; 3+1+1+1+1+1+1; 1+1+1+1+1+1+1+1+1.
%t A062051 nn=70;a=Product[1/(1-x^(3^i)),{i,0,4}];CoefficientList[Series[a,{x,0,nn}],x] (* _Geoffrey Critzer_, Oct 30 2012 *)
%o A062051 (PARI) { n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*3)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } \\ _Jon Perry_
%o A062051 (Python)
%o A062051 from functools import lru_cache
%o A062051 @lru_cache(maxsize=None)
%o A062051 def A062051(n): return A062051(n-1)+(0 if n%3 else A062051(n//3)) if n>2 else 1 # _Chai Wah Wu_, Sep 21 2022
%Y A062051 A005704 with terms repeated 3 times.
%Y A062051 Cf. A000123, A018819, A000009, A003586, A105420, A039966, A023893, A105420, A106244, A131995, A179051, A254296.
%K A062051 nonn
%O A062051 0,4
%A A062051 _Amarnath Murthy_, Jun 06 2001
%E A062051 More terms from Larry Reeves (larryr(AT)acm.org), Jun 11 2001