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

Author

Bill McEachen, Apr 10 2013

Keywords

• nonn

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

Examples

			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.
		

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

Crossrefs

Cf. A132199, A137613.

Cf. A106108.

Programs

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

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

Formula

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

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.