OFFSET
1,2
COMMENTS
In the formula, the relation a(p^e) = p^(e-1)*a(p) is called Wall's conjecture, which has been verified for primes up to 10^14. See A060305. Primes for which this relation fails are called Wall-Sun-Sun primes. - T. D. Noe, Mar 03 2009
All solutions to F_m == 0 (mod n) are given by m == 0 (mod a(n)). For a proof see, e.g., Vajda, p. 73. [Old comment changed by Wolfdieter Lang, Jan 19 2015]
If p is a prime of the form 10n +- 1 then a(p) is a divisor of p-1. If q is a prime of the form 10n +- 3 then a(q) is a divisor of q+1. - Robert G. Wilson v, Jul 07 2007
Definition 1 in Riasat (2011) calls this k(n), or sometimes just k. Corollary 1 in the same paper, "every positive integer divides infinitely many Fibonacci numbers," demonstrates that this sequence is infinite. - Alonso del Arte, Jul 27 2013
If p is a prime then a(p) <= p+1. This is because if p is a prime then exactly one of the following Fibonacci numbers is a multiple of p: F(p-1), F(p) or F(p+1). - Dmitry Kamenetsky, Jul 23 2015
From Renault 1996:
1. a(lcm(n,m)) = lcm(a(n), a(m)).
2. if n|m then a(n)|a(m).
3. if m has prime factorization m=p1^e1 * p2^e2 * ... * pn^en then a(m) = lcm(a(p1^e1), a(p2^e2), ..., a(pn^en)). - Dmitry Kamenetsky, Jul 23 2015
a(n)=n if and only if n=5^k or n=12*5^k for some k >= 0 (see Marques 2012). - Dmitry Kamenetsky, Aug 08 2015
Every positive integer (except 2) eventually appears in this sequence. This is because every Fibonacci number bigger than 1 (except Fibonacci(6)=8 and Fibonacci(12)=144) has at least one prime factor that is not a factor of any earlier Fibonacci number (see Knott reference). Let f(n) be such a prime factor for Fibonacci(n); then a(f(n))=n. - Dmitry Kamenetsky, Aug 08 2015
We can reconstruct the Fibonacci numbers from this sequence using the formula Fibonacci(n+2) = 1 + Sum_{i: a(i) <= n} phi(i)*floor(n/a(i)), where phi(n) is Euler's totient function A000010 (see the Stroinski link). For example F(6) = 1 + phi(1)*floor(4/a(1)) + phi(2)*floor(4/a(2)) + phi(3)*floor(4/a(4)) = 1 + 1*4 + 1*1 + 2*1 = 8. - Peter Bala, Sep 10 2015
Conjecture: Sum_{d|n} phi(d)*a(d) = A232656(n). - Logan J. Kleinwaks, Oct 28 2017
a(F_m) = m for all m > 1. Indeed, let (b(j)) be defined by b(1)=b(2)=1, and b(j+2) = (b(j) + b(j+1)) mod n. Then a(n) equals the index of the first occurrence of 0 in (b(j)). Example: if n=4 then b = A079343 = 1,1,2,3,1,0,1,1,..., so a(4)=6. If n is a Fibonacci number n=F_m, then obviously a(n)=m. Note that this gives a simple proof of the fact that all integers larger than 2 occur in (a(n)). - Michel Dekking, Nov 10 2017
REFERENCES
A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.
B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers. Report ORNL-4261, Oak Ridge National Laboratory, Oak Ridge, Tennessee, June 1968.
Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Afterword by Herbert A. Hauptman, Nobel Laureate, 2. 'The Minor Modulus m(n)', Prometheus Books, NY, 2007, page 329-342.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
N. N. Vorob'ev, Fibonacci numbers, Blaisdell, NY, 1961.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
A. Allard and P. Lecomte, Periods and entry points in Fibonacci sequence, Fib. Quart. 17 (1) (1979) 51-57.
R. C. Archibald (?), Review of B. H. Hannon and W. L. Morris, Tables of arithmetical functions related to the Fibonacci numbers, Math. Comp., 23 (1969), 459-460.
B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 25.
J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.
Molly FitzGibbons, Steven J. Miller, and Amanda Verga, Dynamics of the Fibonacci Order of Appearance Map, arXiv:2309.14501 [math.NT], 2023.
Ramon Glez-Regueral, An entry-point algorithm for high-speed factorization, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.
B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers [Annotated and scanned copy]
Ron Knott, The first 300 Fibonacci numbers factorized
Paolo Leonetti and Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017. See z(n).
Diego Marques, Fixed points of the order of appearance in the Fibonacci sequence, Fibonacci Quart. 50:4 (2012), pp. 346-352.
Diego Marques, The order of appearance of the product of consecutive Lucas numbers, Fibonacci Quarterly, 51 (2013), 38-43.
Diego Marques, Sharper upper bounds for the order of appearance in the fibonacci sequence, Fibonacci Quarterly, 51 (2013), pp. 233-238.
Zuzana Masáková and Edita Pelantová, Midy's Theorem in non-integer bases and divisibility of Fibonacci numbers, arXiv:2401.03874 [math.NT], 2024. See page 9.
Renault, The Fibonacci sequence under various moduli, Masters Thesis, Wake Forest University, 1996.
Samin Riasat, Z[phi] and the Fibonacci Sequence Modulo n, Mathematical Reflections 1 (2011): 1 - 7.
H. J. A. Salle, Maximum value for the rank of apparition of integers in recursive sequences, Fibonacci Quart. 13.2 (1975) 159-161.
U. Stroinski, Connection between Euler's totient function and Fibonacci numbers, Mathematics Stack Exchange, Feb 17 2015.
D. D. Wall, Fibonacci series modulo m, Am. Math. Monthly 67 (6) (1960) 525-532.
Eric Weisstein, MathWorld: Wall-Sun-Sun Prime
FORMULA
a(n) = n if and only if n is of form 5^k or 12*5^k (proved in Marques paper), a(n) = n - 1 if and only if n is in A106535, a(n) = n + 1 if and only if n is in A000057, a(n) = n + 5 if and only if n is in 5*A000057, ... - Benoit Cloitre, Feb 10 2007
a(1) = 1, a(2) = 3, a(4) = 6 and for e > 2, a(2^e) = 3*2^(e-2); a(5^e) = 5^e; and if p is an odd prime not 5, then a(p^e) = p^max(0, e-s)*a(p) where s = valuation(A000045(a(p)), p) (Wall's conjecture states that s = 1 for all p). If (m, n) = 1 then a(m*n) = lcm(a(m), a(n)). See Posamentier & Lahmann. - Robert G. Wilson v, Jul 07 2007; corrected by Max Alekseyev, Oct 19 2007, Jun 24 2011
a(n) < n^2. [Vorob'ev]. - Zak Seidov, Jan 07 2016
a(n) < n^2 - 3n + 6. - Jinyuan Wang, Oct 13 2018
a(n) <= 2n [Salle]. - Jon Maiga, Apr 25 2019
EXAMPLE
a(4) = 6 because the smallest Fibonacci number that 4 divides is F(6) = 8.
a(5) = 5 because the smallest Fibonacci number that 5 divides is F(5) = 5.
a(6) = 12 because the smallest Fibonacci number that 6 divides is F(12) = 144.
From Wolfdieter Lang, Jan 19 2015: (Start)
a(2) = 3, hence 2 | F(m) iff m = 2*k, for k >= 0;
a(3) = 4, hence 3 | F(m) iff m = 4*k, for k >= 0;
etc. See a comment above with the Vajda reference.
(End)
MAPLE
A001177 := proc(n)
for k from 1 do
if combinat[fibonacci](k) mod n = 0 then
return k;
end if;
end do:
end proc: # R. J. Mathar, Jul 09 2012
N:= 1000: # to get a(1) to a(N)
L:= ilcm($1..N):
count:= 0:
for n from 1 while count < N do
fn:= igcd(L, combinat:-fibonacci(n));
divs:= select(`<=`, numtheory:-divisors(fn), N);
for d in divs do if not assigned(A[d]) then count:= count+1; A[d]:= n fi od:
od:
seq(A[n], n=1..N); # Robert Israel, Oct 14 2015
MATHEMATICA
fibEntry[n_] := Block[{k = 1}, While[ Mod[ Fibonacci@k, n] != 0, k++ ]; k]; Array[fibEntry, 74] (* Robert G. Wilson v, Jul 04 2007 *)
PROG
(PARI) a(n)=if(n<0, 0, s=1; while(fibonacci(s)%n>0, s++); s) \\ Benoit Cloitre, Feb 10 2007
(PARI) ap(p)=my(k=p+[0, -1, 1, 1, -1][p%5+1], f=factor(k)); for(i=1, #f[, 1], for(j=1, f[i, 2], if((Mod([1, 1; 1, 0], p)^(k/f[i, 1]))[1, 2], break); k/=f[i, 1])); k
a(n)=if(n==1, return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i, 1]>1e14, ap(f[i, 1]^f[i, 2]), ap(f[i, 1])*f[i, 1]^(f[i, 2]-1))); if(f[1, 1]==2&&f[1, 2]>1, v[1]=3<<max(f[1, 2]-2, 1)); lcm(v) \\ Charles R Greathouse IV, May 08 2017
(Scheme) (define (A001177 n) (let loop ((k 1)) (cond ((zero? (modulo (A000045 k) n)) k) (else (loop (+ k 1)))))) ;; Antti Karttunen, Dec 21 2013
(Haskell)
a001177 n = head [k | k <- [1..], a000045 k `mod` n == 0]
-- Reinhard Zumkeller, Jan 15 2014
CROSSREFS
Cf. A000045, A001175, A001176, A060383, A001602. First occurrence of k is given in A131401. A233281 gives such k that a(k) is a prime.
From Antti Karttunen, Dec 21 2013: (Start)
Various derived sequences:
A132632(n) = a(n^2).
A132633(n) = a(n^3).
A214528(n) = a(n!).
A215453(n) = a(n^n).
Analogous sequence for the tribonacci numbers: A046737, for Lucas numbers: A223486, for Pell numbers: A214028.
KEYWORD
nonn
AUTHOR
EXTENSIONS
Definition corrected by Wolfdieter Lang, Jan 19 2015
STATUS
approved