A112310 Number of terms in lazy Fibonacci representation of n.

0, 1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 3, 3, 4, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5, 5, 6, 4, 4, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 7, 4, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 7, 5, 5, 6, 5, 6, 6, 6, 7, 5, 6, 6, 6, 7, 6, 6, 7, 6, 7, 7, 7, 8, 5, 5, 6, 5, 6, 6, 6, 7, 5, 6, 6, 6, 7, 6, 6, 7, 6

Offset: 0

Author

N. J. A. Sloane, Dec 01 2005

Keywords

• nonn
• easy
• changed

Comments

Equivalently, the number of ones in the maximal Fibonacci bit-representation (A104326) of n.

Conjecture: if we split the sequence in groups that contain Fibonacci(k) terms like (0), (1), (1, 2), (2, 2, 3), (2, 3, 3, 3, 4), (3, 3, 4, 3, 4, 4, 4, 5) etc, the sums in the groups are the terms of A023610. - Gary W. Adamson, Nov 02 2010

Equivalently, the number of periods in the length-n prefix of the infinite Fibonacci word (A003849). An integer p, 1 <= p <= n, is a period of a length-n word x if x[i] = x[i+p] for 1 <= i <= n-p. - Jeffrey Shallit, May 23 2020

Examples

			a(10) = 3 because A104326(10) = 1110 contains three ones.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• J. L. Brown, Jr., A new characterization of the Fibonacci numbers, Fibonacci Quarterly 3, No. 1 (1965), 1-8.
• Ron Knott, Using the Fibonacci numbers to represent whole numbers.
• Wolfgang Steiner, The joint distribution of greedy and lazy Fibonacci expansions, Fib. Q., 43 (No. 1, 2005), 60-69.

Crossrefs

Number of terms in row n of A112309.

Cf. A003849, A035517, A007895, A007953, A104326, A117479.

Record positions are in A001911. - Ray Chandler, Dec 01 2005

Programs

Haskell

a112310 n = a112310_list !! n
a112310_list = concat fss where
   fss = [0] : [1] : (map (map (+ 1))) (zipWith (++) fss $ tail fss)
-- Reinhard Zumkeller, Oct 26 2013

Maple

A112310 := proc(n)
    convert(A104326(n),base,10) ;
    add(d,d=%) ;
end proc:
seq(A112310(n),n=0..120) ; # R. J. Mathar, Aug 28 2025

Mathematica

DeleteCases[IntegerDigits[Range[200], 2], {_, 0, 0, _}]
A112309 = Map[DeleteCases[Reverse[#] Fibonacci[Range[Length[#]] + 1], 0] &, DeleteCases[IntegerDigits[-1 + Range[200], 2], {_, 0, 0, _}]]
A112310 = Map[Length, A112309]
(* Peter J. C. Moses, Mar 03 2015 *)

Formula

a(n) = A007953(A104326(n)). - Amiram Eldar, Oct 10 2023

Extensions

Extended by Ray Chandler, Dec 01 2005

Merged with a sequence from Casey Mongoven, Mar 20 2006, by Franklin T. Adams-Watters, Dec 19 2006