A023359 -id:A023359 - cp's OEIS frontend

A036987 Fredholm-Rueppel sequence.

1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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, 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, 0

Offset: 0

N. J. A. Sloane

Binary representation of the Kempner-Mahler number Sum_{k>=0} 1/2^(2^k) = A007404.
Also a(n) = A(n) mod 2 where A is any of A001700, A005573, A007854, A026641, A049027, A064063, A064088, A064090, A064092, A064325, A064327, A064329, A064331, A064613, A076026, A105523, A123273, A126694, A126930, A126931, A126982, A126983, A126987, A127016, A127053, A127358, A127360, A127361, A127363. - Philippe Deléham, May 26 2007
a(n) = (product of digits of n; n in binary notation) mod 2. This sequence is a transformation of the Thue-Morse sequence (A010060), since there exists a function f such that f(sum of digits of n) = (product of digits of n). - Ctibor O. Zizka, Feb 12 2008
a(n-1), n >= 1, the characteristic sequence for powers of 2, A000079, is the unique solution of the following formal product and formal power series identity: Product_{j>=1} (1 + a(j-1)*x^j) = 1 + Sum_{k>=1} x^k = 1/(1-x). The product is therefore Product_{l>=1} (1 + x^(2^l)). Proof. Compare coefficients of x^n and use the binary representation of n. Uniqueness follows from the recurrence relation given for the general case under A147542. - Wolfdieter Lang, Mar 05 2009
a(n) is also the number of orbits of length n for the map x -> 1-cx^2 on [-1,1] at the Feigenbaum critical value c=1.401155... . - Thomas Ward, Apr 08 2009
A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511 = the inverse of Sierpiński's gasket * the ruler sequence. - Gary W. Adamson, Oct 26 2009 [Of course this is only vaguely correct depending on how the fuzzy indexing in these formulas is made concrete. - R. J. Mathar, Jun 20 2014]
Characteristic function of A000225. - Reinhard Zumkeller, Mar 06 2012
Also parity of the Catalan numbers A000108. - Omar E. Pol, Jan 17 2012
For n >= 2, also the largest exponent k >= 0 such that n^k in binary notation does not contain both 0 and 1. Unlike for the decimal version of this sequence, A062518, where the terms are only conjectural, for this sequence the values of a(n) can be proved to be the characteristic function of A000225, as follows: n^k will contain both 0 and 1 unless n^k = 2^r-1 for some r. But this is a special case of Catalan's equation x^p = y^q-1, which was proved by Preda Mihăilescu to have no nontrivial solution except 2^3 = 3^2 - 1. - Christopher J. Smyth, Aug 22 2014
Image, under the coding a,b -> 1; c -> 0, of the fixed point, starting with a, of the morphism a -> ab, b -> cb, c -> cc. - Jeffrey Shallit, May 14 2016
Number of nonisomorphic Boolean algebras of order n+1. - Jianing Song, Jan 23 2020

			G.f. = 1 + x + x^3 + x^7 + x^15 + x^31 + x^63 + x^127 + x^255 + x^511 + ...
a(7) = 1 since 7 = 2^3 - 1, while a(10) = 0 since 10 is not of the form 2^k - 1 for any integer k.

Antti Karttunen, Table of n, a(n) for n = 0..65537
D. Bailey et al., On the binary expansions of algebraic numbers, Journal de Théorie des Nombres de Bordeaux 16 (2004), 487-518.
Paul Barry, Some observations on the Rueppel sequence and associated Hankel determinants, arXiv:2005.04066 [math.CO], 2020.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Mats Granvik, Mathematica program for computing Fredholm Rueppel sequences
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions, in Sequences and their Applications, C. Ding, T. Helleseth, and H. Niederreiter, eds., Proceedings of SETA'98 (Singapore, 1998), 308-317, 1999.
Preda Mihăilescu, Primary Cyclotomic Units and a Proof of Catalan's Conjecture, J. Reine angew. Math. 572 (2004): 167-195. doi:10.1515/crll.2004.048. MR 2076124.
H. Niederreiter and M. Vielhaber, Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences, J. Complexity, 12 (1996), 187-198.
Apisit Pakapongpun and Thomas Ward, Functorial orbit counting, Journal of Integer Sequences, 12 (2009) Article 09.2.4. [From _Thomas Ward_, Apr 08 2009]
Eric Rowland and Reem Yassawi, Profinite automata, arXiv:1403.7659 [math.DS], 2014. See p. 8.
E. Sheppard, net.math post (1985)
Stephen Wolfram, [Page 1092] A New Kind of Science | Online.
Index entries for characteristic functions

Cf. A007404, A043545, A062518, A078885, A078585, A078886, A078887, A078888, A078889, A078890.
The first row of A073346. Occurs for first time in A073202 as row 6 (and again as row 8).
Congruent to any of the sequences A000108, A007460, A007461, A007463, A007464, A061922, A068068 reduced modulo 2. Characteristic function of A000225.
If interpreted with offset=1 instead of 0 (i.e., a(1)=1, a(2)=1, a(3)=0, a(4)=1, ...) then this is the characteristic function of 2^n (A000079) and as such occurs as the first row of A073265. Also, in that case the INVERT transform will produce A023359.
This is Guy Steele's sequence GS(1, 3), also GS(3, 1) (see A135416).
Cf. A054525, A047999. - Gary W. Adamson, Oct 26 2009
Cf. A043529, A127802.

a036987 n = ibp (n+1) where
   ibp 1 = 1
   ibp n = if r > 0 then 0 else ibp n' where (n',r) = divMod n 2
a036987_list = 1 : f [0,1] where f (x:y:xs) = y : f (x:xs ++ [x,x+y])
-- Same list generator function as for a091090_list, cf. A091090.
-- Reinhard Zumkeller, May 19 2015, Apr 13 2013, Mar 13 2013

A036987:= n-> `if`(2^ilog2(n+1) = n+1, 1, 0):
seq(A036987(n), n=0..128);

RealDigits[ N[ Sum[1/10^(2^n), {n, 0, Infinity}], 110]][[1]]
(* Recurrence: *)
t[n_, 1] = 1; t[1, k_] = 1;
t[n_, k_] := t[n, k] =
  If[n < k, If[n > 1 && k > 1, -Sum[t[k - i, n], {i, 1, n - 1}], 0],
   If[n > 1 && k > 1, Sum[t[n - i, k], {i, 1, k - 1}], 0]];
Table[t[n, k], {k, n, n}, {n, 104}]
(* Mats Granvik, Jun 03 2011 *)
mb2d[n_]:=1 - Module[{n2 = IntegerDigits[n, 2]}, Max[n2] - Min[n2]]; Array[mb2d, 120, 0] (* Vincenzo Librandi, Jul 19 2019 *)
Table[PadRight[{1},2^k,0],{k,0,7}]//Flatten (* Harvey P. Dale, Apr 23 2022 *)

{a(n) =( n++) == 2^valuation(n, 2)}; /* Michael Somos, Aug 25 2003 */

a(n) = !bitand(n, n+1); \\ Ruud H.G. van Tol, Apr 05 2023

from sympy import catalan
def a(n): return catalan(n)%2 # Indranil Ghosh, May 25 2017

def A036987(n): return int(not(n&(n+1))) # Chai Wah Wu, Jul 06 2022

1 followed by a string of 2^k - 1 0's. Also a(n)=1 iff n = 2^m - 1.
a(n) = a(floor(n/2)) * (n mod 2) for n>0 with a(0)=1. - Reinhard Zumkeller, Aug 02 2002 [Corrected by Mikhail Kurkov, Jul 16 2019]
Sum_{n>=0} 1/10^(2^n) = 0.110100010000000100000000000000010...
1 if n=0, floor(log_2(n+1)) - floor(log_2(n)) otherwise. G.f.: (1/x) * Sum_{k>=0} x^(2^k) = Sum_{k>=0} x^(2^k-1). - Ralf Stephan, Apr 28 2003
a(n) = 1 - A043545(n). - Michael Somos, Aug 25 2003
a(n) = -Sum_{d|n+1} mu(2*d). - Benoit Cloitre, Oct 24 2003
Dirichlet g.f. for right-shifted sequence: 2^(-s)/(1-2^(-s)).
a(n) = A000108(n) mod 2 = A001405(n) mod 2. - Paul Barry, Nov 22 2004
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{j=0..k} binomial(k, 2^j-1). - Paul Barry, Jun 01 2006
A000523(n+1) = Sum_{k=1..n} a(k). - Mitch Harris, Jul 22 2011
a(n) = A209229(n+1). - Reinhard Zumkeller, Mar 07 2012
a(n) = Sum_{k=1..n} A191898(n,k)*cos(Pi*(n-1)*(k-1))/n; (conjecture). - Mats Granvik, Mar 04 2013
a(n) = A000035(A000108(n)). - Omar E. Pol, Aug 06 2013
a(n) = 1 iff n=2^k-1 for some k, 0 otherwise. - M. F. Hasler, Jun 20 2014
a(n) = ceiling(log_2(n+2)) - ceiling(log_2(n+1)). - Gionata Neri, Sep 06 2015
From John M. Campbell, Jul 21 2016: (Start)
a(n) = (A000168(n-1) mod 2).
a(n) = (A000531(n+1) mod 2).
a(n) = (A000699(n+1) mod 2).
a(n) = (A000891(n) mod 2).
a(n) = (A000913(n-1) mod 2), for n>1.
a(n) = (A000917(n-1) mod 2), for n>0.
a(n) = (A001142(n) mod 2).
a(n) = (A001246(n) mod 2).
a(n) = (A001246(n) mod 4).
a(n) = (A002057(n-2) mod 2), for n>1.
a(n) = (A002430(n+1) mod 2). (End)
a(n) = 2 - A043529(n). - Antti Karttunen, Nov 19 2017
a(n) = floor(1+log(n+1)/log(2)) - floor(log(2n+1)/log(2)). - Adriano Caroli, Sep 22 2019
This is also the decimal expansion of -Sum_{k>=1} mu(2*k)/(10^k - 1), where mu is the Möbius function (A008683). - Amiram Eldar, Jul 12 2020

Edited by M. F. Hasler, Jun 20 2014

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

A073202 Array of fix-count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 3, 0, 1, 1, 2, 8, 1, 0, 1, 1, 0, 20, 0, 0, 0, 1, 1, 5, 60, 2, 0, 1, 0, 1, 1, 0, 181, 0, 0, 0, 0, 0, 1, 1, 14, 584, 5, 0, 2, 0, 1, 2, 1, 1, 0, 1916, 0, 0, 0, 0, 0, 5, 0, 1, 1, 42, 6476, 14, 0, 5, 0, 0, 14, 1, 2, 1, 1, 0, 22210, 0, 0, 0, 0, 0, 42, 0, 1, 0, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of elements fixed by the Catalan bijection (given in the corresponding row of A073200) when it acts on A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

A. Karttunen, Gatomorphisms (With the complete source and explanation)

Cf. also A073201, A073203.
Few EIS-sequences which occur in this table. Only the first known occurrence(s) given (marked with ? if not yet proved/unclear):
Rows 0, 2, 4, etc.: "Aerated Catalan numbers" shifted right and prepended with 1 (Cf. A000108), Row 1: A073190, Rows 3, 5, 261, 2614, 2618, 17517, etc: A019590 but with offset 0 instead of 1 (means that the Catalan bijections like A073269, A073270, A057501, A057505, A057503 and A057161 never fix any Catalan structure of size larger than 1).
Row 6: A036987, Row 7: A000108, Rows 12, 14, 20, ...: A057546, Rows 16, 18: A034731, Row 41: A073268, Row 105: essentially A073267, Row 57, ..., 164: A001405, Row 168: A073192, Row 416: essentially A023359 ?, Row 10435: also A036987.

A073267 Number of compositions (ordered partitions) of n into exactly two powers of 2.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 25 2002

nonn

Starting with 1 = self-convolution of A036987, the characteristic function of the powers of 2. [Gary W. Adamson, Feb 23 2010]

			For 2 there is only composition {1+1}, for 3 there is {1+2, 2+1}, for 4 {2+2}, for 5 {1+4, 4+1}, for 6 {2+4,4+2}, for 7 none, thus a(2)=1, a(3)=2, a(4)=1, a(5)=2, a(6)=2 and a(7)=0.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Sen-Peng Eu, Shu-Chung Liu and Yeong-Nan Yeh, Catalan and Motzkin numbers modulo 4 and 8, Eur. J. Combinat. 29 (2008) 1449-1466.

The second row of the table A073265. The essentially same sequence 1, 1, 2, 1, 2, 2, 0, 1, ... occurs for first time in A073202 as row 105 (the fix count sequence of A073290). The positions of 1's for n > 1 is given by the characteristic function of A000079, i.e. A036987 with offset 1 instead of 0 and the positions of 2's is given by A018900. Cf. also A023359.

Cf. A036987. [Gary W. Adamson, Feb 23 2010]

a073267 n = sum $ zipWith (*) a209229_list $ reverse $ take n a036987_list
-- Reinhard Zumkeller, Mar 07 2012

f:= proc(n) local d;
d:= convert(convert(n,base,2),`+`);
if d=2 then 2 elif d=1 then 1 else 0 fi
end proc:
0, 0, seq(f(n),n=2..100); # Robert Israel, Jul 07 2016

Table[Count[Map[{#, n - #} &, Range[0, n]], k_ /; Times @@ Boole@ Map[IntegerQ@ Log2@ # &, k] == 1], {n, 0, 88}] (* Michael De Vlieger, Jul 08 2016 *)

N=166; x='x+O('x^N);
v=Vec( 'a0 + sum(k=0,ceil(log(N)/log(2)), x^(2^k) )^2 );
v[1] -= 'a0;  v
/* Joerg Arndt, Oct 21 2012 */

def A073267(n): return m if n>1 and (m:=n.bit_count())<3 else 0 # Chai Wah Wu, Oct 30 2024

G.f.: (Sum_{k>=0} x^(2^k) )^2. - Vladeta Jovovic, Mar 28 2005
a(n+1) = A000108(n) mod 4, n>=1 [Theorem 2.3 of Eu et al.]. - R. J. Mathar, Feb 27 2008
a(n) = sum (A209229(k)*A036987(n-k): k = 0..n), convolution of characteristic functions of 2^n and 2^n-1. [Reinhard Zumkeller, Mar 07 2012]
a(n+2) = A000168(n) mod 4. - John M. Campbell, Jul 07 2016

A060945 Number of compositions (ordered partitions) of n into 1's, 2's and 4's.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 18, 31, 55, 96, 169, 296, 520, 912, 1601, 2809, 4930, 8651, 15182, 26642, 46754, 82047, 143983, 252672, 443409, 778128, 1365520, 2396320, 4205249, 7379697, 12950466, 22726483, 39882198, 69988378, 122821042, 215535903, 378239143, 663763424, 1164823609

Offset: 0

Len Smiley, May 07 2001

Diagonal sums of A038137. - Paul Barry, Oct 24 2005
From Gary W. Adamson, Oct 28 2010: (Start)
INVERT transform of the aerated Fibonacci sequence (1, 0, 1, 0, 2, 0, 3, 0, 5, ...).
a(n) = term (4,4) in the n-th power of the matrix [0,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,1,1]. (End)
Number of permutations satisfying -k <= p(i)-i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={2}. - Vladimir Baltic, Mar 07 2012
Number of compositions of n if the summand 2 is frozen in place or equivalently, if the ordering of the summand 2 does not count. - Gregory L. Simay, Jul 18 2016
a(n) - a(n-2) = number of compositions of n with no 2's = A005251(n+1). - Gregory L. Simay, Jul 18 2016
In general, the number of compositions of n with summand k frozen in place is equal to the number of compositions of n with only summands 1,...,k,2k. - Gregory L. Simay, May 10 2017
In the same way that the sum of any two alternating terms of A006498 produces a term from A000045 (the Fibonacci sequence), so it could be thought of as a "meta-Fibonacci," and the sum of any two alternating terms of A013979 produces a term from A000930 (Narayana’s cows), so it could analogously be called "meta-Narayana’s cows," this sequence embeds (can generate) A000931 (the Padovan sequence), as the odd terms of A000931 are generated by the sum of successive elements (e.g. 1+2=3, 2+3=5, 3+6=9, 6+10=16) and its even terms are generated by the difference of "supersuccessive" (second-order successive or "alternating," separated by a single other term) terms (e.g. 10-3=7, 18-6=12, 31-10=21, 55-18=37) — or, equivalently, adding "supersupersuccessive" terms (separated by 2 other terms, e.g. 1+6=7, 2+10=12, 3+18=21, 6+31=37) — so it could be dubbed the "metaPadovan." - Michael Cohen and Yasuyuki Kachi, Jun 13 2024

			There are 18=a(6) compositions of 6 with the summand 2 frozen in place: (6), (51), (15), (4[2]), (33), (411), (141), (114), (3[2]1), (1[2]3), ([222]), (3111), (1311), (1131), (1113), ([22]11), ([2]1111), (111111). Equivalently, the position of the summand 2 does not affect the composition count. For example, (321)=(231)=(312) and (123)=(213)=(132).

Harry J. Smith, Table of n, a(n) for n = 0..500
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135
Michael Cohen and Yasuyuki Kachi (2024). Recurrence Relations Rhythm. In: Noll, T., Montiel, M., Gómez, F., Hamido, O.C., Besada, J.L., Martins, J.O. (eds) Mathematics and Computation in Music. MCM 2024. Lecture Notes in Computer Science, vol. 14639. Springer, Cham.
K. Edwards, M. A. Allen, Strongly restricted permutations and tiling with fences, Disc. Appl. Math. 187 (2015) 82-90, Sect. 4.3
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1).

Cf. A000045 (1's and 2's only), A023359 (all powers of 2)
Same as unsigned version of A077930.
All of A060945, A077930, A181532 are variations of the same sequence. - N. J. A. Sloane, Mar 04 2012

a060945 n = a060945_list !! (n-1)
a060945_list = 1 : 1 : 2 : 3 : 6 : zipWith (+) a060945_list
   (zipWith (+) (drop 2 a060945_list) (drop 3 a060945_list))
-- Reinhard Zumkeller, Mar 23 2012

R:=PowerSeriesRing(Integers(), 40);
Coefficients(R!( 1/(1-x-x^2-x^4) )); // G. C. Greubel, Apr 09 2021

m:= 40; S:= series( 1/(1-x-x^2-x^4), x, m+1);
seq(coeff(S, x, j), j = 0..m); # G. C. Greubel, Apr 09 2021

LinearRecurrence[{1,1,0,1}, {1,1,2,3}, 39] (* or *)
CoefficientList[Series[1/(1-x-x^2-x^4), {x, 0, 38}], x] (* Michael De Vlieger, May 10 2017 *)

N=66; my(x='x+O('x^N));
Vec(1/(1-x-x^2-x^4))
/* Joerg Arndt, Oct 21 2012 */

def A060945_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-x-x^2-x^4) ).list()
A060945_list(40) # G. C. Greubel, Apr 09 2021

a(n) = a(n-1) + a(n-2) + a(n-4).
G.f.: 1 / (1 - x - x^2 - x^4).
a(n) = Sum_{k=0..floor(n/2)} Sum_{i=0..n-k} C(i, n-k-i)*C(2*i-n+k, 3*k-2*n+2*i). - Paul Barry, Oct 24 2005
a(2n) = A238236(n), a(2n+1) = A097472(n). - Philippe Deléham, Feb 20 2014
a(n) + a(n+1) = A005314(n+2). - R. J. Mathar, Jun 17 2020

a(0) = 1 prepended by Joerg Arndt, Oct 21 2012

cp's OEIS Frontend

A084356 A000055(n+2)-A023359(n).

Views

Author

Keywords

Crossrefs

A036987 Fredholm-Rueppel sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

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

A073202 Array of fix-count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A073267 Number of compositions (ordered partitions) of n into exactly two powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A060945 Number of compositions (ordered partitions) of n into 1's, 2's and 4's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica