A167493 a(1) = 2; thereafter a(n) = a(n-1) + gcd(n, a(n-1)) if n is odd, and a(n) = a(n-1) + gcd(n-2, a(n-1)) if n is even.

2, 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 19, 20, 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39, 52, 53, 54, 55, 60, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 124, 125, 126

Offset: 1

Author

Vladimir Shevelev, Nov 05 2009

Keywords

• nonn

Comments

Conjectures. 1) For n >= 2, every difference a(n) - a(n-1) is 1 or prime; 2) Every record of differences a(n) - a(n-1) greater than 3 belongs to the sequence of the greater of twin primes (A006512).

Conjecture #1 above fails at n = 620757, with a(n) = 1241487 and a(n-1) = 1241460, difference = 27. Additionally, the terms of related A167495(m) quickly tend to index n/2. So for example, A167495(14) = 19141 is seen at n = 38284. - Bill McEachen, Jan 20 2023

It seems that, for n > 4, (3*n-3)/2 <= a(n) <= 2n - 3. Can anyone find a proof or disproof? - Charles R Greathouse IV, Jan 22 2023

Links

• Bill McEachen, Table of n, a(n) for n = 1..100000
• E. S. Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, Vol.11 (2008), Article 08.2.8.
• Vladimir Shevelev, A new generator of primes based on the Rowland idea, arXiv:0910.4676 [math.NT], 2009.
• Vladimir Shevelev, Three theorems on twin primes, arXiv:0911.5478 [math.NT], 2009-2010.

Crossrefs

Cf. A167197, A167195, A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.

Cf also A006512, A167494.

Programs

Mathematica

nxt[{n_,a_}]:={n+1,If[EvenQ[n],a+GCD[n+1,a],a+GCD[n-1,a]]}; Transpose[ NestList[nxt,{1,2},70]][[2]] (* Harvey P. Dale, Dec 05 2015 *)

PARI

lista(nn)=my(va = vector(nn)); va[1] = 2; for (n=2, nn, va[n] = if (n%2, va[n-1] + gcd(n, va[n-1]), va[n-1] + gcd(n-2, va[n-1]));); va; \\ Michel Marcus, Dec 13 2018

Python

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    an = 2
    for n in count(2):
        yield an
        an = an + gcd(n, an) if n&1 else an + gcd(n-2, an)
print(list(islice(agen(), 66))) # Michael S. Branicky, Jan 22 2023

Formula

For n > 3, n < a(n) < n*(n-1)/2. - Charles R Greathouse IV, Jan 22 2023

Extensions

More terms from Harvey P. Dale, Dec 05 2015