A008650 -id:A008650 - cp's OEIS frontend

A062051 Number of partitions of n into powers of 3.

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, 23, 28, 28, 28, 33, 33, 33, 40, 40, 40, 47, 47, 47, 54, 54, 54, 63, 63, 63, 72, 72, 72, 81, 81, 81, 93, 93, 93, 105, 105, 105, 117, 117, 117, 132, 132, 132, 147, 147, 147, 162

Offset: 0

Amarnath Murthy, Jun 06 2001

nonn

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
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
Starts to differ from A008650 at a(81). - R. J. Mathar, Jul 31 2010
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
From Gary W. Adamson, Sep 03 2016: (Start)
Let M =
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  ..., 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)

			a(4) = 2 and the partitions are 3+1, 1+1+1+1;
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.

Seiichi Manyama, Table of n, a(n) for n = 0..1000
Vassil Dimitrov, Laurent Imbert, and Andrew Zakaluzny, Multiplication by a Constant is Sublinear, 18th IEEE Symposium on Computer Arithmetic (2007). See Theorem 1.
Md Towhidul Islam and Md Shahidul Islam, 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, arXiv:1502.07730 [math.CO], 2015.
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]

A005704 with terms repeated 3 times.

Cf. A000123, A018819, A000009, A003586, A105420, A039966, A023893, A105420, A106244, A131995, A179051, A254296.

nn=70;a=Product[1/(1-x^(3^i)),{i,0,4}];CoefficientList[Series[a,{x,0,nn}],x] (* Geoffrey Critzer, Oct 30 2012 *)

{ 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

from functools import lru_cache
@lru_cache(maxsize=None)
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

a(n) = A005704([n/3]).
G.f.: Product_{k>=0} 1/(1-x^(3^k)). - R. J. Mathar, Jul 31 2010
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
G.f.: 1 + Sum_{i>=0} x^(3^i) / Product_{j=0..i} (1 - x^(3^j)). - Ilya Gutkovskiy, May 07 2017

More terms from Larry Reeves (larryr(AT)acm.org), Jun 11 2001

A102430 Triangle read by rows where T(n,k) is the number of integer partitions of n > 1 into powers of k > 1.

Original entry on oeis.org

2, 2, 2, 4, 2, 2, 4, 2, 2, 2, 6, 3, 2, 2, 2, 6, 3, 2, 2, 2, 2, 10, 3, 3, 2, 2, 2, 2, 10, 5, 3, 2, 2, 2, 2, 2, 14, 5, 3, 3, 2, 2, 2, 2, 2, 14, 5, 3, 3, 2, 2, 2, 2, 2, 2, 20, 7, 4, 3, 3, 2, 2, 2, 2, 2, 2, 20, 7, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 26, 7, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2

Offset: 2

Marc LeBrun, Jan 08 2005

All entries above main diagonal are = 1.

			The T(9,3)=5 partitions of 9 into powers of 3: 111111111, 1111113, 11133, 333, 9.
From _Gus Wiseman_, Jun 07 2019: (Start)
Triangle begins:
   2
   2  2
   4  2  2
   4  2  2  2
   6  3  2  2  2
   6  3  2  2  2  2
  10  3  3  2  2  2  2
  10  5  3  2  2  2  2  2
  14  5  3  3  2  2  2  2  2
  14  5  3  3  2  2  2  2  2  2
  20  7  4  3  3  2  2  2  2  2  2
  20  7  4  3  3  2  2  2  2  2  2  2
  26  7  4  3  3  3  2  2  2  2  2  2  2
  26  9  4  4  3  3  2  2  2  2  2  2  2  2
  36  9  6  4  3  3  3  2  2  2  2  2  2  2  2
  36  9  6  4  3  3  3  2  2  2  2  2  2  2  2  2
  46 12  6  4  4  3  3  3  2  2  2  2  2  2  2  2  2
Row n = 8 counts the following partitions:
  8          3311       44         5111       611        71         8
  44         311111     41111      11111111   11111111   11111111   11111111
  422        11111111   11111111
  2222
  4211
  22211
  41111
  221111
  2111111
  11111111
(End)

Alois P. Heinz, Rows n = 2..500, flattened

Cf. A102431, A102432, A102433, A102434, A001700, A018819, A062051, A008645, A008650, A008652, A008648.
Same as A308558 except for the k = 1 column.
Row sums are A102431.
First column (k = 2) is A018819.
Second column (k = 3) is A062051.
Cf. A000961, A001597, A007916, A023894, A052410, A112344.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<0, 0,
      b(n, i-1, k)+(p-> `if`(p>n, 0, b(n-p, i, k)))(k^i)))
    end:
T:= (n, k)-> b(n, ilog[k](n), k):
seq(seq(T(n, k), k=2..n), n=2..20);  # Alois P. Heinz, Oct 12 2019

Table[Length[Select[IntegerPartitions[n],And@@(IntegerQ[Log[k,#]]&/@#)&]],{n,2,10},{k,2,n}] (* Gus Wiseman, Jun 07 2019 *)

T(1, k) = 1, T(n, 1) = choose(2n-1, n), T(n>1, k>1) = T(n-1, k) + (T(n/k, k) if k divides n, else 0)

Corrected and rewritten by Gus Wiseman, Jun 07 2019

cp's OEIS Frontend

A062051 Number of partitions of n into powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions