%I #30 Jan 24 2023 14:42:43

%S 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,

%T 38,39,52,53,54,55,60,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,

%U 79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,124,125,126

%N 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.

%C 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).

%C 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

%C 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

%H Bill McEachen, <a href="/A167493/b167493.txt">Table of n, a(n) for n = 1..100000</a>

%H E. S. 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 Vladimir Shevelev, <a href="https://arxiv.org/abs/0910.4676">A new generator of primes based on the Rowland idea</a>, arXiv:0910.4676 [math.NT], 2009.

%H Vladimir Shevelev, <a href="https://arxiv.org/abs/0911.5478">Three theorems on twin primes</a>, arXiv:0911.5478 [math.NT], 2009-2010.

%F For n > 3, n < a(n) < n*(n-1)/2. - _Charles R Greathouse IV_, Jan 22 2023

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

%o (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

%o (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o an = 2

%o for n in count(2):

%o yield an

%o an = an + gcd(n, an) if n&1 else an + gcd(n-2, an)

%o print(list(islice(agen(), 66))) # _Michael S. Branicky_, Jan 22 2023

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

%Y Cf also A006512, A167494.

%K nonn

%O 1,1

%A _Vladimir Shevelev_, Nov 05 2009

%E More terms from _Harvey P. Dale_, Dec 05 2015