

A260228


a(n) = max(gcd(n,F(n1)),gcd(n,F(n+1))), where F(n) is the nth Fibonacci number.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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)<n. However, there are exceptions to this rule and for n<=10000 they are: 323, 377, 442, 1891, 2737, 2834, 3827, 4181, 5777, 6479, 6601, 6721 and 8149 (see 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(p1) or F(p+1) is a multiple of p (see Lawrence and Burton references) and so for those cases we have a(p)=p.


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


EXAMPLE

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.


MATHEMATICA

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


PROG

(MAGMA) [Max(Gcd(n, Fibonacci(n1)), Gcd(n, Fibonacci(n+1))): n in [1..90]]; // Vincenzo Librandi, Jul 20 2015
(PARI) first(m)=vector(m, n, max(gcd(n, fibonacci(n1)), gcd(n, fibonacci(n+1)))) /* Anders Hellström, Jul 20 2015 */


CROSSREFS

Cf. A106108, A182554, A260222.
Sequence in context: A082868 A219539 A154556 * A316657 A277914 A126626
Adjacent sequences: A260225 A260226 A260227 * A260229 A260230 A260231


KEYWORD

nonn


AUTHOR

Dmitry Kamenetsky, Jul 20 2015


STATUS

approved



