cp's OEIS Frontend

A167195 a(2)=3, for n>=3, a(n)=a(n-1)+gcd(n, a(n-1)).

%I A167195 #17 Aug 24 2025 22:07:56
%S A167195 3,6,8,9,12,13,14,15,20,21,24,25,26,27,28,29,30,31,32,33,44,45,48,49,
%T A167195 50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,92,93,96,
%U A167195 97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116
%N A167195 a(2)=3, for n>=3, a(n)=a(n-1)+gcd(n, a(n-1)).
%C A167195 For every n>=3, a(n)-a(n-1) is 1 or prime. This Rowland-like "generator of primes" is different from A106108 and from generators A167168. Generalization: Let p be a prime. Let N(p-1)=p and for n>=p, N(n)=N(n-1)+gcd(n, N(n-1)). Then, for every n>=p, N(n)-N(n-1) is 1 or prime.
%H A167195 G. C. Greubel, <a href="/A167195/b167195.txt">Table of n, a(n) for n = 2..1000</a>
%H A167195 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, 11 (2008), Article 08.2.8.
%H A167195 Vladimir Shevelev, <a href="http://arxiv.org/abs/0910.4676">A new generator of primes based on the Rowland idea</a>, arXiv:0910.4676 [math.NT], 2009.
%F A167195 a(n) = a(n-1) + 1 if gcd(a(n-1), n) = 1, or a(n) = 2*n otherwise. - _Yifan Xie_, Aug 20 2025
%t A167195 RecurrenceTable[{a[n] == a[n - 1] + GCD[n, a[n - 1]], a[2] == 3}, a, {n, 2, 100}] (* _G. C. Greubel_, Jun 05 2016 *)
%Y A167195 Cf. A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.
%K A167195 nonn,easy,changed
%O A167195 2,1
%A A167195 _Vladimir Shevelev_, Oct 30 2009, Nov 06 2009
%E A167195 Edited by _Charles R Greathouse IV_, Nov 02 2009