A230504 -id:A230504 - cp's OEIS frontend

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

N. J. A. Sloane, Jan 28 2008

nonn

The title refers to the sequence of first differences, A132199.
Setting a(1) = 4 gives A084662.
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

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

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.

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

Cf. A230504.

a106108 n = a106108_list !! (n-1)
a106108_list =
   7 : zipWith (+) a106108_list (zipWith gcd a106108_list [2..])
-- Reinhard Zumkeller, Nov 15 2013

[n le 1 select 7 else Self(n-1) + Gcd(n, Self(n-1)): n in [1..70]]; // Vincenzo Librandi, Jul 19 2015

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

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

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

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

A084662 a(1) = 4; a(n) = a(n-1) + gcd(a(n-1), n).

Original entry on oeis.org

4, 6, 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

Matthew Frank (mfrank(AT)wopr.wolfram.com) on behalf of the 2003 New Kind of Science Summer School, Jul 15 2003

nonn

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

Indranil Ghosh, Table of n, a(n) for n = 1..50000 (terms 1..1000 from T. D. Noe)
Eric S. Rowland, A simple prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.

Cf. A084663, A106108 and other sequences mentioned in A106108.

Cf. A134734 (first differences), A134736, A230504.

a084662 n = a084662_list !! (n-1)
a084662_list =
   4 : zipWith (+) a084662_list (zipWith gcd a084662_list [2..])
-- Reinhard Zumkeller, Nov 15 2013

[n eq 1 select 4 else Self(n-1)+Gcd(Self(n-1),n): n in [1..66]]; // Bruno Berselli, May 24 2011

S := 4; f := proc(n) option remember; global S; if n=1 then S else f(n-1)+igcd(n,f(n-1)); fi; end;

a[1]= 4; a[n_]:= a[n]= a[n-1] + GCD[n, a[n-1]]; Table[a[n], {n, 70}]
nxt[{n_, a_}]:= {n+1, a + GCD[a, n+1]}; NestList[nxt,{1,4},70][[All,2]] (* Harvey P. Dale, Dec 25 2018 *)

a[1]:4$ a[n]:=a[n-1]+gcd(a[n-1],n)$ makelist(a[n], n, 1, 66); /* Bruno Berselli, May 24 2011 */

@CachedFunction
def a(n): # a = A084662
    if (n==1): return 4
    else: return a(n-1) + gcd(a(n-1), n)
[a(n) for n in range(1,71)] # G. C. Greubel, Mar 22 2023

A084663 a(1) = 8; a(n) = a(n-1) + gcd(a(n-1), n).

Original entry on oeis.org

8, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 39, 40, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 87, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 177, 180, 181, 182, 189, 190

Offset: 1

Matthew Frank (mfrank(AT)wopr.wolfram.com) on behalf of the 2003 New Kind of Science Summer School, Jul 15 2003

nonn

The first 150000000 differences are all primes or 1. Is this true in general?

The proof of the conjecture is identical to the proof in the Rowland link. - Yifan Xie, Apr 11 2025

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

Indranil Ghosh, Table of n, a(n) for n = 1..50000
Eric S. Rowland, A natural prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.
Eric S. Rowland, A natural prime-generating recurrence, JIS 11 (2008) 08.2.8.

Cf. A084662, A106108.

Cf. A230504, A134744 (first differences), A134736.

a084663 n = a084663_list !! (n-1)
a084663_list =
   8 : zipWith (+) a084663_list (zipWith gcd a084663_list [2..])
-- Reinhard Zumkeller, Nov 15 2013

S := 8; f := proc(n) option remember; global S; if n=1 then S else f(n-1)+igcd(n,f(n-1)); fi; end;

a[n_]:= a[n]= If[n==1,8, a[n-1] + GCD[n, a[n-1]]]; Table[a[n], {n,70}]
RecurrenceTable[{a[1]==8,a[n]==a[n-1]+GCD[a[n-1],n]},a,{n,70}] (* Harvey P. Dale, Apr 12 2016 *)

@CachedFunction
def a(n): # a = A084663
    if (n==1): return 8
    else: return a(n-1) + gcd(a(n-1), n)
[a(n) for n in range(1, 71)] # G. C. Greubel, Mar 22 2023

A134736 a(1) = 5; for n >1, a(n) = a(n-1) + gcd(n, a(n-1)).

Original entry on oeis.org

5, 6, 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

N. J. A. Sloane, Jan 28 2008

nonn

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

T. D. Noe, Table of n, a(n) for n=1..1000
Eric S. Rowland, A natural prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.

See A106108 for other cross-references.

Cf. A230504, A134743 (first differences), A084662, A084663.

a134736 n = a134736_list !! (n-1)
a134736_list =
   5 : zipWith (+) a134736_list (zipWith gcd a134736_list [2..])
-- Reinhard Zumkeller, Nov 15 2013

a[1] = 5; a[n_] := a[n] = a[n-1] + GCD[n, a[n-1]];
Array[a, 66] (* Jean-François Alcover, Oct 01 2018 *)
RecurrenceTable[{a[1]==5,a[n]==a[n-1]+GCD[n,a[n-1]]},a,{n,70}] (* Harvey P. Dale, Nov 24 2018 *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

A084662 a(1) = 4; a(n) = a(n-1) + gcd(a(n-1), n).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

SageMath

A084663 a(1) = 8; a(n) = a(n-1) + gcd(a(n-1), n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

SageMath

A134736 a(1) = 5; for n >1, a(n) = a(n-1) + gcd(n, a(n-1)).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica