A230504 Smallest prime in r(k) = r(k-1) + gcd(k,r(k-1)) with r(1) = n.

2, 2, 3, 19, 5, 19, 7, 11, 11, 17, 11, 17, 13, 17, 17, 23, 17, 23, 19, 23, 23, 29, 23, 29, 29, 29, 29, 37, 29, 37, 31, 37, 37, 53, 53, 53, 37, 41, 41, 47, 41, 47, 43, 47, 47, 53, 47, 53, 53, 53, 53, 59, 53, 59, 59, 59, 59, 67, 59, 67, 61, 67, 67, 79, 79, 79

Offset: 1

Author

Reinhard Zumkeller, Nov 15 2013

Keywords

• nonn

Comments

a(p) = p, p prime;

a(2*n-1) = A060264(n-1).

Examples

			n = 1 -> 1 + GCD(1,2) = 1+1 = 2 = prime(1) = a(1);
n = 2 = prime(1) = a(2);
n = 3 = prime(2) = a(3);
n = 4 -> 4+GCD(4,2) = 4+2 = 6 -> 6+GCD(6,3) = 6+3 = 9 -> 9+GCD(9,4) = 9+1 = 10 -> 10+GCD(10,5) = 10+5 = 15 -> 15+GCD(15,6) = 15+3 = 18 -> 18+GCD(18,7) = 18+1 = 19 = prime(8) = a(4) = A084662(7);
n = 5 = prime(3) = a(5) = A134736(1);
n = 6 -> 6+GCD(6,2) = 6+2 = 8 -> 8+GCD(8,3) = 8+1 = 9 -> 9+GCD(9,4) = 9+1 = 10 -> 10+GCD(10,5) = 10+5 = 15 -> 15+GCD(15,6) = 15+3 = 18 -> 18+GCD(18,7) = 18+1 = 19 = prime(8) = a(6);
n = 7 = prime(4) = a(7) = A106108(1);
n = 8 -> 8+GCD(8,2) = 8+2 = 10 -> 10+GCD(10,3) = 10+1 = 11 = prime(5) = a(8) = A084663(3);
n = 9 -> 9+GCD(9,2) = 9+2 = 11 = prime(5) = a(9);
n = 10 -> 10+GCD(10,2) = 10+2 = 12 -> 12+GCD(12,3) = 12+3 = 15 -> 15+GCD(15,4) = 15+1 = 16 -> 16+GCD(16,5) = 16+1 = 17 = prime(7) = a(10);
n = 11 = prime(5) = a(11);
n = 12 -> 12+GCD(12,2) = 12+2 = 14 -> 14+GCD(14,3) = 14+1 = 15 -> 15+GCD(15,4) = 15+1 = 16 -> 16+GCD(16,5) = 16+1 = 17 = prime(7) = a(10).
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Eric S. Rowland, A simple prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.

Crossrefs

Cf. A084662, A134736, A106108, A084663.

Programs

Haskell

a230504 n = head $ filter ((== 1) . a010051') rs where
                   rs = n : zipWith (+) rs (zipWith gcd rs [2..])

Mathematica

a[n_] := Module[{r}, If[PrimeQ[n], n, r[1]=n; r[k_] := r[k] = r[k-1] + GCD[k, r[k-1]]; For[k=1, True, k++, If[PrimeQ[r[k]], Return[r[k]]]]]];
Array[a, 66] (* Jean-François Alcover, Dec 03 2018 *)

Python

from math import gcd
from itertools import count, accumulate
from sympy import isprime
def A230504(n): return next(filter(isprime,accumulate(count(2),lambda x,y:x+gcd(x,y),initial=n))) # Chai Wah Wu, Mar 15 2023