A054495 Smallest k such that n/k is a Fibonacci number.

1, 1, 1, 2, 1, 2, 7, 1, 3, 2, 11, 4, 1, 7, 3, 2, 17, 6, 19, 4, 1, 11, 23, 3, 5, 2, 9, 14, 29, 6, 31, 4, 11, 1, 7, 12, 37, 19, 3, 5, 41, 2, 43, 22, 9, 23, 47, 6, 49, 10, 17, 4, 53, 18, 1, 7, 19, 29, 59, 12, 61, 31, 3, 8, 5, 22, 67, 2, 23, 14, 71, 9, 73, 37, 15, 38, 77, 6, 79, 10, 27, 41

Offset: 1

Author

Henry Bottomley, Apr 04 2000

Keywords

• easy
• nonn

Examples

			a(10)=2 because 10/1=10 is not a Fibonacci number but 10/2=5 is.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000045, A010056, A005086, A037943.

Programs

PARI

A010056(n)=my(k=n^2); k+=(k+1)<<2; issquare(k) || (n>0 && issquare(k-8))
a(n)=fordiv(n,d,if(A010056(n/d), return(d))) \\ Charles R Greathouse IV, Nov 05 2014

Python

from sympy import divisors
from sympy.ntheory.primetest import is_square
def A054495(n): return next(d for d in divisors(n) if is_square(m:=5*(n//d)**2-4) or is_square(m+8)) # Chai Wah Wu, May 06 2024

Formula

a(n) = n/A054494(n). [Corrected by Charles R Greathouse IV, Nov 05 2014]

Extensions

a(34), a(55), a(68) corrected by Charles R Greathouse IV, Nov 06 2014