login
Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....
56

%I #113 Sep 16 2021 02:41:14

%S 1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,

%T 1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,

%U 0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1,0,1

%N Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....

%C Differences of the Meta-Fibonacci sequence for s=0. - _Frank Ruskey_ and Chris Deugau (deugaucj(AT)uvic.ca)

%C Fixed point of morphism 0-->0, 1-->110 - _Joerg Arndt_, Jun 07 2007

%C A006697(k) gives number of distinct subwords of length k, conjectured to be equal to A094913(k)+1. - _M. F. Hasler_, Dec 19 2007

%C Characteristic function for the range of A005187: a(A055938(n))=0; a(A005187(n))=1; if a(m)=1 then either a(m-1)=1 or a(m+1)=1. - _Reinhard Zumkeller_, Mar 18 2009

%C The number of zeros between successive pairs of ones in this sequence is A007814. - _Franklin T. Adams-Watters_, Oct 05 2011

%C Length of n-th run = abs(A088705) + 1. - _Reinhard Zumkeller_, Dec 11 2011

%H Reinhard Zumkeller, <a href="/A079559/b079559.txt">Table of n, a(n) for n = 0..1000</a>

%H Gary W. Adamson, <a href="/A079559/a079559.txt">Comments on A079559</a>

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 1.26.5, Recursive generation and relation to a power series, page 74, figure 1.26-E and function A.

%H Benoit Cloitre, <a href="/A079559/a079559.png">Fractal walk generated by the 130000 first terms (step of unit length moving to right if 0 left if 1) starting at (0,0)</a>

%H C. Deugau and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/GenMetaFib.html">Complete k-ary Trees and Generalized Meta-Fibonacci Sequences</a>

%H B. Jackson and F. Ruskey, <a href="https://doi.org/10.37236/1052">Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes</a>, Electronic Journal of Combinatorics, 13 (2006), R26.[<a href="http://www.cs.uvic.ca/~ruskey/Publications/MetaFib/MetaFib.html">alt source</a>]

%H Thomas M. Lewis and Fabian Salinas, <a href="https://arxiv.org/abs/2109.07328">Optimal pebbling of complete binary trees and a meta-Fibonacci sequence</a>, arXiv:2109.07328 [math.CO], 2021.

%H F. Ruskey and C. Deugau, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.html">The Combinatorics of Certain k-ary Meta-Fibonacci Sequences</a>, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%F G.f.: Product_{n>=1} (1 + x^(2^n-1)).

%F a(n) = 1 if n=0, otherwise A043545(n+1)*a(n+1-A053644(n+1)). - _Reinhard Zumkeller_, Aug 19 2006

%F a(n) = p(n,1) with p(n,k) = p(n-k,2*k+1) + p(n,2*k+1) if k <= n, otherwise 0^n. - _Reinhard Zumkeller_, Mar 18 2009

%F Euler transform is sequence A111113 sequence offset -1. - _Michael Somos_, Aug 03 2009

%F G.f.: Product_{k>0} (1 - x^k)^-A111113(k+1). - _Michael Somos_, Aug 03 2009

%F a(n) = A108918(n+1) mod 2. - _Joerg Arndt_, Apr 06 2011

%F a(n) = A000035(A153000(n)), n >= 1. - _Omar E. Pol_, Nov 29 2009, Aug 06 2013

%e a(11)=1 because we have [7,3,1].

%e G.f. = 1 + x + x^3 + x^4 + x^7 + x^8 + x^10 + x^11 + x^15 + x^16 + x^18 + ...

%e From _Omar E. Pol_, Nov 30 2009: (Start)

%e The sequence, displayed as irregular triangle, in which rows length are powers of 2, begins:

%e 1;

%e 1,0;

%e 1,1,0,0;

%e 1,1,0,1,1,0,0,0;

%e 1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0;

%e 1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0;

%e 1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0;

%e (End)

%p g:=product(1+x^(2^n-1),n=1..15): gser:=series(g,x=0,110): seq(coeff(gser,x,n),n=0..104); # _Emeric Deutsch_, Apr 06 2006

%p d := n -> if n=1 then 1 else A046699(n)-A046699(n-1) fi; # _Frank Ruskey_ and Chris Deugau (deugaucj(AT)uvic.ca)

%t row[1] = {1}; row[2] = {1, 0}; row[n_] := row[n] = row[n-1] /. 1 -> Sequence[1, 1, 0]; Table[row[n], {n, 1, 7}] // Flatten (* _Jean-François Alcover_, Jul 30 2012, after _Omar E. Pol_ *)

%t CoefficientList[ Series[ Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 104}], x] (* or *)

%t Nest[ Flatten[# /. {0 -> {0}, 1 -> {1, 1, 0}}] &, {1}, 6] (* _Robert G. Wilson v_, Sep 08 2014 *)

%o (PARI) w="1,";for(i=1,5,print1(w=concat([w,w,"0,"])))

%o (PARI) A079559(n,w=[1])=until(n<#w=concat([w,w,[0]]),);w[n+1] \\ _M. F. Hasler_, Dec 19 2007

%o (PARI) {a(n) = if( n<0, 0, polcoeff( prod(k=1, #binary(n+1), 1 + x^(2^k-1), 1 + x * O(x^n)), n))} /* _Michael Somos_, Aug 03 2009 */

%o (Haskell)

%o a079559 = p $ tail a000225_list where

%o p _ 0 = 1

%o p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Dec 11 2011

%o (Haskell)

%o a079559_list = 1 : f [1] where

%o f xs = ys ++ f ys where ys = init xs ++ [1] ++ tail xs ++ [0]

%o -- _Reinhard Zumkeller_, May 05 2015

%o (Python)

%o def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1)

%o def a043545(n):

%o x=bin(n)[2:]

%o return int(max(x)) - int(min(x))

%o l=[1]

%o for n in range(1, 101): l+=[a043545(n + 1)*l[n + 1 - a053644(n + 1)], ]

%o print(l) # _Indranil Ghosh_, Jun 11 2017

%Y Cf. A000929, A001511, A005187, A006697, A007814, A046699, A055938, A094913, A163988.

%Y Cf. A035263, A066519.

%K nonn,nice

%O 0,1

%A _Vladeta Jovovic_, Jan 25 2003

%E Edited by _M. F. Hasler_, Jan 03 2008