login
Number of Fibonacci numbers 1,2,3,5,... dividing n.
23

%I #49 Dec 31 2023 06:23:02

%S 1,2,2,2,2,3,1,3,2,3,1,3,2,2,3,3,1,3,1,3,3,2,1,4,2,3,2,2,1,4,1,3,2,3,

%T 2,3,1,2,3,4,1,4,1,2,3,2,1,4,1,3,2,3,1,3,3,3,2,2,1,4,1,2,3,3,3,3,1,3,

%U 2,3,1,4,1,2,3,2,1,4,1,4,2,2,1,4,2,2,2,3,2,4,2,2,2,2,2,4,1,2,2,3,1,4,1,4,4

%N Number of Fibonacci numbers 1,2,3,5,... dividing n.

%C Indices of records are in A129655. - _R. J. Mathar_, Nov 02 2007

%H Charles R Greathouse IV, <a href="/A005086/b005086.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) <= A072649(n). - _Robert G. Wilson v_, Dec 10 2006

%F Equals A051731 * A010056. - _Gary W. Adamson_, Nov 06 2007

%F G.f.: Sum_{n>=2} x^F(n)/(1-x^F(n)) where F(n) = A000045(n). - _Joerg Arndt_, Jan 06 2015

%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = A079586 - 1 = 2.359885... . - _Amiram Eldar_, Dec 31 2023

%p with(combinat): for n from 1 to 200 do printf(`%d,`,sum(floor(n/fibonacci(k))-floor((n-1)/fibonacci(k)), k=2..15)) od:

%t f[n_] := Block[{k = 1}, While[Fibonacci[k] <= n, k++ ]; Count[ Mod[n, Array[ Fibonacci, k - 1]], 0] - 1]; Array[f, 105] (* _Robert G. Wilson v_, Dec 10 2006 *)

%o (PARI) isfib(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))

%o a(n)=sumdiv(n,d,isfib(d)) \\ _Charles R Greathouse IV_, Nov 06 2014

%o (Python)

%o from sympy import divisors

%o from sympy.ntheory.primetest import is_square

%o def A005086(n): return sum(1 for d in divisors(n,generator=True) if is_square(m:=5*d**2-4) or is_square(m+8)) # _Chai Wah Wu_, Mar 30 2023

%o (Python)

%o from itertools import count, takewhile

%o def F(f=1, g=1):

%o while True:

%o f, g = g, f+g;

%o yield f

%o def a(n):

%o return sum(1 for f in takewhile(lambda x: x<=n, F()) if n%f == 0)

%o print([a(n) for n in range(1, 106)]) # _Michael S. Branicky_, Apr 03 2023

%Y Cf. A000045, A038663, A051731, A010056, A072649, A079586, A129655.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Feb 19 2001

%E Incorrect comment removed by _Charles R Greathouse IV_, Nov 06 2014