login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001177 Fibonacci entry points: a(n) = least k such that n divides Fibonacci number F_k (=A000045(k)).
(Formerly M2314 N0914)
38
1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, 56, 75, 36, 42, 27, 36, 10, 24, 36, 42, 58, 60, 15, 30, 24, 48, 35, 60, 68, 18, 24, 120 (list; graph; refs; listen; history; text; internal format)
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

Solutions to F_m == 0 (mod n) are given by m == 0 (mod a(n)).

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

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).

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

A. Allard, 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, 2014

J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.

Ramon Glez-Regueral, An entry-point algorithm for high-speed factorization, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.

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.

Samin Riasat, Z[phi] and the Fibonacci Sequence Modulo n, Mathematical Reflections 1 (2011): 1 - 7.

D. D. Wall, Fibonacci series modulo m, Am. Math. Monthly 67 (6) (1960) 525-532

Eric Weisstein, MathWorld: Wall-Sun-Sun Prime

FORMULA

A001175(n) = A001176(n) * a(n) for n >= 1.

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 (r, s) = 1 then a(r*s) = LCM(a(r), a(s)). See Posamentier & Lahmann. - Robert G. Wilson v, Jul 07 2007; corrected by Max Alekseyev, Oct 19 2007, Jun 24 2011

Apparently a(n) = A213648(n) + 1 for n >= 2. - Art DuPre, Jul 01 2012

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.

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

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=1); while(fibonacci(k++)%p, ); 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, Feb 04 2014

(PARI) ap(p)=my(k=1, c=Mod(1, p), o); while(c, [o, c]=[c, c+o]; k++); 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, Feb 13 2014

(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:

A047930(n) = A000045(a(n)).

A037943(n) = A000045(a(n))/n.

A217036(n) = A000045(a(n)-1) mod n.

A132632(n) = a(n^2).

A132633(n) = a(n^3).

A214528(n) = a(n!).

A215011(n) = a(A000217(n)).

A215453(n) = a(n^n).

Analogous sequence for the tribonacci numbers: A046737, for Lucas numbers: A223486, for Pell numbers: A214028.

Cf. also A000057, A106535, A120255, A120256, A175026, A213648, A214031, A214781, A214783, A230359, A233283, A233285, A233287. (End)

Sequence in context: A016655 A057757 A058838 * A053991 A198617 A033957

Adjacent sequences:  A001174 A001175 A001176 * A001178 A001179 A001180

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 23 00:52 EDT 2014. Contains 248411 sequences.