A179051 -id:A179051 - cp's OEIS frontend

A018819 Binary partition function: number of partitions of n into powers of 2.

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294

Offset: 0

David W. Wilson, N. J. A. Sloane and J. H. Conway

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.
Euler transform of A036987 with offset 1.
a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003
Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.
Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004
Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007
Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008
Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009
Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).
Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009
Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016
From Gary W. Adamson, Sep 08 2016: (Start)
The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ... (End)
a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020
From Gus Wiseman, May 25 2024: (Start)
Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
  {1}  {2}   {12}   {3}     {13}     {23}      {123}      {4}
       {11}  {111}  {22}    {122}    {113}     {1113}     {33}
                    {112}   {1112}   {222}     {1222}     {223}
                    {1111}  {11111}  {1122}    {11122}    {1123}
                                     {11112}   {111112}   {2222}
                                     {111111}  {1111111}  {11113}
                                                          {11222}
                                                          {111122}
                                                          {1111112}
                                                          {11111111}
(End)

			G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.
From _Joerg Arndt_, Dec 17 2012: (Start)
The a(10) = 14 binary partitions of 10 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 ]
[ 6]  [ 2 2 2 2 2 ]
[ 7]  [ 4 1 1 1 1 1 1 ]
[ 8]  [ 4 2 1 1 1 1 ]
[ 9]  [ 4 2 2 1 1 ]
[10]  [ 4 2 2 2 ]
[11]  [ 4 4 1 1 ]
[12]  [ 4 4 2 ]
[13]  [ 8 1 1 ]
[14]  [ 8 2 ]
The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
[ 1]  [ 6 3 1 1 ]
[ 2]  [ 6 3 2 ]
[ 3]  [ 6 4 1 ]
[ 4]  [ 6 5 ]
[ 5]  [ 7 2 1 1 ]
[ 6]  [ 7 2 2 ]
[ 7]  [ 7 3 1 ]
[ 8]  [ 7 4 ]
[ 9]  [ 8 2 1 ]
[10]  [ 8 3 ]
[11]  [ 9 1 1 ]
[12]  [ 9 2 ]
[13]  [ 10 1 ]
[14]  [ 11 ]
The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _David V. Feldman_, Jan 29 2020: (Start)
The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 non-borrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(End)
For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

T. D. Noe, Table of n, a(n) for n = 0..1000
Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic
Giedrius Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110.
Giedrius Alkauskas, Congruence Properties of the Function that Counts Compositions into Powers of 2 , J. Int. Seq. 13 (2010), 10.5.3.
Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.
Scott M. Bailey and Donald M. Larson, The A(1)-module structure of the homology of Brown-Gitler spectra, arXiv:2107.01316 [math.AT], 2021.
Valentin P. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.
Philippe Biane, Laver tables and combinatorics, arXiv:1810.00548 [math.CO], 2018. Mentions this sequence.
Peter J. Cameron, Firdous Ee Jannat, Rajat Kanti Nath, and Reza Sharafdini, A survey on conjugacy class graphs of groups, arXiv:2403.09423 [math.GR], 2024.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 48, 581.
Maciej Gawron, Piotr Miska and Maciej Ulas, Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t, arXiv:1703.01955 [math.NT], 2017.
Michael D. Hirschhorn and James A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.
Jonathan Jordan and Richard Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045. - From _N. J. A. Sloane_, Feb 03 2013
Yasuyuki Kachi and Pavlos Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
Matjaž Konvalinka and Igor Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91; see also DOI link. - From _N. J. A. Sloane_, Dec 22 2012
Apisit Pakapongpun and Thomas Ward, Functorial Orbit counting, J. Int. Seq., 12 (2009) 09.2.4, example 25.
Øystein J. Rodseth and James A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
David Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
Convolution inverse of A106400.
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
Multiplicity of n in A048675, for distinct prime indices A087207.
Row lengths of A277905.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A372890 adds up binary ranks of integer partitions.
Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.

a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
   f (x:xs) = (sum $ take x a018819_list) : f xs
-- Reinhard Zumkeller, Jan 28 2012

import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
-- Johan Wiltink, Nov 08 2018

with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
# while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay

max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-François Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* Michael Somos, May 04 2022 *)
Table[Count[IntegerPartitions[n],?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale, Jun 20 2024 *)

{ 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]*2)); 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 */

{a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) / (1 - x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */

{a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* Michael Somos, Aug 25 2003 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # Chai Wah Wu, Jan 18 2022

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002
a(2*n) = a(2*n + 1) = A000123(n). - Michael Somos, Aug 25 2003
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2*w - 2*u*v^2 + v^3. - Michael Somos, Apr 10 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006
G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). - Paul D. Hanna, Jan 23 2012
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. - Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - Ilya Gutkovskiy, May 07 2017

A008592 Multiples of 10: a(n) = 10*n.

Original entry on oeis.org

0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500, 510, 520, 530

Offset: 0

N. J. A. Sloane

Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (01,1) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i11 and n>1. - Sergey Kitaev, Nov 12 2004
If Y is a 5-subset of an n-set X then, for n>=5, a(n-4) is the number of 3-subsets of X having at least two elements in common with Y. - Milan Janjic, Dec 08 2007
Complement of A067251; A168184(a(n)) = 0. - Reinhard Zumkeller, Nov 30 2009
Where record values occur for the number of partitions of n into powers of 10: A179052(n) = A179051(a(n)). - Reinhard Zumkeller, Jun 27 2010
Numbers ending in 0. - Wesley Ivan Hurt, Apr 10 2016

Ivan Panchenko, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 322.
Tanya Khovanova, Recursive Sequences.
Sergey Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A005843, A008587, A008590, A008591, A067251, A168184, A179051, A179052.

a008592 = (10 *)  -- Reinhard Zumkeller, Jun 13 2015

[10*n : n in [0..100]]; // Wesley Ivan Hurt, Apr 10 2016

A008592:=n->10*n: seq(A008592(n), n=0..100); # Wesley Ivan Hurt, Apr 10 2016

Range[0, 1000, 10] (* Vladimir Joseph Stephan Orlovsky, May 28 2011 *)

vector(50, n, n--; 10*n) \\ Michel Marcus, Feb 05 2016

x='x+O('x^999); concat(0, Vec(10*x/(x-1)^2)) \\ Altug Alkan, Apr 11 2016

apply( A008592(n)=10*n, [1..55]) \\ M. F. Hasler, Apr 23 2021

From Vincenzo Librandi, Dec 24 2010: (Start)
G.f.: 10*x/(x-1)^2.
a(n) = 2*a(n-1) - a(n-2) for n > 1. (End)
a(n) = Sum_{i=2n-2..2n+2} i. - Wesley Ivan Hurt, Apr 11 2016
E.g.f.: 10*x*exp(x). - Stefano Spezia, May 31 2021

A133880 n modulo p repeated p times (where p=10).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1

Offset: 0

Hieronymus Fischer, Oct 10 2007

Periodic with length p^2=100.

a(n) = A179051(n) for n < 90. - Reinhard Zumkeller, Jun 27 2010

Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1).

Cf. A000040, A133620-A133625, A133630, A038509, A133634-A133636.

Cf. A133890, A133900, A133910.

Flatten[Table[PadRight[{},10,Mod[n,10]],{n,11}]] (* Harvey P. Dale, May 10 2012 *)

a(n)=(n\10+1)%10 \\ Charles R Greathouse IV, Nov 15 2022

The following formulas are given for a general parameter p (p=10 for this sequence).
a(n)=(1+floor(n/p)) mod p.
a(n)=1+floor(n/p)-p*floor((n+p)/p^2).
a(n)=(((n+p) mod p^2)-(n mod p))/p.
a(n)=((n+p-(n mod p))/p) mod p.
G.f. g(x)=((p-1)x^(p^2)-px^(p(p-1))+1)/((1-x)(1-x^p)(1-x^(p^2))).
G.f. g(x)=(1-x^p)*sum{0<=k<(p-1), (k+1)*x^(k*p)}/((1-x)(1-x^(p^2))).

A062051 Number of partitions of n into powers of 3.

Original entry on oeis.org

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

A132272 a(n) = Product_{k>0} (1 + floor(n/10^k)).

Original entry on oeis.org

Offset: 0

Hieronymus Fischer, Aug 20 2007

If n is written in base-10 as n=d(m)d(m-1)d(m-2)...d(2)d(1)d(0) (where d(k) is the digit at position k) then a(n) is also the product (1+d(m)d(m-1)d(m-2)...d(2)d(1))*(1+d(m)d(m-1)d(m-2)...d(2))*...*(1+d(m)d(m-1)d(m-2))*(1+d(m)d(m-1))*(1+d(m)).

a(n) = A179051(n) for n < 100. [From Reinhard Zumkeller, Jun 27 2010]

			a(121)=(1+floor(121/10^1))*(1+floor(121/10^2))=13*2=26; a(132)=28 since 132=132(base-10) and so
a(132)=(1+13)*(1+1)(base-10)=14*2=28.

R. J. Mathar, Table of n, a(n) for n = 0..500

Cf. A132038, A132270(p=2), A132271, A132325, A132328(p=3), A132271.

For the product of terms floor(n/p^k) see A098844, A067080, A132027-A132033, A132263, A132264.

A132272 := proc(n)
    a := 1;
    for k from 1 do
        f := floor(n/10^k) ;
        if f <=0 then
            return a;
        else
            a := a*(1+f) ;
        end if;
    end do:
end proc:
seq(A132272(n),n=1..120) ; # R. J. Mathar, Jun 13 2025

Table[Product[1+Floor[n/10^k],{k,n}],{n,0,100}] (* Harvey P. Dale, Jul 20 2024 *)

The following formulas are given for a general parameter p considering the product of terms 1+floor(n/p^k) for 0

Recurrence: a(n)=(1+floor(n/p))*a(floor(n/p)); a(pn)=(1+n)*a(n); a(n*p^m)=product{0<=k

a(k*p^m-j)=k^m*p^(m(m-1)/2), for 0=1. a(p^m)=p^(m(m-1)/2)*product{0<=k

a(n)=A132271(floor(n/p))=A132271(n)/(1+n).

Asymptotic behavior: a(n)=O(n^((log_p(n)-1)/p)); this follows from the inequalities below.

a(n)<=A067080(n)/(n+1)*product{0<=k<=floor(log_p(n)), 1+1/p^k}.

a(n)>=A067080(n)/((n+1)*product{0

a(n)A000217(log_p(n))/(n+1), where c=product{k>0, 1+1/p^k}=2.2244691382741012... (for p=10 see constant A132325).

a(n)>n^((1+log_p(n))/2)/(n+1)=p^A000217(log_p(n))/(n+1).

lim sup n*a(n)/A067080(n)=2*product{k>0, 1+1/p^k}=2.2244691382741012..., for n-->oo (for p=10 see constant A132325).

lim inf n*a(n)/A067080(n)=1/product{k>0, 1-1/p^k}=1/0.8900100999989990000001000..., for n-->oo (for p=10 s. constant A132038).

lim inf a(n)/n^((1+log_p(n))/2)=1, for n-->oo.

lim sup a(n)/n^((1+log_p(n))/2)=2*product{k>0, 1+1/p^k}=2.2244691382741012..., for n-->oo (for p=10 see constant A132325).

lim inf a(n+1)/a(n)=2*product{k>0, 1+1/p^k}=2.2244691382741012... for n-->oo (for p=10 see constant A132325).

A329624 Number of iterations of A329623 for starting value n before a repeated value appears, or -1 if this never happens.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10

Offset: 1

Scott R. Shannon, Nov 19 2019

This sequence gives the number of iterations of A329623 for start value n before a repeated value first appears. Unlike the "ghost iteration" of A329200 the only fixed points are the single digits 0 to 9. See A328865 for the first repeating value.
Due to A329623(n) being significantly larger than n for some values of n, the iterative sequence can grow to infinity for some n. The first value to do so is n = 1373. This appears due to the occurrence of the digit string '62637' at the end of the term of the third iteration. These five digits reappear every second iteration at the end of the term, but with more and more digits preceding it. A329917 lists other divergent n values.
The smallest value, for n >= 10, which acts as an end point before repeating is 9, which is the final value for many starting values.
The digit string '8091' forms the basis of a very long convergent series for some values of n. The digit string consisting of an arbitrary number of copies of '80' followed by '91' will eventually converge to 8091, then 891, then 91, which finally converges in ten more iterations. We can thus form a number of arbitrary length using this rule which is guaranteed to converge. This sequence appears naturally with the starting value n = 139100 which converges to 9 after 136 iterations after reaching a term with 72 digits after 20 iterations. See the linked file below.
From M. F. Hasler, Dec 03 2019: (Start)
It seems the a(n) = -1 are conjectural, i.e., we have no proof that the terms for which the trajectory seems to "explode" do not eventually end up in a cycle. For example, the 8th iterate of 1373 is 5218725017016262626273. If the 2nd digit is changed from 2 to 0, then the further iterates appear to explode up to a length of 157 bits, but finally end up in a 2-cycle of 41-digit numbers (26...26273, 62...62637).
The "repeating values" are members of cycles, listed in A328142. Only fixed points 1, ..., 9 and 4*(10^k-1)/9 + 11, k >=3, and 6 infinite families of 2-cycles are known.
(End)
The first escape value is a(1373) = -1 (without proof). - Georg Fischer, Jul 16 2020

			a(1) = 1 as A329623(1) = 1, so a repeating value occurs after 1 iteration.
a(10) = 2 as A329623(10) = 9 and A329623(9) = 9, so a repeating value occurs after 2 iterations.
a(128) = 3, as A329623(128) = 182, A329623(182) = 728, A329623(728) = 182, so a repeating value occurs after 3 iterations.

Scott R. Shannon, Table of n, a(n) for n = 1..10000
Scott R. Shannon, The iterative series for start value n = 139100.

Cf. A329623, A329197, A329200, A328865, A329917.

Sequences A324160, A226233, A179051, A140438, A132272 are unrelated; they begin with the same numbers as this sequence but differ after a(110) = 10, which ends the pattern of incrementing numbers, 2 through 11, repeated ten times.

A329624(n,L=n^10,U=[n])=-!for(i=1,oo,setsearch(U,n=A329623(n))&&return(i); nM. F. Hasler, Dec 02 2019

A145513 Number of partitions of 10^n into powers of 10.

Original entry on oeis.org

1, 2, 12, 562, 195812, 515009562, 10837901390812, 1899421190329234562, 2851206628197445401265812, 37421114946843687272702534859562, 4362395890943439751990308572939648140812, 4573514084633441973328831327010967245403925484562, 43557001521047571730475817291330175020887917015964570015812

Offset: 0

Alois P. Heinz, Oct 11 2008

nonn

a(n) = A179051(10^n); for n>0: a(n) = A179052(10^(n-1)). - Reinhard Zumkeller, Jun 27 2010

			a(1) = 2, because there are 2 partitions of 10^1 into powers of 10: [1,1,1,1,1,1,1,1,1,1], [10].

Alois P. Heinz, Table of n, a(n) for n = 0..45

Cf. 10th column of A145515, A007318.

Cf. A011557, A002577, A078125.

import Data.MemoCombinators (memo2, list, integral)
a145513 n = a145513_list !! n
a145513_list = f [1] where
   f xs = (p' xs $ last xs) : f (1 : map (* 10) xs)
   p' = memo2 (list integral) integral p
   p  0 = 1; p []  = 0
   p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
-- Reinhard Zumkeller, Nov 27 2015

g:= proc(b,n,k) option remember; local t; if b<0 then 0 elif b=0 or n=0 or k<=1 then 1 elif b>=n then add(g(b-t, n, k) *binomial(n+1, t) *(-1)^(t+1), t=1..n+1); else g(b-1, n, k) +g(b*k, n-1, k) fi end: a:= n-> g(1,n,10): seq(a(n), n=0..13);

g[b_, n_, k_] := g[b, n, k] = Module[{t}, Which[b < 0, 0, b == 0 || n == 0 || k <= 1, 1, b >= n, Sum[g[b - t, n, k]*Binomial[n + 1, t] *(-1)^(t + 1), {t, 1, n + 1}], True, g[b - 1, n, k] + g[b*k, n - 1, k]]]; a[n_] := g[1, n, 10]; Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)

a(n) = [x^(10^n)] 1/Product_{j>=0} (1-x^(10^j)).

A206245 Number of partitions of n into repunit powers, cf. A083278.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset: 0

Reinhard Zumkeller, Feb 05 2012

nonn

a(n) = A206244(n) for n <= 120, a(n) > A206244(n) for n > 120.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Repunit
Wikipedia, Repunit
Index entries for related partition-counting sequences

Cf. A002275, A000041, A179051.

a206245 = p a083278_list where
   p _      0 = 1
   p rps'@(rp:rps) n = if n < rp then 0 else p rps' (n - rp) + p rps n

A206244 Number of partitions of n into repunits (A002275).

Original entry on oeis.org

Offset: 0

Reinhard Zumkeller, Feb 05 2012

nonn

a(n) = A206245(n) for n <= 120, a(n) < A206245(n) for n > 120.

			a(12)=2 is the first nontrivial term, from the partitions 12 = 1+1+...+1 = 11+1. - _N. J. A. Sloane_, Jul 26 2017

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Repunit
Wikipedia, Repunit
Index entries for related partition-counting sequences

Cf. A000041, A002275, A179051.

a206244 = p $ tail a002275_list where
   p _             0 = 1
   p rus'@(ru:rus) n = if n < ru then 0 else p rus' (n - ru) + p rus n

With[{nn = 50}, Table[Count[IntegerPartitions@ n, k_ /; ContainsAll[Array[Floor[10^#/9] &, IntegerLength[nn + 1]], Union@ k]], {n, 0, nn}]] (* Michael De Vlieger, Jul 26 2017 *)

G.f.: Product_{k>=1} 1/(1 - x^((10^k-1)/9)). - Ilya Gutkovskiy, Jul 26 2017

Showing 1-10 of 10 results.

cp's OEIS Frontend

A179052 Range and record values of number of partitions of n into powers of 10 (cf. A179051).

Views

Author

Keywords

Comments

Links

A018819 Binary partition function: number of partitions of n into powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A008592 Multiples of 10: a(n) = 10*n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

A133880 n modulo p repeated p times (where p=10).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A062051 Number of partitions of n into powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A132272 a(n) = Product_{k>0} (1 + floor(n/10^k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A329624 Number of iterations of A329623 for starting value n before a repeated value appears, or -1 if this never happens.

Views