|
%I #53 Apr 08 2016 07:34:06
%S 5,3,11,23,47,101,7,13,233,467,941,1889,3779,7559,15131,53,30323,
%T 60647,121403,242807,19,37,17,199,29,486041,421,972533,577,1945649,
%U 163,3891467,127,443,31,7783541,15567089,5323,31139561,41,62279171,83,1103,124559609
%N New primes found by Rowland's recurrence in the order of their appearance.
%C The terms up to 1103 required examining numbers produced by Rowland's recurrence up to n = 10^8. - _T. D. Noe_, Apr 11 2013
%C Exactly 177789368686545736460055960459780707068552048703463291 iterations to find the first 1000 terms of this sequence. - _T. D. Noe_, Apr 13 2013
%C The first 10^100 terms of Rowland's sequence generate 18321 primes, 3074 of which are distinct. - _Giovanni Resta_, Apr 08 2016
%C Same as A137613 with duplicates deleted; same as A132199 with 1s and duplicates deleted. - _Jonathan Sondow_, May 03 2013
%H Giovanni Resta, <a href="/A221869/b221869.txt">Table of n, a(n) for n = 1..3074</a>[Terms 1 to 1000 were computed by T. D. Noe; terms 1001 to 3074 by _Giovanni Resta_, Apr 08 2016]
%H Ivars Peterson, <a href="http://www.maa.org/mathtourist/mathtourist_8_8_08.html">A new formula for generating primes</a>
%H Eric Rowland, <a href="http://thenksblog.wordpress.com/2008/07/21/a-simple-recurrence-that-produces-complex-behavior-and-primes/">A simple recurrence that produces complex behavior — and primes!</a>
%H Eric Rowland, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html">A natural prime-generating recurrence</a>, Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8
%H Jeffrey Shallit, <a href="http://recursed.blogspot.com/2008/07/rutgers-graduate-student-finds-new.html">Recursivity: Rutgers graduate student finds new prime-generating formula</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Formula_for_primes#Recurrence_relation">Formula for primes</a>
%F Entries stem from new adjacent differences b(n) = b(n - 1) + GCD(n, b(n - 1)) where b(1)=7.
%e b(5)-b(4) = 15-10 = 5, so a(1)=5.
%e b(6)-b(5) = 18-15 = 3, so a(2)=3.
%e b(11)-b(10) = 33-22 =11, so a(3)=11.
%t t = {}; b1 = 7; Do[b0 = b1; b1 = b0 + GCD[n, b0]; d = b1 - b0; If[d > 1 && !MemberQ[t, d], AppendTo[t, d]], {n, 2, 10^6}]; t (* _T. D. Noe_, Apr 10 2013 *)
%t Rest[ DeleteDuplicates[ f[1] = 7; f[n_] := f[n] = f[n - 1] + GCD[n, f[n - 1]]; Differences[ Table[ f[n], {n, 10^6}]]]] (* _Jonathan Sondow_, May 03 2013 *)
%o See the Shallit link for code in Haskell and C.
%o (Haskell)
%o import Data.Set (singleton, member, insert)
%o a221869 n = a221869_list !! (n-1)
%o a221869_list = f 2 7 (singleton 1) where
%o f u v s | d `member` s = f (u + 1) (v + d) s
%o | otherwise = d : f (u + 1) (v + d) (d `insert` s)
%o where d = gcd u v
%o -- _Reinhard Zumkeller_, Nov 15 2013
%Y Cf. A132199, A137613.
%Y Cf. A106108.
%K nonn
%O 1,1
%A _Bill McEachen_, Apr 10 2013
%E More terms from _T. D. Noe_, Apr 11 2013
%E Edited by _N. J. A. Sloane_, Apr 12 2013 at the suggestion of Eric Rowland.
| 