A072649 n occurs Fibonacci(n) times (cf. A000045).

1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 1

Author

Antti Karttunen, Jun 02 2002

Keywords

• nonn
• look

Comments

Number of digits in Zeckendorf-binary representation of n. E.g., the Zeckendorf representation of 12 is 8+3+1, which in binary notation is 10101, which consists of 5 digits. - Clark Kimberling, Jun 05 2004

First position where value n occurs is A000045(n+1), i.e., a(A000045(n)) = n-1, for n >= 2 and a(A000045(n)-1) = n-2, for n >= 3.

This is the number of distinct Fibonacci numbers greater than 0 which are less than or equal to n. - Robert G. Wilson v, Dec 10 2006

The smallest nondecreasing sequence a(n) such that a(Fibonacci(n-1)) = n. - Tanya Khovanova, Jun 20 2007

Examples

			1, 1, then F(2) 2's, then F(3) 3's, then F(4) 4's, ..., then F(k) k's, ...
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See page 4.
• Popular Computing (Calabasas, CA), A Coding Exercise (from a suggestion by R. W. Hamming), Vol. 5 (No. 54, Sep 1977), p. PC55-18.

Crossrefs

Cf. A000045, A095791, A095792.

Cf. A001622 (golden ratio phi), A073010.

Used to construct A003714. Cf. also A002024, A072643, A072648, A072650.

Cf. A131234.

Partial sums: A256966, A256967.

Programs

Haskell

a072649 n = a072649_list !! (n-1)
a072649_list = f 1 where
   f n = (replicate (fromInteger $ a000045 n) n) ++ f (n+1)
-- Reinhard Zumkeller, Jul 04 2011

Maple

A072649 := proc(n)
    local j;
    for j from ilog[(1+sqrt(5))/2](n) while combinat[fibonacci](j+1)<=n do
    end do;
    j-1
end proc:
seq(A072649(n), n=1..120);  # Alois P. Heinz, Mar 18 2013

Mathematica

Table[Table[n, {Fibonacci[n]}], {n, 10}] // Flatten (* Robert G. Wilson v, Jan 14 2007 *)
a[n_] := Module[{j}, For[j = Floor@Log[GoldenRatio, n], Fibonacci[j+1] <= n, j++]; j-1];
Table[a[n], {n, 1, 120}] (* Jean-François Alcover, Nov 17 2022, after Alois P. Heinz *)

PARI

a(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2))

PARI

a(n)=local(m); if(n<1,0,m=0; until(fibonacci(m)>n,m++); m-2)

Python

from sympy import fibonacci
def a(n):
    if n<1: return 0
    m=0
    while fibonacci(m)<=n: m+=1
    return m-2
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 09 2017

Python

def A072649(n):
    a, b, c = 0, 1, -2
    while a <= n:
        a, b = b, a+b
        c += 1
    return c # Chai Wah Wu, Nov 04 2024
(MIT/GNU Scheme) (define (A072649 n) (let ((b (A072648 n))) (+ -1 b (floor->exact (/ n (A000045 (1+ b))))))) ;; (The implementation below is better)

Scheme

(define (A072649 n) (if (<= n 3) n (let loop ((k 5)) (if (> (A000045 k) n) (- k 2) (loop (+ 1 k)))))) ;; (Use this with the memoized implementation of A000045 given under that entry. No floating point arithmetic is involved). - Antti Karttunen, Oct 06 2017

Formula

G.f.: (Sum_{n>1} x^Fibonacci(n))/(1-x). - Michael Somos, Apr 25 2003

From Hieronymus Fischer, May 02 2007: (Start)

a(n) = floor(log_phi((sqrt(5)*n + sqrt(5*n^2+4))/2)) - 1, where phi is A001622.

a(n) = floor(arcsinh(sqrt(5)*n/2)/log(phi)) - 1.

a(n) = A108852(n) - 2. (End)

a(n) = -1 + floor( log_phi( (n+0.2)*sqrt(5) ) ), where log_phi(x) is the logarithm to the base (1+sqrt(5))/2. - Ralf Stephan, May 14 2007

Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/(3*sqrt(3)) (A073010). - Amiram Eldar, Feb 18 2024

Extensions

Typo fixed by Charles R Greathouse IV, Oct 28 2009