A260228 a(n) = max(gcd(n,F(n-1)),gcd(n,F(n+1))), where F(n) is the n-th Fibonacci number.

1, 2, 3, 2, 1, 1, 7, 2, 3, 2, 11, 1, 13, 2, 3, 2, 17, 1, 19, 2, 3, 2, 23, 1, 1, 2, 3, 2, 29, 1, 31, 2, 3, 2, 1, 1, 37, 2, 3, 2, 41, 1, 43, 2, 3, 2, 47, 1, 7, 2, 3, 2, 53, 1, 1, 2, 3, 2, 59, 1, 61, 2, 21, 2, 1, 1, 67, 2, 3, 2, 71, 1, 73, 2, 3, 2, 1, 13, 79, 2, 3, 2, 83, 1, 1, 2, 3, 2, 89, 1, 1, 2, 3, 2, 1, 1, 97, 2, 33, 2

Offset: 1

Author

Dmitry Kamenetsky, Jul 20 2015

Keywords

• nonn

Comments

This sequence seems very good at generating primes. Many primes p are generated when a(p)=p. In fact for n<=10000, a(n)=n occurs 1242 times and 1228 of these times n is prime. When n is a composite we often have a(n)A182554).

For n<=1000000 and a(n)=n this sequence generates all primes in the given range (except 5) and produces a prime 99.73% of the time.

It is known that if p is a prime greater than 5 then either F(p-1) or F(p+1) is a multiple of p (see Lawrence and Burton references) and so for those cases we have a(p)=p.

Examples

			a(2) = max(gcd(2,F(1)),gcd(2,F(3))) = max(1,2)=2.
a(11) = max(gcd(11,F(10)),gcd(11,F(12))) = max(gcd(11,55),gcd(11,144)) = max(11,1) = 11.
a(13) = max(gcd(13,144),gcd(13,377)) = 13.
a(23) = max(gcd(23,17711),gcd(23,46368)) = 23.
		

References

• David M. Burton, Elementary Number Theory, Allyn and Bacon, p. 292, 1980.

Links

• Dmitry Kamenetsky, Table of n, a(n) for n = 1..10000
• D. E. Daykin and L. A. G. Dresel, Factorization of Fibonacci numbers, Fibonacci Quarterly 8:1 (1970), pp. 23-30.
• Ron Knott, Factorisation of the first 300 Fibonacci numbers
• Brian Lawrence, Fibonacci numbers modulo p, Stanford SUMO talk, 2014.
• Eric W. Weisstein‘s World of Mathematics, Prime Formulas
• Wikipedia, Formula for primes

Crossrefs

Cf. A106108, A182554, A260222.

Programs

Magma

[Max(Gcd(n,Fibonacci(n-1)),Gcd(n,Fibonacci(n+1))): n in [1..90]]; // Vincenzo Librandi, Jul 20 2015

Mathematica

Table[Max[GCD[n, Fibonacci[n - 1]], GCD[n, Fibonacci[n + 1]]], {n, 1, 80}] (* Vincenzo Librandi, Jul 20 2015 *)

PARI

first(m)=vector(m,n,max(gcd(n,fibonacci(n-1)),gcd(n,fibonacci(n+1)))) /* Anders Hellström, Jul 20 2015 */