|
%I #46 Sep 08 2022 08:46:13
%S 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,
%T 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,
%U 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
%N a(n) = max(gcd(n,F(n-1)),gcd(n,F(n+1))), where F(n) is the n-th Fibonacci number.
%C 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).
%C 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.
%C 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.
%D David M. Burton, Elementary Number Theory, Allyn and Bacon, p. 292, 1980.
%H Dmitry Kamenetsky, <a href="/A260228/b260228.txt">Table of n, a(n) for n = 1..10000</a>
%H D. E. Daykin and L. A. G. Dresel, <a href="http://www.fq.math.ca/Scanned/8-1/daykin-a.pdf">Factorization of Fibonacci numbers</a>, Fibonacci Quarterly 8:1 (1970), pp. 23-30.
%H Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html">Factorisation of the first 300 Fibonacci numbers</a>
%H Brian Lawrence, <a href="https://sumo.stanford.edu/pdfs/speakers/fibonacci.pdf">Fibonacci numbers modulo p</a>, Stanford SUMO talk, 2014.
%H Eric W. Weisstein‘s World of Mathematics, <a href="http://mathworld.wolfram.com/PrimeFormulas.html">Prime Formulas</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Formula_for_primes">Formula for primes</a>
%e a(2) = max(gcd(2,F(1)),gcd(2,F(3))) = max(1,2)=2.
%e a(11) = max(gcd(11,F(10)),gcd(11,F(12))) = max(gcd(11,55),gcd(11,144)) = max(11,1) = 11.
%e a(13) = max(gcd(13,144),gcd(13,377)) = 13.
%e a(23) = max(gcd(23,17711),gcd(23,46368)) = 23.
%t Table[Max[GCD[n, Fibonacci[n - 1]], GCD[n, Fibonacci[n + 1]]], {n, 1, 80}] (* _Vincenzo Librandi_, Jul 20 2015 *)
%o (Magma) [Max(Gcd(n,Fibonacci(n-1)),Gcd(n,Fibonacci(n+1))): n in [1..90]]; // _Vincenzo Librandi_, Jul 20 2015
%o (PARI) first(m)=vector(m,n,max(gcd(n,fibonacci(n-1)),gcd(n,fibonacci(n+1)))) /* _Anders Hellström_, Jul 20 2015 */
%Y Cf. A106108, A182554, A260222.
%K nonn
%O 1,2
%A _Dmitry Kamenetsky_, Jul 20 2015
|
