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

7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 69, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 141, 144, 145, 150, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168

Offset

1,1

Comments

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

Setting a(1) = 4 gives A084662, the same from the 3rd term on.

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

See A137613 for additional comments, links and references. - Jonathan Sondow, Aug 14 2008

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

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

References

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

Links

Indranil Ghosh, Table of n, a(n) for n = 1..25000 (terms 1..1000 from T. D. Noe)

Fernando Chamizo, Dulcinea Raboso and Serafin Ruiz-Cabello, On Rowland's sequence, Electronic J. Combin., Vol. 18(2), 2011, #P10.

Brian Hayes, Pumping the Primes, bit-player, 19 August 2015.

Eric S. Rowland, A simple prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.

Eric S. Rowland, Prime-Generating Recurrence, Wolfram Demonstrations Project. - Robert G. Wilson v, Sep 10 2008

Eric S. Rowland, Prime-Generating Recurrences and a Tale of Logarithmic Scale, YouTube video, 2023.

Maple

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)];

Mathematica

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

Prog

(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
(Haskell)
a106108 n = a106108_list !! (n-1)
a106108_list =
   7 : zipWith (+) a106108_list (zipWith gcd a106108_list [2..])
-- Reinhard Zumkeller, Nov 15 2013
(Magma) [n le 1 select 7 else Self(n-1) + Gcd(n, Self(n-1)): n in [1..70]]; // Vincenzo Librandi, Jul 19 2015
(Python)
from itertools import count, islice
from math import gcd
def A106108_gen(): # generator of terms
    yield (a:=7)
    for n in count(2):
        yield (a:=a+gcd(a, n))
A106108_list = list(islice(A106108_gen(), 20)) # Chai Wah Wu, Mar 14 2023

Crossrefs

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

Cf. A230504.

Sequence in context: A120200 A356635 A343297 * A120309 A035705 A205698

Adjacent sequences: A106105 A106106 A106107 * A106109 A106110 A106111

Keyword

nonn

Author

N. J. A. Sloane, Jan 28 2008

Status

approved