A005704 -id:A005704 - cp's OEIS frontend

A268127 a(n) = (A005704(n)-A006047(n))/3.

0, 0, 0, 1, 1, 1, 3, 3, 3, 7, 8, 9, 12, 13, 14, 19, 20, 21, 30, 33, 36, 42, 45, 48, 57, 60, 63, 79, 86, 93, 103, 111, 119, 132, 141, 150, 168, 180, 192, 209, 222, 235, 257, 271, 285, 316, 335, 354, 380, 400, 420, 453, 474, 495, 543, 573, 603, 639, 672, 705, 747

Offset: 0

Tom Edgar, Jan 26 2016

nonn

G. E. Andrews, A. S. Fraenkel, and J. A. Sellers, Characterizing the number of m-ary partitions modulo m, The American Mathematical Monthly, Vol. 122, No. 9 (November 2015), pp. 880-885.
G. E. Andrews, A. S. Fraenkel, and J. A. Sellers, Characterizing the number of m-ary partitions modulo m.
Tom Edgar, The distribution of the number of parts of m-ary partitions modulo m., arXiv:1603.00085 [math.CO], 2016.

Cf. A005704, A006047, A268128.

b[n_] := b[n] = If[n <= 2, n+1, b[n-1] + b[Floor[n/3]]];
c = Nest[Join[#, 2#, 3#]&, {1}, 4];
a[n_] := (b[n] - c[[n+1]])/3;
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Dec 12 2018 *)

def b(n):
    A=[1]
    for i in [1..n]:
        A.append(A[i-1] + A[floor(i/3)])
    return A[n]
[(b(n)-prod(x+1 for x in n.digits(3)))/3 for n in [0..60]]

Let b(0) = 1 and b(n) = b(n-1) + b(floor(n/3)) and let c(n) = Product_{i=0..k}(n_i+1) where n = Sum_{i=0..k}n_i*3^i is the ternary representation of n. Then a(n) = (1/3)*(b(n) - c(n)).

A132843 a(n) = A005704( A037480(n) ) for n>0 with a(0)=1, where A005704 = number of partitions of 3n into powers of 3 and A037480(n) = n-th number having alternating base-3 digits 1, 2 (starting with '1').

Original entry on oeis.org

1, 2, 9, 72, 1296, 52407, 5240052, 1314516033, 853923545352, 1457086698392796, 6631460154689418828, 81384300080656595328843, 2719577128999047606509974434, 249432083657086432899494832228657

Offset: 0

Paul D. Hanna, Sep 27 2007

			Let b(n) = A005704(n) = number of partitions of 3n into powers of 3,
then the initial terms of this sequence begin:
b(0), b(1), b(5), b(16), b(50), b(151), b(455), b(1366),...
APPLICATION: SPECIAL TERNARY TREE.
a(n) = number of nodes in generation n of the following tree.
Start at generation 0 with a single root node labeled [2].
From then on, each parent node [k] is attached k child nodes with
labels congruent to 2(mod 3) for even n, or 3(mod 3) for odd n,
within the range {1..3k}, for generation n >= 0.
The initial generations 0..3 of the tree begin as follows;
the path from the root node is given, followed by child nodes in [].
GEN.0: [2];
GEN.1: 2->[3,6];
GEN.2:
2-3->[2,5,8]
2-6->[2,5,8,11,14,17];
GEN.3:
2-3-2->[3,6]
2-3-5->[3,6,9,12,15]
2-3-8->[3,6,9,12,15,18,21,24]
2-6-2->[3,6]
2-6-5->[3,6,9,12,15]
2-6-8->[3,6,9,12,15,18,21,24]
2-6-11->[3,6,9,12,15,18,21,24,27,30,33]
2-6-14->[3,6,9,12,15,18,21,24,27,30,33,36,39,42]
2-6-17->[3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51] .
Note: largest node label in generation n is A037480(n) + 1,
and the sum of the labels in generation n equals a(n+1).

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

Cf. A005704, A037480; variant: A132880.

{A005704(n) = if(n<1, n==0, A005704(n\3) + A005704(n-1))}
{a(n) = A005704( (5*3^n + (-1)^n - 6)/8 )}

a(n) = A005704( (5*3^n + (-1)^n - 6)/8 ).

A133987 a(n) = A005704( (3^n + (-1)^n - 2)/4 ), where A005704(n) = number of partitions of 3n into powers of 3.

Original entry on oeis.org

1, 1, 3, 12, 117, 2250, 107352, 12298500, 3613136949, 2742962912055, 5503085134707267, 29497134965411187747, 427365985177386403469028, 16883252883454411208147060304, 1832920589508888783152391724736550

Offset: 0

Paul D. Hanna, Oct 01 2007

nonn

			Let b(n) = A005704(n) = number of partitions of 3n into powers of 3, then
the initial terms of this sequence begin:
b(0), b(0), b(2), b(6), b(20), b(60), b(182), b(546), b(1640),...
APPLICATION: SPECIAL TERNARY TREE.
a(n) = number of nodes in generation n of the following tree.
Start at generation 0 with a single root node labeled [1].
From then on, each parent node [k] is attached to k child nodes with
labels congruent to 1(mod 3) for even n, or 3(mod 3) for odd n,
within the range {1..3k}, for generation n >= 0.
The initial generations 0..4 of the tree are as follows;
the path from the root node is given, followed by child nodes in [].
GEN.0: [1];
GEN.1: 1->[3];
GEN.2: 1-3->[1,4,7];
GEN.3:
1-3-1->[3]
1-3-4->[3,6,9,12]
1-3-7->[3,6,9,12,15,18,21];
GEN.4:
1-3-1-3->[1,4,7]
1-3-4-3->[1,4,7]
1-3-4-6->[1,4,7,10,13,16]
1-3-4-9->[1,4,7,10,13,16,19,22,25]
1-3-4-12->[1,4,7,10,13,16,19,22,25,28,31,34]
1-3-7-3->[1,4,7]
1-3-7-6->[1,4,7,10,13,16]
1-3-7-9->[1,4,7,10,13,16,19,22,25]
1-3-7-12->[1,4,7,10,13,16,19,22,25,28,31,34]
1-3-7-15->[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43]
1-3-7-18->[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52]
1-3-7-21->[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61] .
Note: the sum of the labels in generation n equals a(n+1) and
the largest term in generation n = (3^(n+1) + (-1)^(n+1) - 2)/4 + 1.

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

Cf. A005704; variants: A132843, A132880.

{A005704(n) = if(n<1, n==0, A005704(n\3) + A005704(n-1))} {a(n) = A005704( (3^n + (-1)^n - 2)/4 )}

(3^n + (-1)^n - 2)/4 gives the n-th number that has alternating base-3 digits {0,2} (starting with zero).

A000123 Number of binary partitions: number of partitions of 2n into powers of 2.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390, 450, 524, 598, 692, 786, 900, 1014, 1154, 1294, 1460, 1626, 1828, 2030, 2268, 2506, 2790, 3074, 3404, 3734, 4124, 4514, 4964, 5414, 5938, 6462, 7060, 7658, 8350, 9042, 9828

Offset: 0

N. J. A. Sloane

Also, a(n) = number of "non-squashing" partitions of 2n (or 2n+1), that is, partitions 2n = 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 [Hirschhorn and Sellers].
Row sums of A101566. - Paul Barry, Jan 03 2005
Equals infinite convolution product of [1,2,2,2,2,2,2,2,2] aerated A000079 - 1 times, i.e., [1,2,2,2,2,2,2,2,2] * [1,0,2,0,2,0,2,0,2] * [1,0,0,0,2,0,0,0,2]. - Mats Granvik and Gary W. Adamson, Aug 04 2009
Which can be further decomposed to the infinite convolution product of finally supported sequences, namely [1,1] aerated A000079 - 1 times with multiplicity A000027 + 1 times, i.e., [1,1] * [1,1] * [1,0,1] * [1,0,1] * [1,0,1] * ... (next terms are [1,0,0,0,1] 4 times, etc.). - Eitan Y. Levine, Jun 18 2023
Given A018819 = A000123 with repeats, polcoeff (1, 1, 2, 2, 4, 4, ...) * (1, 1, 1, ...) = (1, 2, 4, 6, 10, ...) = (1, 0, 2, 0, 4, 0, 6, ...) * (1, 2, 2, 2, ...). - Gary W. Adamson, Dec 16 2009
Let M = an infinite lower triangular matrix with (1, 2, 2, 2, ...) in every column shifted down twice. A000123 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. Replacing (1, 2, 2, 2, ...) with (1, 3, 3, 3, ...) and following the same procedure, we obtain A171370: (1, 3, 6, 12, 18, 30, 42, 66, 84, 120, ...). - Gary W. Adamson, Dec 06 2009
First differences of the sequence are (1, 2, 2, 4, 4, 6, 6, 10, ...), A018819, i.e., the sequence itself with each term duplicated except for the first one (unless a 0 is prefixed before taking the first differences), as shown by the formula a(n) - a(n-1) = a(floor(n/2)), valid for all n including n = 0 if we let a(-1) = 0. - M. F. Hasler, Feb 19 2019
Sum over k <= n of number of partitions of k into powers of 2, A018819. - Peter Munn, Feb 21 2020

			For non-squashing partitions and binary partitions see the example in A018819.
For n=3, the a(3)=6 admitted partitions of 2n=6 are 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2, 1+1+4 and 2+4. - _R. J. Mathar_, Aug 11 2021

G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.
H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..65536 (first 10001 terms from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook), p. 728
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, 2012. - From _N. J. A. Sloane_, Dec 23 2012
Sara Billey, Matjaž Konvalinka and Frederick A. Matsen IV, On trees, tanglegrams, and tangled chains, hal-02173394 [math.CO], 2020.
Henry Bottomley, Illustration of initial terms
N. G. de Bruijn, On Mahler's partition problem, 1948.
R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc. 66 1969 371-376.
Philippe Deléham, Letter to N. J. A. Sloane, Apr 20 1998
P. Dumas and P. Flajolet, Asymptotique des recurrences mahleriennes: le cas cyclotomique, Journal de Théorie des Nombres de Bordeaux 8 (1996), pp. 1-30.
Amanda Folsom et al, On a general class of non-squashing partitions, Discrete Mathematics 339.5 (2016): 1482-1506.
C.-E. Froberg, Accurate estimation of the number of binary partitions, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.
C.-E. Froberg, Accurate estimation of the number of binary partitions [Annotated scanned copy]
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.
H. Gupta, Proof of the Churchhouse conjecture concerning binary partitions, Proc. Camb. Phil. Soc. 70 (1971), 53-56.
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions
Youkow Homma, Jun Hwan Ryu and Benjamin Tong, Sequence non-squashing partitions, Slides from a talk, Jul 24 2014.
K. Ji and H. S. Wilf, Extreme palindromes, Amer. Math. Monthly, 115, no. 5 (2008), 447-451.
Y. Kachi and P. Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
D. E. Knuth, An almost linear recurrence, Fib. Quart., 4 (1966), 117-128.
M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections - _N. J. A. Sloane_, Dec 22 2012
M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.
Vaclav Kotesovec, Graph - the asymptotic ratio (10^8 terms)
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]
K. Mahler, On a special functional equation, Journ. London Math. Soc. 15 (1940), 115-123.
Mathematics Stack Exchange, Efficient computation of number of partitions into powers of 2, Jul 10 2024.
E. O'Shea, M-partitions: optimal partitions of weight for one scale pan, Discrete Math. 289 (2004), 81-93. See Lemma 29.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
John L. Pfaltz, Evaluating the binary partition function when N = 2^n, Congr. Numer, 109:3-12, 1995. [Broken link]
B. Reznick, Some binary partition functions, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990.
O. J. Rodseth, Enumeration of M-partitions, Discrete Math., 306 (2006), 694-698.
O. J. Rodseth and J. A. Sellers, Binary partitions revisited, J. Combinatorial Theory, Series A 98 (2002), 33-45.
O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
D. Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
Frank Ruskey, Info on binary partitions
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.
Daniel G. Zhu, An improved lower bound on the Shannon capacities of complements of odd cycles, arXiv:2402.10025 [math.CO], 2024.
Index entries for "core" sequences

Cf. A000041, A002033, A002487, A002577, A005704-A005706, A023359, A040039, A100529. Partial sums and bisection of A018819.
A column of A072170. Row sums of A089177. Twice A033485.
Cf. A145515. - Alois P. Heinz, Apr 16 2009
Cf. A171370. - Gary W. Adamson, Dec 06 2009

import Data.List (transpose)
a000123 n = a000123_list !! n
a000123_list = 1 : zipWith (+)
   a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])
-- Reinhard Zumkeller, Nov 15 2012, Aug 01 2011

[1] cat [n eq 1 select n+1 else Self(n-1) + Self(n div 2): n in [1..70]]; // Vincenzo Librandi, Dec 17 2016

A000123 := proc(n) option remember; if n=0 then 1 else A000123(n-1)+A000123(floor(n/2)); fi; end; [ seq(A000123(i),i=0..50) ];
# second Maple program: more efficient for large n; try: a( 10^25 );
g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or
      n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)
      *g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))
    end:
a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):
seq(a(n), n=0..60); # Alois P. Heinz, Apr 16 2009, revised Apr 14 2016

a[0] = 1; a[n_] := a[n] = a[Floor[n/2]] + a[n-1]; Array[a,49,0] (* Jean-François Alcover, Apr 11 2011, after M. F. Hasler *)
Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* Birkas Gyorgy, Apr 18 2011 *)

{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) / (1-x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */

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

A123=[];A000123(n)={ n<3 && return(2^n); if( n<=#A123, A123[n] && return(A123[n]); A123[n-1] && return( A123[n] = A123[n-1]+A000123(n\2) ), n>2*#A123 && A123=concat(A123,vector((n-#A123)\2))); A123[if(n>#A123,1,n)]=2*sum(k=1,n\2-1,A000123(k),1)+(n%2+1)*A000123(n\2)} \\ Stores results in global vector A123 dynamically resized to at most 3n/4 when size is less than n/2. Gives a(n*10^6) in ~ n sec. - M. F. Hasler, Apr 30 2009

{a(n)=polcoeff(exp(sum(m=1,n,2^valuation(2*m,2)*x^m/m)+x*O(x^n)),n)} \\ Paul D. Hanna, Oct 30 2012

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

a(n) = A018819(2*n).
a(n) = a(n-1) + a(floor(n/2)). For proof see A018819.
2 * a(n) = a(n+1) + a(n-1) if n is even. - Michael Somos, Jan 07 2011
G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).
a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].
a(n) = (1/n)*Sum_{k=1..n} (A038712(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002
Conjecture: Limit_{n ->infinity} (log(n)*a(2n))/(n*a(n)) = c = 1.63... - Benoit Cloitre, Jan 26 2003 [The constant c is equal to 2*log(2) = 1.38629436... =A016627. - Vaclav Kotesovec, Aug 07 2019]
G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - Michael Somos, Aug 25 2003
G.f.: Product_{k>=0} (1+x^(2^k))/(1-x^(2^k)) = (Product_{k>=0} (1+x^(2^k))^(k+1) )/(1-x) = Product_{k>=0} (1+x^(2^k))^(k+2). - Joerg Arndt, Apr 24 2005
From Philippe Flajolet, Sep 06 2008: (Start)
The asymptotic rate of growth is known precisely - see De Bruijn's paper. With p(n) the number of partitions of n into powers of two, the asymptotic formula of de Bruijn is: log(p(2*n)) = 1/(2*L2)*(log(n/log(n)))^2 + (1/2 + 1/L2 + LL2/L2)*log(n) - (1 + LL2/L2)*log(log(n)) + Phi(log(n/log(n))/L2), where L2=log(2), LL2=log(log(2)) and Phi(x) is a certain periodic function with period 1 and a tiny amplitude.
Numerically, Phi(x) appears to have a mean value around 0.66. An expansion up to O(1) term had been obtained earlier by Kurt Mahler. (End)
G.f.: exp( Sum_{n>=1} 2^A001511(n) * x^n/n ), where 2^A001511(n) is the highest power of 2 that divides 2*n. - Paul D. Hanna, Oct 30 2012
(n/2)*a(n) = Sum_{k = 0..n-1} (n-k)/A000265(n-k)*a(k). - Peter Bala, Mar 03 2019
Conjectures from Mikhail Kurkov, May 04 2025: (Start)
Sum_{k=0..n} a(2^m*k)*A106400(n-k) = A125790(m,2*n) for m >= 0, n >= 0.
Sum_{k=0..n} a(2^m*(2*k+1))*A106400(n-k) = A125790(m+1,2*n+1) for m >= 0, n >= 0.
More generally, if we define b(n,m,p,q) = Sum_{k=0..n} a(2^m*(2*p*k+2*q+1))*A106400(n-k) for m >= 0, p > 0, q >= 0, n >= 0, then it also looks like that we have b(n,m,p,q) = Sum_{k=0..m+1} A078121(m+1,k)*b(n,k,p/2,(q-1)/2), b(n,m,p,q) = Sum_{k=0..m+1} A078121(m+1,k)*b(n,k,p/2,q/2)*(-1)^(m+k+1) for m >= 0, p > 0, q >= 0, n >= 0. (End)
Conjecture: Sum_{i>=0} a(2^m*i + k)*x^i = f(k,x) / Product_{q>=0} (1 - x^(2^q)) for m > 0, 2^(m-1) <= k < 2^m where f(k,x) is g.f. for k-th row of A381810. - Mikhail Kurkov, May 17 2025

More terms from Robin Trew (trew(AT)hcs.harvard.edu)

Values up to a(10^4) checked with given PARI code by M. F. Hasler, Apr 30 2009

A006336 a(n) = a(n-1) + a(n - 1 - number of even terms so far).

Original entry on oeis.org

1, 2, 3, 5, 8, 11, 16, 21, 29, 40, 51, 67, 88, 109, 138, 167, 207, 258, 309, 376, 443, 531, 640, 749, 887, 1054, 1221, 1428, 1635, 1893, 2202, 2511, 2887, 3330, 3773, 4304, 4835, 5475, 6224, 6973, 7860, 8747, 9801, 11022, 12243, 13671, 15306, 16941

Offset: 1

D. R. Hofstadter, Jul 15 1977

From T. D. Noe, Jul 27 2007: (Start)
This is similar to A000123 and A005704, which both have a recursion a(n)=a(n-1)+a([n/k]), where k is 2 and 3, respectively. Those sequences count "partitions of k*n into powers of k". For the present sequence, k=phi. Does A006336(n) count the partitions of n*phi into powers of phi?
Answering my own question: If the recursion starts with a(0)=1, then I think we obtain "number of partitions of n*phi into powers of phi" (see A131882).
Here we need negative powers of phi also: letting p=phi and q=1/phi, we have
n=0: 0*p = {} for 1 partition,
n=1: 1*p = p = 1+q for 2 partitions,
n=2: 2*p = p+p = 1+p+q = 1+1+q+q = p^2+q for 4 partitions, etc.
So the present sequence, which starts with a(1)=1, counts 1/2 of the "number of partitions of n*phi into powers of phi". (End)

N. J. A. Sloane, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Max Alekseyev, Proof of Paul Hanna's formula.
D. R. Hofstadter, Eta-Lore. [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences. [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991.

Cf. A007604, A000123, A005704, A131882, A134408, A134409, A001950.

"Number of even terms so far" is A060144(n+1).

a006336 n = a006336_list !! (n-1)
a006336_list = 1 : h 2 1 0 where
  h n last evens = x : h (n + 1) x (evens + 1 - x `mod` 2) where
    x = last + a006336 (n - 1 - evens)
-- Reinhard Zumkeller, May 18 2011

# Maple code for first M terms of a(n) and A060144, from N. J. A. Sloane, Oct 25 2014
M:=100;
v[1]:=1; v[2]:=2; w[1]:=0; w[2]:=1;
for n from 3 to M do
   v[n]:=v[n-1]+v[n-1-w[n-1]];
if v[n] mod 2 = 0 then w[n]:=w[n-1]+1 else w[n]:=w[n-1]; fi; od:
[seq(v[n],n=1..M)]; # A006336
[seq(w[n],n=1..M)]; # A060144 shifted

a[n_Integer] := a[n] = Block[{c, k}, c = 0; k = 1; While[k < n, If[ EvenQ[ a[k] ], c++ ]; k++ ]; Return[a[n - 1] + a[n - 1 - c] ] ]; a[1] = 1; a[2] = 2; Table[ a[n], {n, 0, 60} ]

A006336(N=99) = local(a=vector(N,i,1), e=0); for(n=2,#a,e+=0==(a[n]=a[n-1]+a[n-1-e])%2);a \\ M. F. Hasler, Jul 23 2007

It seems that A006336 can be generated by a rule using the golden ratio phi: a(n) = a(n-1) + a([n/Phi]) for n>1 with a(1)=1 where phi = (sqrt(5)+1)/2, I.e. the number of even terms up to position n-1 equals n-1 - [n/Phi] for n>1 where Phi = (sqrt(5)+1)/2. (This is true - see the Alekseyev link.) - Paul D. Hanna, Jul 22 2007

a(n) = a(n-1)+a(A060143(n)) for n>1; subsequence of A134409; A134408 and A134409 give first and second differences; A001950(n)=Min(m:A134409(m)=a(n)). - Reinhard Zumkeller, Oct 24 2007

More terms from Robert G. Wilson v, Mar 07 2001

Entry revised by N. J. A. Sloane, Oct 25 2014

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

A254296 The number of partitions of n having the minimum number of summands such that all integers from 1 to n can be represented as the sum of the summands times one of {-1, 0, 1}.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 2, 2, 2, 1, 1, 1, 10, 11, 12, 11, 12, 12, 11, 11, 12, 9, 9, 9, 7, 7, 7, 5, 5, 5, 3, 3, 3, 2, 2, 2, 1, 1, 1, 131, 136, 140, 133, 137, 140, 133, 136, 138, 129, 131, 134, 125, 126, 128, 117, 119, 120, 109, 110, 111, 101, 102, 102, 92, 92, 93, 81, 81, 81, 72, 72, 72, 63, 63, 63, 54, 54, 54, 47, 47, 47, 40, 40, 40, 33, 33, 33

Offset: 1

Md. Towhidul Islam, Jan 27 2015

Define a feasible partition of an n-kilogram stone as an ordered partition of minimum possible m parts W_1 <= W_2 <= ... <= W_m broken from the stone such that all integral weights from 1 to n can be weighed in one weighing using the parts/weights on a two pan balance. The minimum m for any n is m=ceiling(log_3(2n)). This sequence gives the number of feasible partitions of n.
From Robert G. Wilson v, Feb 04 2015: (Start)
Records: 1, 2, 3, 10, 11, 12, 131, 136, 140, 3887, 3921, 3950, 262555, 263112, 263707, 42240104, 42262878, 42285095, 16821037273, 16823225535, 16825391023, ..., .
Possible values: 1, 2, 3, 5, 7, 9, 10, 11, 12, 15, 18, 23, 28, 33, 40, 47, 54, 63, 72, 81, 92, 93, 101, 102, 105, ..., .
First occurrence on k, or 0 if not present: 1, 5, 7, 0 29, 0, 26, 0, 23, 14, 15, 16, 0, 0, 98, 0, 0, 95, 0, 0, 0, 0, 92, ..., .
1 occurs at: 1, 2, 3, 4, 11, 12, 13, 38, 39, 40, 119, 120, 121, 362, 363, 364, 1091, 1092, 1093, 3278, 3279, 3280, 9839, 9840, 9841, ..., .
2 occurs at: 5, 6, 8, 9, 10, 35, 36, 37, 116, 117, 118, 359, 360, 361, 1088, 1089, 1090, 3275, 3276, 3277, 9836, 9837, 9838, ..., .
3 occurs at: 7, 32, 33, 34, 113, 114, 115, 356, 357, 358, 1085, 1086, 1087, 3272, 3273, 3274, 9833, 9834, 9835, ..., .
5 occurs at: 29, 30, 31, 110, 111, 112, 353, 354, 355, 1082, 1083, 1084, 3269, 3270, 3271, 9830, 9831, 9832, ..., . (End)

			For n=3, minimum number of weights m is 2. The only "feasible" set of weights is [1,2]. So, a(3)=1.
For n=7, m is 3. The "feasible" sets of weights are [1,1,5], [1,2,4], [1,3,3]. So, a(7)=3.
For n=19, m is 4. The "feasible" sets of weights are [1,1,4,13], [1,1,5,12], [1,2,3,13], [1,2,4,12], [1,2,5,11], [1,2,6,10], [1,2,7,9], [1,3,3,12], [1,3,4,11], [1,3,5,10], [1,3,6,9], [1,3,7,8]. There are no other "feasible" sets. So, a(19)=12.

Md. Towhidul Islam, Table of n, a(n) for n = 1..88573
Md. Towhidul Islam, Formula for number of feasible partitions of n
Md Towhidul Islam & 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.

Cf. A254296, A254430, A254431, A254432, A254433, A254435, A254436, A254437, A254438, A254439, A254440, A254442.

When we calculate a(n) for (3^(m-1)+1)/2+3^(m-2)+1 <= n <= (3^m-1)/2 starting from n=(3^m-1)/2 backwards, we get the sequence A062051 which is also the triplication of the terms of sequence A005704.

okQ[v_] := Module[{s=0}, For[i=1, i <= Length[v], i++, If[v[[i]] > 2*s+1, Return[ False], s += v[[i]] ] ]; Return[True]]; a[n_] := With[{k = Ceiling[Log[3, 2n]]}, Select[Reverse /@ IntegerPartitions[n, {k}], okQ] // Length]; Table[a[n], {n, 1, 88}] (* Jean-François Alcover, Feb 03 2015, after Charles R Greathouse IV *)

ok(v)=my(s);for(i=1,#v,if(v[i]>2*s+1,return(0),s+=v[i]));1
a(n)=my(k=ceil(log(2*n)/log(3))); #select(ok, partitions(n,,k)) \\ Charles R Greathouse IV, Feb 02 2015

Let us suppose, a(0)=1 and for (3^(m-1)+1)/2<=n<=(3^m-1)/2, m=ceiling(log_3(2n)).
Then for (3^(m-1)+1)/2<=n<=(3^(m-1)+1)/2+(3^(m-2)),a(n)=Sum{s=ceiling((n-1)/3..floor((2n+3^(m-2)-1)/4)}a(s)-Sum{d=ceiling((3n+2)/5)..(3^(m-1)-1)/2}Sum{p=ceiling((d-1)/3..2d-n-1}a(p)
and for (3^(m-1)+1)/2+3^(m-2)+1<=n<=(3^m-1)/2, a(n)=Sum_{s=ceiling((n-1)/3)..(3^(m-1)-1)/2}a(s).

A005706 Number of partitions of 5n into powers of 5.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 11, 13, 15, 18, 21, 24, 27, 30, 34, 38, 42, 46, 50, 55, 60, 65, 70, 75, 82, 89, 96, 103, 110, 119, 128, 137, 146, 155, 166, 177, 188, 199, 210, 223, 236, 249, 262, 275, 290, 305, 320, 335, 350, 368, 386, 404, 422, 440, 461, 482, 503, 524, 545

Offset: 0

N. J. A. Sloane

Euler transform of [2,0,0,0,1,0,0,0,0,...] with 1's at 5^n. - Michael Somos, Mar 16 2004

Partial sums of number of partitions of n into powers of 5. - Michael Somos, Mar 16 2004

R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..10000
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, preprint 2012; SIAM J. Discrete Math., 28(1), 342-371, 2014. - _N. J. A. Sloane_, Dec 23 2012
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions
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]
O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.

Column k=5 of A292477.

Cf. A000041, A000123, A005704, A005705.

a[0] = 1; a[n_] := a[n] = a[n - 1] + a[Floor[n/5]]; Table[a@ n, {n, 0, 60}] (* Michael De Vlieger, Mar 25 2016 *)

PARI
```
a(n)=if(n<1,n==0,a(n-1)+a(n\5))
```

a(n) = a(n-1) + a([n/5]).

a(n) = [x^(5*n)] Product_{k>=0} 1/(1 - x^(5^k)). - Ilya Gutkovskiy, Jun 05 2017

Formula and more terms from Henry Bottomley, Apr 30 2001

A006996 a(n) = C(2n,n) mod 3.

Original entry on oeis.org

1, 2, 0, 2, 1, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 2, 0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

N. J. A. Sloane, James Propp

Removing 0's from the sequence gives Thue-Morse sequence A001285 : 1,2,0,2,1,0,0,0,0,2,1,0,1,2,..->1,2,2,1,2,1,1,2,... - Benoit Cloitre, Jan 04 2004
a(n) = 0 if n in A074940, a(n) = 1 if n in A074939, a(n) = 2 if n in A074938.
Central terms of the triangle in A083093. - Reinhard Zumkeller, Jul 11 2013

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..2187=3^7
Michael Gilleland, Some Self-Similar Integer Sequences
Index entries for sequences that are fixed points of mappings

Cf. A001285.
Cf. A074938, A074939, A074940.
Cf. A083093.
Cf. A000984, A005704.

a006996 n = a083093 (2 * n) n  -- Reinhard Zumkeller, Jul 11 2013

Table[ Mod[ Binomial[2n, n], 3], {n, 0, 104}] (* Or *)
Nest[ Function[ l, {Flatten[(l /. {0 -> {0, 0, 0}, 1 -> {1, 2, 0}, 2 -> {2, 1, 0}})]}], {1}, 7] (* Robert G. Wilson v, Mar 28 2005 *)

a(n)=if(n==0, return(1)); if(vecmax(Set(digits(n,3)))>1, 0, 1 + n%2) \\ Charles R Greathouse IV, May 09 2016

from gmpy2 import digits
def A006996(n): return 0 if '2' in digits(n,3) else 1+(n&1) # Chai Wah Wu, Jun 26 2025

a(n) = A000984(n) mod 3.
a(n) = A005704(n) mod 3. - Benoit Cloitre, Jan 04 2004
A fixed point of the morphism : 1 -> 120, 2 -> 210, 0 -> 000. - Philippe Deléham, Jan 08 2004

A005705 Number of partitions of 4*n into powers of 4.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 10, 12, 15, 18, 21, 24, 28, 32, 36, 40, 46, 52, 58, 64, 72, 80, 88, 96, 106, 116, 126, 136, 148, 160, 172, 184, 199, 214, 229, 244, 262, 280, 298, 316, 337, 358, 379, 400, 424, 448, 472, 496, 524, 552, 580, 608, 640, 672, 704, 736, 772, 808, 844

Offset: 0

N. J. A. Sloane

Also number of partitions of 4*n+k into powers of 4 where k=1,2,3. - Michael Somos, Mar 15 2020

R. K. Guy, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..1000
C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics, preprint 2012; SIAM J. Discrete Math., 28(1), 342-371, 2014. - _N. J. A. Sloane_, Dec 23 2012
R. K. Guy, Letters to N. J. A. Sloane and J. W. Moon, 1988
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions
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]
O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.

Column k=4 of A292477.

Cf. A000041, A000123, A005704, A005706.

Fold[Append[#1, Total[Take[Flatten[Transpose[Table[#1, {4}]]], #2]]] &, {1},  Range[2, 20]] (* Birkas Gyorgy, Apr 18 2011 *)

a(n) = a(n-1) + a(floor(n/4)).

G.f.: T(x)=(1-x)^(-1)/(Product_{k>=0} 1-x^(4^k)), it satisfies T(x)=(1-x^4)/(1-x)^2*T(x^4). - Joerg Arndt, May 12 2010

Formula and more terms from Henry Bottomley, Apr 30 2001

cp's OEIS Frontend

A268127 a(n) = (A005704(n)-A006047(n))/3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A132843 a(n) = A005704( A037480(n) ) for n>0 with a(0)=1, where A005704 = number of partitions of 3n into powers of 3 and A037480(n) = n-th number having alternating base-3 digits 1, 2 (starting with '1').

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A133987 a(n) = A005704( (3^n + (-1)^n - 2)/4 ), where A005704(n) = number of partitions of 3n into powers of 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A000123 Number of binary partitions: number of partitions of 2n into powers of 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

Extensions

A006336 a(n) = a(n-1) + a(n - 1 - number of even terms so far).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A062051 Number of partitions of n into powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions