|
|
A007895
|
|
Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).
|
|
139
|
|
|
0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - Wolfdieter Lang, Jan 21 2008; N. J. A. Sloane, Jun 28 2008
Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - Wolfdieter Lang, Jan 21 2008
Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
A000120 gives the equivalent for (all) compositions. (End)
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m. See Lemma 2.1 of the Stoll link. - Robert Israel, Apr 17 2015
This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
tau((j,0)) = (j,0) (j+1,1),
tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
|tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
a(F(n+1)+i) = a(i) + 1.
From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet: (j,0)-> 2j (j,1)-> 2j+1, which yields the morphism
tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)
|
|
REFERENCES
|
Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
F. Weinstein, The Fibonacci Partitions, preprint, 1995.
Édouard Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.
|
|
LINKS
|
Paul Baird-Smith, Alyssa Epstein, Kristen Flint, and Steven J. Miller, The Zeckendorf Game, arXiv:1809.04881 [math.NT], 2018.
|
|
FORMULA
|
|
|
EXAMPLE
|
a(46) = a(1 + 3 + 8 + 34) = 4.
Connection to the compositions of n into odd parts (see comment):
[ #]: a(n) composition into odd parts
[ 0] [ 0] 1 1 1 1 1 1 1 1
[1] [1] 1 1 1 1 1 3
[2] [1] 1 1 1 1 3 1
[3] [1] 1 1 1 3 1 1
[4] [2] 1 1 1 5
[5] [1] 1 1 3 1 1 1
[6] [2] 1 1 3 3
[7] [2] 1 1 5 1
[8] [1] 1 3 1 1 1 1
[9] [2] 1 3 1 3
[10] [2] 1 3 3 1
[11] [2] 1 5 1 1
[12] [3] 1 7
[13] [1] 3 1 1 1 1 1
[14] [2] 3 1 1 3
[15] [2] 3 1 3 1
[16] [2] 3 3 1 1
[17] [3] 3 5
[18] [2] 5 1 1 1
[19] [3] 5 3
[20] [3] 7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]: a(n) composition into parts 1 and 2
[ 0] [0] 1 1 1 1 1 1 1
[1] [1] 1 1 1 1 1 2
[2] [1] 1 1 1 1 2 1
[3] [1] 1 1 1 2 1 1
[4] [2] 1 1 1 2 2
[5] [1] 1 1 2 1 1 1
[6] [2] 1 1 2 1 2
[7] [2] 1 1 2 2 1
[8] [1] 1 2 1 1 1 1
[9] [2] 1 2 1 1 2
[10] [2] 1 2 1 2 1
[11] [2] 1 2 2 1 1
[12] [3] 1 2 2 2
[13] [1] 2 1 1 1 1 1
[14] [2] 2 1 1 1 2
[15] [2] 2 1 1 2 1
[16] [2] 2 1 2 1 1
[17] [3] 2 1 2 2
[18] [2] 2 2 1 1 1
[19] [3] 2 2 1 2
[20] [3] 2 2 2 1
(End)
The third iterate of the morphism tau generating this sequence:
tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)
|
|
MAPLE
|
# With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n.
with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0; m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: 0, seq(B(n), n = 1 .. 104);
N:= 1000: # to get a(n) for n <= N
m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)):
Z:= Vector(m):
a[0]:= 0:
for n from 1 to N do
if Z[1] = 0 then Z[1]:= 1; q:= 1;
else Z[2]:= 1; Z[1]:= 0; q:= 2;
fi;
while Z[q+1] = 1 do
Z[q]:= 0;
Z[q+1]:= 0;
Z[q+2]:= 1;
q:= q+2;
od:
a[n]:= add(Z[i], i=1..m);
od:
# alternative
read("transforms") :
end proc:
|
|
MATHEMATICA
|
zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *)
Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* Alonso del Arte, May 14 2019 *)
Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *)
|
|
PROG
|
(PARI) a(n, mx=0)=if(n<4, n>0, if(!mx, while(fibonacci(mx)<n, mx++)); while(fibonacci(mx)>n, mx--); 1+a(n-fibonacci(mx), mx-2)) \\ Charles R Greathouse IV, Feb 14 2013
(PARI) a(n)=if(n<4, n>0, my(k=2, s, t); while(fibonacci(k++)<=n, ); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ Charles R Greathouse IV, Sep 02 2015
(Haskell)
(Python)
from sympy import fibonacci
def a(n):
k=0
x=0
while n>0:
k=0
while fibonacci(k)<=n: k+=1
x+=10**(k - 3)
n-=fibonacci(k - 1)
return str(x).count("1")
|
|
CROSSREFS
|
Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|