A221869 New primes found by Rowland's recurrence in the order of their appearance.

5, 3, 11, 23, 47, 101, 7, 13, 233, 467, 941, 1889, 3779, 7559, 15131, 53, 30323, 60647, 121403, 242807, 19, 37, 17, 199, 29, 486041, 421, 972533, 577, 1945649, 163, 3891467, 127, 443, 31, 7783541, 15567089, 5323, 31139561, 41, 62279171, 83, 1103, 124559609

Offset

1,1

Comments

The terms up to 1103 required examining numbers produced by Rowland's recurrence up to n = 10^8. - T. D. Noe, Apr 11 2013

Exactly 177789368686545736460055960459780707068552048703463291 iterations to find the first 1000 terms of this sequence. - T. D. Noe, Apr 13 2013

The first 10^100 terms of Rowland's sequence generate 18321 primes, 3074 of which are distinct. - Giovanni Resta, Apr 08 2016

Same as A137613 with duplicates deleted; same as A132199 with 1s and duplicates deleted. - Jonathan Sondow, May 03 2013

Links

Giovanni Resta, Table of n, a(n) for n = 1..3074[Terms 1 to 1000 were computed by T. D. Noe; terms 1001 to 3074 by Giovanni Resta, Apr 08 2016]

Ivars Peterson, A new formula for generating primes

Eric Rowland, A simple recurrence that produces complex behavior — and primes!

Eric Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8

Jeffrey Shallit, Recursivity: Rutgers graduate student finds new prime-generating formula

Wikipedia, Formula for primes

Formula

Entries stem from new adjacent differences b(n) = b(n - 1) + GCD(n, b(n - 1)) where b(1)=7.

Example

b(5)-b(4) = 15-10 = 5, so a(1)=5.
b(6)-b(5) = 18-15 = 3, so a(2)=3.
b(11)-b(10) = 33-22 =11, so a(3)=11.

Mathematica

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 *)
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 *)

Prog

See the Shallit link for code in Haskell and C.
(Haskell)
import Data.Set (singleton, member, insert)
a221869 n = a221869_list !! (n-1)
a221869_list = f 2 7 (singleton 1) where
   f u v s | d `member` s = f (u + 1) (v + d) s
           | otherwise    = d : f (u + 1) (v + d) (d `insert` s)
           where d = gcd u v
-- Reinhard Zumkeller, Nov 15 2013

Crossrefs

Cf. A132199, A137613.

Cf. A106108.

Sequence in context: A335302 A259650 A165670 * A237116 A141234 A130180

Adjacent sequences: A221866 A221867 A221868 * A221870 A221871 A221872

Keyword

nonn

Author

Bill McEachen, Apr 10 2013

Extensions

More terms from T. D. Noe, Apr 11 2013

Edited by N. J. A. Sloane, Apr 12 2013 at the suggestion of Eric Rowland.

Status

approved