A106108 - OEIS

%I #67 Mar 15 2023 07:53:54

%S 7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44,45,46,69,72,

%T 73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,

%U 141,144,145,150,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168

%N Rowland's prime-generating sequence: a(1) = 7; for n > 1, a(n) = a(n-1) + gcd(n, a(n-1)).

%C The title refers to the sequence of first differences, A132199.

%C Setting a(1) = 4 gives A084662.

%C Rowland proves that the first differences are all 1's or primes. The prime differences form A137613.

%C See A137613 for additional comments, links and references. - _Jonathan Sondow_, Aug 14 2008

%C Not all starting values generate differences of all 1's or primes. The following a(1) generate composite differences: 532, 533, 534, 535, 698, 699, 706, 707, 708, 709, 712, 713, 714, 715, ... - _Dmitry Kamenetsky_, Jul 18 2015

%C The same results are obtained if 2's are removed from n when gcd is performed, so the following is also true: a(1) = 7; for n > 1, a(n) = a(n-1) + gcd(A000265(n), a(n-1)). - _David Morales Marciel_, Sep 14 2016

%D Eric S. Rowland, A simple prime-generating recurrence, Abstracts Amer. Math. Soc., 29 (No. 1, 2008), p. 50 (Abstract 1035-11-986).

%H Indranil Ghosh, <a href="/A106108/b106108.txt">Table of n, a(n) for n = 1..25000</a> (terms 1..1000 from T. D. Noe)

%H Fernando Chamizo, Dulcinea Raboso and Serafin Ruiz-Cabello, <a href="https://doi.org/10.37236/2006">On Rowland's sequence</a>, Electronic J. Combin., Vol. 18(2), 2011, #P10.

%H Brian Hayes, <a href="http://bit-player.org/2015/pumping-the-primes">Pumping the Primes</a>, bit-player, 19 August 2015.

%H Eric S. Rowland, <a href="http://arXiv.org/abs/0710.3217">A simple prime-generating recurrence</a>, arXiv:0710.3217 [math.NT], 2007-2008.

%H Eric S. Rowland, <a href="http://demonstrations.wolfram.com/PrimeGeneratingRecurrence/">Prime-Generating Recurrence</a>, Wolfram Demonstrations Project. - _Robert G. Wilson v_, Sep 10 2008

%H Eric S. Rowland, <a href="https://www.youtube.com/watch?v=OpaKpzMFOpg">Prime-Generating Recurrences and a Tale of Logarithmic Scale</a>, YouTube video, 2023.

%p S:=7; f:= proc(n) option remember; global S; if n=1 then RETURN(S); else RETURN(f(n-1)+gcd(n,f(n-1))); fi; end; [seq(f(n),n=1..200)];

%t a[1] = 7; a[n_] := a[n] = a[n - 1] + GCD[n, a[n - 1]]; Array[a, 66] (* _Robert G. Wilson v_, Sep 10 2008 *)

%o (PARI) a=vector(100);a[1]=7;for(n=2,#a,a[n]=a[n-1]+gcd(n,a[n-1]));a \\ _Charles R Greathouse IV_, Jul 15 2011

%o (Haskell)

%o a106108 n = a106108_list !! (n-1)

%o a106108_list =

%o    7 : zipWith (+) a106108_list (zipWith gcd a106108_list [2..])

%o -- _Reinhard Zumkeller_, Nov 15 2013

%o (Magma) [n le 1 select 7 else Self(n-1) + Gcd(n, Self(n-1)): n in [1..70]]; // _Vincenzo Librandi_, Jul 19 2015

%o (Python)

%o from itertools import count, islice

%o from math import gcd

%o def A106108_gen(): # generator of terms

%o     yield (a:=7)

%o     for n in count(2):

%o         yield (a:=a+gcd(a,n))

%o A106108_list = list(islice(A106108_gen(),20)) # _Chai Wah Wu_, Mar 14 2023

%Y Cf. A084662, A084663, A132199, A134734, A134736, A134743, A134744, A134162, A137613, A221869.

%Y Cf. A230504.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Jan 28 2008