A171370 -id:A171370 - cp's OEIS frontend

A032766 Numbers that are congruent to 0 or 1 (mod 3).

0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 30, 31, 33, 34, 36, 37, 39, 40, 42, 43, 45, 46, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 66, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 90, 91, 93, 94, 96, 97, 99, 100, 102, 103

Offset: 0

Patrick De Geest, May 15 1998

Omitting the initial 0, a(n) is the number of 1's in the n-th row of the triangle in A118111. - Hans Havermann, May 26 2002
Binomial transform is A053220. - Michael Somos, Jul 10 2003
Smallest number of different people in a set of n-1 photographs that satisfies the following conditions: In each photograph there are 3 women, the woman in the middle is the mother of the person on her left and is a sister of the person on her right and the women in the middle of the photographs are all different. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006
Partial sums of A000034. - Richard Choulet, Jan 28 2010
Starting with 1 = row sums of triangle A171370. - Gary W. Adamson, Feb 15 2010
a(n) is the set of values for m in which 6k + m can be a perfect square (quadratic residues of 6 including trivial case of 0). - Gary Detlefs, Mar 19 2010
For n >= 2, a(n) is the smallest number with n as an anti-divisor. - Franklin T. Adams-Watters, Oct 28 2011
Sequence is also the maximum number of floors with 3 elevators and n stops in a "Convenient Building". See A196592 and Erich Friedman link below. - Robert Price, May 30 2013
a(n) is also the total number of coins left after packing 4-curves patterns (4c2) into a fountain of coins base n. The total number of 4c2 is A002620 and voids left is A000982. See illustration in links. - Kival Ngaokrajang, Oct 26 2013
Number of partitions of 6n into two even parts. - Wesley Ivan Hurt, Nov 15 2014
Number of partitions of 3n into exactly 2 parts. - Colin Barker, Mar 23 2015
Nonnegative m such that floor(2*m/3) = 2*floor(m/3). - Bruno Berselli, Dec 09 2015
For n >= 3, also the independence number of the n-web graph. - Eric W. Weisstein, Dec 31 2015
Equivalently, nonnegative numbers m for which m*(m+2)/3 and m*(m+5)/6 are integers. - Bruno Berselli, Jul 18 2016
Also the clique covering number of the n-Andrásfai graph for n > 0. - Eric W. Weisstein, Mar 26 2018
Maximum sum of degeneracies over all decompositions of the complete graph of order n+1 into three factors. The extremal decompositions are characterized in the Bickle link below. - Allan Bickle, Dec 21 2021
Also the Hadwiger number of the n-cocktail party graph. - Eric W. Weisstein, Apr 30 2022
The number of integer rectangles with a side of length n+1 and the property: the bisectors of the angles form a square within its limits. - Alexander M. Domashenko, Oct 17 2024
The maximum possible number of 5-cycles in an outerplanar graph on n+4 vertices. - Stephen Bartell, Jul 10 2025

Indranil Ghosh, Table of n, a(n) for n = 0..10000
Allan Bickle, Nordhaus-Gaddum Theorems for k-Decompositions, Congr. Num. 211 (2012) 171-183.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
Erich Friedman, Problem of the month November 2009
Z. Füredi, A. Kostochka, M. Stiebitz, R. Skrekovski, and D. West, Nordhaus-Gaddum-type theorems for decompositions into many parts, J. Graph Theory 50 (2005), 273-292.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 282. [Book's website]
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
International Mathematical Olympiad 2001, Hong Kong Preliminary Selection Contest, Problem #20. [Broken link; Cached copy]
Matroids Matheplanet, Number of d-generator groups of order 2^(d+1) and exponent-p class 2 (in German).
Emanuele Munarini, Topological indices for the antiregular graphs, Le Mathematiche, Vol. 76, No. 1 (2021), pp. 277-310, see p. 302.
Kival Ngaokrajang, Illustration of initial terms (U).
Eric Weisstein's World of Mathematics, Andrásfai Graph
Eric Weisstein's World of Mathematics, Clique Covering Number
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Hadwiger Number
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Web Graph
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A006578 (partial sums), A000034 (first differences), A016789 (complement).
Essentially the same: A049624.
Column 1 (the second leftmost) of triangular table A026374.
Column 1 (the leftmost) of square array A191450.
Row 1 of A254051.
Row sums of A171370.
Cf. A066272 for anti-divisors.
Cf. A253888 and A254049 (permutations of this sequence without the initial zero).
Cf. A254103 and A254104 (pair of permutations based on this sequence and its complement).
Cf. A000035, A000217, A000982, A001651, A002620, A002717, A003945.
Cf. A004396, A004526, A007310, A007494, A008619, A030308, A035360.
Cf. A047270, A049615, A052928, A053220, A070893, A084056, A092942.
Cf. A118111, A132463, A133083, A196592, A249745.

a032766 n = div n 2 + n  -- Reinhard Zumkeller, Dec 13 2014
(MIT/GNU Scheme) (define (A032766 n) (+ n (floor->exact (/ n 2)))) ;; Antti Karttunen, Jan 24 2015

&cat[ [n, n+1]: n in [0..100 by 3] ]; // Vincenzo Librandi, Nov 16 2014

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=a[n-2]+3 od: seq(a[n], n=0..69); # Zerinvary Lajos, Mar 16 2008
seq(floor(n/2)+n, n=0..69); # Gary Detlefs, Mar 19 2010
select(n->member(n mod 3,{0,1}), [$0..103]); # Peter Luschny, Apr 06 2014

a[n_] := a[n] = 2a[n - 1] - 2a[n - 3] + a[n - 4]; a[0] = 0; a[1] = 1; a[2] = 3; a[3] = 4; Array[a, 60, 0] (* Robert G. Wilson v, Mar 28 2011 *)
Select[Range[0, 200], MemberQ[{0, 1}, Mod[#, 3]] &] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
Flatten[{#,#+1}&/@(3Range[0,40])] (* or *) LinearRecurrence[{1,1,-1}, {0,1,3}, 100] (* or *) With[{nn=110}, Complement[Range[0,nn], Range[2,nn,3]]] (* Harvey P. Dale, Mar 10 2013 *)
CoefficientList[Series[x (1 + 2 x) / ((1 - x) (1 - x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Nov 16 2014 *)
Floor[3 Range[0, 69]/2] (* L. Edson Jeffery, Jan 14 2017 *)
Drop[Range[0,110],{3,-1,3}] (* Harvey P. Dale, Sep 02 2023 *)

PARI
```
{a(n) = n + n\2}
```

concat(0, Vec(x*(1+2*x)/((1-x)*(1-x^2)) + O(x^100))) \\ Altug Alkan, Dec 09 2015

[int(3*n//2) for n in range(101)] # G. C. Greubel, Jun 23 2024

G.f.: x*(1+2*x)/((1-x)*(1-x^2)).
a(-n) = -A007494(n).
a(n) = A049615(n, 2), for n > 2.
From Paul Barry, Sep 04 2003: (Start)
a(n) = (6n - 1 + (-1)^n)/4.
a(n) = floor((3n + 2)/2) - 1 = A001651(n) - 1.
a(n) = sqrt(2) * sqrt( (6n-1) (-1)^n + 18n^2 - 6n + 1 )/4.
a(n) = Sum_{k=0..n} 3/2 - 2*0^k + (-1)^k/2. (End)
a(n) = 3*floor(n/2) + (n mod 2) = A007494(n) - A000035(n). - Reinhard Zumkeller, Apr 04 2005
a(n) = 2 * A004526(n) + A004526(n+1). - Philippe Deléham, Aug 07 2006
a(n) = 1 + ceiling(3*(n-1)/2). - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006
Row sums of triangle A133083. - Gary W. Adamson, Sep 08 2007
a(n) = (cos(Pi*n) - 1)/4 + 3*n/2. - Bart Snapp (snapp(AT)coastal.edu), Sep 18 2008
A004396(a(n)) = n. - Reinhard Zumkeller, Oct 30 2009
a(n) = floor(n/2) + n. - Gary Detlefs, Mar 19 2010
a(n) = 3n - a(n-1) - 2, for n>0, a(0)=0. - Vincenzo Librandi, Nov 19 2010
a(n) = n + (n-1) - (n-2) + (n-3) - ... 1 = A052928(n) + A008619(n-1). - Jaroslav Krizek, Mar 22 2011
a(n) = a(n-1) + a(n-2) - a(n-3). - Robert G. Wilson v, Mar 28 2011
a(n) = Sum_{k>=0} A030308(n,k) * A003945(k). - Philippe Deléham, Oct 17 2011
a(n) = 2n - ceiling(n/2). - Wesley Ivan Hurt, Oct 25 2013
a(n) = A000217(n) - 2 * A002620(n-1). - Kival Ngaokrajang, Oct 26 2013
a(n) = Sum_{i=1..n} gcd(i, 2). - Wesley Ivan Hurt, Jan 23 2014
a(n) = 2n + floor((-n - (n mod 2))/2). - Wesley Ivan Hurt, Mar 31 2014
A092942(a(n)) = n for n > 0. - Reinhard Zumkeller, Dec 13 2014
a(n) = floor(3*n/2). - L. Edson Jeffery, Jan 18 2015
a(n) = A254049(A249745(n)) = (1+A007310(n)) / 2 for n >= 1. - Antti Karttunen, Jan 24 2015
E.g.f.: (3*x*exp(x) - sinh(x))/2. - Ilya Gutkovskiy, Jul 18 2016
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/(6*sqrt(3)) + log(3)/2. - Amiram Eldar, Dec 04 2021

Better description from N. J. A. Sloane, Aug 01 1998

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

cp's OEIS Frontend

A032766 Numbers that are congruent to 0 or 1 (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

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