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

1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 11, 1, 1, 1, 1, 2, 1, 1, 19, 1, 3, 2, 1, 1, 1, 1, 1, 2, 29, 1, 31, 1, 3, 2, 1, 1, 1, 1, 1, 2, 41, 1, 1, 1, 3, 2, 1, 1, 7, 1, 1, 2, 1, 1, 1, 1, 3, 2, 59, 1, 61, 1, 1, 2, 1, 1, 1, 1, 3, 2, 71, 1, 1, 1, 1, 2, 1, 13, 79, 1, 3, 2, 1

Offset: 1

Author

Dmitry Kamenetsky, Jul 19 2015

Keywords

• nonn

Comments

This sequence seems good at generating primes, in particular, twin primes. Many primes p are generated when a(p)=p. In fact for n<=10000, a(n)=n occurs 617 times and 609 of these times n is prime. Furthermore, 275 of these times n is also a twin prime.

For n<=1000000 and a(n)=n this sequence generates 39210 primes (49.95% of primes in the range) and produces a prime 99.75% of the time. At the same time it generates 10864 twin primes, which is 66.50% of all twin primes in the range.

A260228 is a similar sequence that produces more primes.

It is well known that p|F(p-(p/5)) for every prime p. So a(p) = p for any prime p == 1,4 (mod 5). - Zhi-Wei Sun, Aug 29 2015

Examples

			a(2) = gcd(2,F(1)) = gcd(2,1) = 1.
a(11) = gcd(11,F(10)) = gcd(11,55) = 11.
a(19) = gcd(19,2584) = 19.
a(29) = gcd(29,317811) = 29.
		

Links

• Dmitry Kamenetsky, Table of n, a(n) for n = 1..10000
• Z.-H. Sun and Z.-W. Sun, Fibonacci numbers and Fermat's last theorem, Acta Arithmetica 60(4) (1992), 371-388.

Crossrefs

Cf. A104714, A106108, A260228.

Programs

Magma

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

Mathematica

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

PARI

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