A079559 Number of partitions of n into distinct parts of the form 2^j-1, j=1,2,....
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, 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
Offset: 0
Examples
a(11)=1 because we have [7,3,1]. G.f. = 1 + x + x^3 + x^4 + x^7 + x^8 + x^10 + x^11 + x^15 + x^16 + x^18 + ... From _Omar E. Pol_, Nov 30 2009: (Start) The sequence, displayed as irregular triangle, in which rows length are powers of 2, begins: 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; 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; (End)
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
- Gary W. Adamson, Comments on A079559
- Joerg Arndt, Matters Computational (The Fxtbook), section 1.26.5, Recursive generation and relation to a power series, page 74, figure 1.26-E and function A.
- Benoit Cloitre, Fractal walk generated by the 130000 first terms (step of unit length moving to right if 0 left if 1) starting at (0,0)
- C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
- B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.[alt source]
- Thomas M. Lewis and Fabian Salinas, Optimal pebbling of complete binary trees and a meta-Fibonacci sequence, arXiv:2109.07328 [math.CO], 2021.
- F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3. [This is a later version than that in the GenMetaFib.html link]
- Index entries for characteristic functions
Crossrefs
Programs
-
Haskell
a079559 = p $ tail a000225_list where p _ 0 = 1 p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m -- Reinhard Zumkeller, Dec 11 2011
-
Haskell
a079559_list = 1 : f [1] where f xs = ys ++ f ys where ys = init xs ++ [1] ++ tail xs ++ [0] -- Reinhard Zumkeller, May 05 2015
-
Maple
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 d := n -> if n=1 then 1 else A046699(n)-A046699(n-1) fi; # Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
-
Mathematica
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 *) CoefficientList[ Series[ Product[1 + x^(2^n - 1), {n, 6}], {x, 0, 104}], x] (* or *) Nest[ Flatten[# /. {0 -> {0}, 1 -> {1, 1, 0}}] &, {1}, 6] (* Robert G. Wilson v, Sep 08 2014 *) -
PARI
w="1,";for(i=1,5,print1(w=concat([w,w,"0,"])))
-
PARI
A079559(n,w=[1])=until(n<#w=concat([w,w,[0]]),);w[n+1] \\ M. F. Hasler, Dec 19 2007
-
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 */ -
Python
def a053644(n): return 0 if n==0 else 2**(len(bin(n)[2:]) - 1) def a043545(n): x=bin(n)[2:] return int(max(x)) - int(min(x)) l=[1] for n in range(1, 101): l+=[a043545(n + 1)*l[n + 1 - a053644(n + 1)], ] print(l) # Indranil Ghosh, Jun 11 2017
Formula
G.f.: Product_{n>=1} (1 + x^(2^n-1)).
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
Euler transform is sequence A111113 sequence offset -1. - Michael Somos, Aug 03 2009
G.f.: Product_{k>0} (1 - x^k)^-A111113(k+1). - Michael Somos, Aug 03 2009
a(n) = A108918(n+1) mod 2. - Joerg Arndt, Apr 06 2011
Extensions
Edited by M. F. Hasler, Jan 03 2008
Comments