A134734 -id:A134734 - 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

A132199 Rowland's prime-generating sequence: first differences of A106108.

Original entry on oeis.org

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101, 3, 1, 1

Offset: 1

N. J. A. Sloane, Jan 28 2008

nonn

Rowland shows that the terms are all 1's or primes.
The prime terms form A137613.
See A137613 for additional comments, links and references. - Jonathan Sondow, Aug 14 2008
From Robert G. Wilson v, Apr 30 2009: (Start)
First appearance of k-th prime, k >= 0: 1, 0, 5, 4, 104, 10, 116, 242878, 242819, 22, 243019, 3891770, 242867, ..., .
The number of different numbers in the first 10^k terms beginning with k=0: 1, 4, 7, 12, 15, 19, 30, >35, ..., .
Record high values are A191304. (End)

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

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 .
Jean-Paul Delahaye, Déconcertantes conjectures, Pour la Science (French edition of Scientific American), No. 367, May 2008.
Brian Hayes, Pumping the Primes, bit-player, 19 August 2015.
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 18.
Eric S. Rowland, A natural prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.
Eric S. Rowland, A simple prime-generating recurrence, 2008.
Eric S. Rowland, Prime-Generating Recurrences and a Tale of Logarithmic Scale, 20 January 2023.

Cf. A106108, A137613, A134734, A134743, A134744, A191304 (record highs) A247090. See A106108 for other cross-references.

a132199 n = a132199_list !! (n-1)
a132199_list = zipWith (-) (tail a106108_list) a106108_list
-- Reinhard Zumkeller, Nov 15 2013

A106108 := proc(n)
    option remember;
    if n = 1 then
        7;
    else
        procname(n-1)+igcd(n,procname(n-1)) ;
    end if;
end proc:
A132199 := proc(n)
    A106108(n+1)-A106108(n) ;
end proc: # R. J. Mathar, Jul 04 2013

a[1] = 7; a[n_] := a[n] = a[n - 1] + GCD[n, a[n - 1]]; t = Array[a, 104]; Rest@t - Most@t (* Robert G. Wilson v, Apr 30 2009 *)

ub=1000; a=7; n=2; while(nDaniel Constantin Mayer, Aug 31 2014

from itertools import count, islice
from math import gcd
def A132199_gen(): # generator of terms
    a = 7
    for n in count(2):
        yield (b:=gcd(a,n))
        a += b
A132199_list = list(islice(A132199_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

A137613 Omit the 1's from Rowland's sequence f(n) - f(n-1) = gcd(n,f(n-1)), where f(1) = 7.

Original entry on oeis.org

5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, 60647, 3, 5, 3, 101, 3, 121403, 3, 242807, 3, 5, 3, 19, 7, 5, 3, 47, 3, 37, 5, 3, 17, 3, 199, 53, 3, 29, 3, 486041, 3, 7, 421, 23

Offset: 1

Jonathan Sondow, Jan 29 2008, Jan 30 2008

nonn

Rowland proves that each term is prime. He says it is likely that all odd primes occur.
In the first 5000 terms, there are 965 distinct primes and 397 is the least odd prime that does not appear. - T. D. Noe, Mar 01 2008
In the first 10000 terms, the least odd prime that does not appear is 587, according to Rowland. - Jonathan Sondow, Aug 14 2008
Removing duplicates from this sequence yields A221869. The duplicates are A225487. - Jonathan Sondow, May 03 2013

			f(n) = 7, 8, 9, 10, 15, 18, 19, 20, ..., so f(n) - f(n-1) = 1, 1, 1, 5, 3, 1, 1, ... and a(n) = 5, 3, ... .
From _Vladimir Shevelev_, Mar 03 2010: (Start)
  a(1) = Lpf(6-1) = 5;
  a(2) = Lpf(6-2+5) = 3;
  a(3) = Lpf(6-3+5+3) = 11;
  a(4) = Lpf(6-4+5+3+11) = 3;
  a(5) = Lpf(6-5+5+3+11+3) = 23. (End)

T. D. Noe, Table of n, a(n) for n = 1..5000
Jean-Paul Delahaye, Déconcertantes conjectures, Pour la science, 5 (2008), 92-97.
Brian Hayes, Pumping the Primes, bit-player, 19 August 2015.
John Moyer, Source code in C and C++ to print this sequence or sorted and unique values from this sequence. [From John Moyer (jrm(AT)rsok.com), Nov 06 2009]
Ivars Peterson, A New Formula for Generating Primes, The Mathematical Tourist.
Eric S. Rowland, A simple prime-generating recurrence, Abstracts Amer. Math. Soc. 29 (No. 1, 2008), p. 50 (Abstract 1035-11-986).
Eric S. Rowland, A natural prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.
Eric S. Rowland, A natural prime-generating recurrence, J. of Integer Sequences 11 (2008), Article 08.2.8.
Eric Rowland, A simple recurrence that produces complex behavior ..., A New Kind of Science blog.
Eric Rowland, Prime-Generating Recurrence, Wolfram Demonstrations Project, 2008.
Eric Rowland, A Bizarre Way to Generate Primes, YouTube video, 2023.
Jeffrey Shallit, Rutgers Graduate Student Finds New Prime-Generating Formula, Recursivity blog.
Vladimir Shevelev, Generalizations of the Rowland theorem, arXiv:0911.3491 [math.NT], 2009-2010.
Wikipedia, Formula for primes.

f(n) = f(n-1) + gcd(n, f(n-1)) = A106108(n) and f(n) - f(n-1) = A132199(n-1).
Cf. also A084662, A084663, A134734, A134736, A134743, A134744, A221869.
Cf. A020639, A168008, A190894, A231900.

a137613 n = a137613_list !! (n-1)
a137613_list =  filter (> 1) a132199_list
-- Reinhard Zumkeller, Nov 15 2013

A137613_list := proc(n)
local a, c, k, L;
L := NULL; a := 7;
for k from 2 to n do
    c := igcd(k,a);
    a := a + c;
    if c > 1 then L:=L,c fi;
od;
L end:
A137613_list(500000); # Peter Luschny, Nov 17 2011

f[1] = 7; f[n_] := f[n] = f[n - 1] + GCD[n, f[n - 1]]; DeleteCases[Differences[Table[f[n], {n, 10^6}]], 1] (* Alonso del Arte, Nov 17 2011 *)

ub=1000; n=3; a=9; while(nDaniel Constantin Mayer, Aug 31 2014

from itertools import count, islice
from math import gcd
def A137613_gen(): # generator of terms
    a = 7
    for n in count(2):
        if (b:=gcd(a,n)) > 1: yield b
        a += b
A137613_list = list(islice(A137613_gen(),20)) # Chai Wah Wu, Mar 14 2023

Denote by Lpf(n) the least prime factor of n. Then a(n) = Lpf( 6-n+Sum_{i=1..n-1} a(i) ). - Vladimir Shevelev, Mar 03 2010
a(n) = A168008(2*n+4) (conjectured). - Jon Maiga, May 20 2021
a(n) = A020639(A190894(n)). - Seiichi Manyama, Aug 11 2023

A134744 First differences of A084663.

Original entry on oeis.org

2, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 13, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 29, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 59, 3, 1, 1, 7, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

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

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric S. Rowland, A simple prime-generating recurrence, arXiv:0710.3217 [math.NT], 2007-2008.

Cf. A084663. See A106108 for other cross-references.

Cf. A132199, A134734, A134743.

a134744 n = a134744_list !! (n-1)
a134744_list = zipWith (-) (tail a084663_list) a084663_list
-- Reinhard Zumkeller, Nov 15 2013

b[1] = 8; b[n_] := b[n] = b[n-1] + GCD[n, b[n-1]];
Table[b[n], {n, 105}] // Differences (* Jean-François Alcover, Sep 28 2018 *)

A134743 First differences of A134736.

Original entry on oeis.org

1, 3, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101, 3, 1, 1

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

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

See A106108 for other cross-references.

Cf. A134734, A134744.

a134743 n = a134743_list !! (n-1)
a134743_list = zipWith (-) (tail a134736_list) a134736_list
-- Reinhard Zumkeller, Nov 15 2013

b[1] = 5; b[n_] := b[n] = b[n-1] + GCD[n, b[n-1]];
Array[b, 104] // Differences (* Jean-François Alcover, Oct 01 2018 *)

a(n) = A132199(n), n>2. [R. J. Mathar, Dec 13 2008]

A291528 First term s_n(1) of equivalence classes of prime sequences {s_n(k)} for k > 0 derived by records of first differences of Rowland-like recurrences with increasing even starting values e(n) >= 4.

Original entry on oeis.org

2, 7, 17, 19, 31, 43, 53, 71, 67, 79, 97, 103, 109, 113, 127, 137, 151, 163, 181, 173, 191, 197, 199, 211, 229, 239, 241, 251, 269, 257, 271, 283, 293, 317, 331, 337, 349, 367, 373, 419, 409, 431, 433, 439, 443, 463, 491, 487, 499, 523, 557, 547, 577, 593, 607, 599, 601

Offset: 1

Ralf Steiner, Aug 25 2017

nonn

These kinds of equivalence classes {s_n(k)} were defined by Shevelev, see Crossrefs.
Some equivalence classes of prime sequences {s_n(k)} have the same tail for a constant C_n < k, such as {s_2(k)} = {a(2),...} = {7,13,29,59,131,...} and {s_5(k)} = {a(5),...} = {31,61,131,...} with common tail {131,...}. Thus it seems that all terms are leaves of a kind of an inverse prime-tree with branches in A291620 and the root at infinity.
In each equivalence class {s_n(k)} the terms hold: s_n(k+1)-2*s_n(k) >= -1;
(s_n(k+1)+1)/s_n(k) >= 2; lim_{k -> inf} (s_n(k+1)+1)/s_n(k) = 2.

			For n=1 the Rowland recurrence with e(1)=4 is A084662 with first differences A134734 and records {2,3,5,11,...} gives the least new prime a(1)=2 as the first term of a first equivalence class {2,3,5,11,...} of prime sequences.
For n=2 with e(2)=8 and records {2,7,13,29,59,...} gives the least new prime a(2)=7 as the first term of a second equivalence class {7,13,29,59,...} of prime sequences.
For n=3 with e(3)=16, a(3)=17 the third equivalence class is {17,41,83,167,...}.

Cf. A291620 (branches), A167168 (equivalence classes), A134734 (first differences of A084662), A134162.

For[i = 2; pl = {}; fp = {}, i < 350, i++,
ps = Union@FoldList[Max, 1, Rest@# - Most@#] &@
   FoldList[#1 + GCD[#2, #1] &, 2 i, Range[2, 10^5]];
p = Select[ps, (i <= #) && ! MemberQ[pl, #] &, 1];
If[p != {}, fp = Join[fp, {p}];
  pl = Union[pl,
    Drop[ps, -1 + Position[ps, p[[1]]][[1]][[1]]]]]]; Flatten@fp

a(n) >= 2*n; a(n) > 10*n - 50; a(n) < 12*n.

a(n) >= e(n) - 1, for n > 1; a(n) < e(n) + n.

A291620 Branch term s_n(b), b > 1 of equivalence classes of prime sequences {s_n(k)} for k > 0 derived by records of first differences of Rowland-like recurrences with increasing even start values >= 4.

Original entry on oeis.org

0, 0, 0, 0, 131, 0, 233, 167, 2381, 647, 0, 233, 0, 941, 263, 0, 0, 353, 0, 0, 797, 0, 0, 0, 941, 0, 0, 8273, 569, 0, 0, 569, 1181, 0, 0, 22133, 761, 0, 761, 1721, 839, 1811, 881, 0, 1811, 929, 1973, 0, 0, 1049, 1181, 9323, 2309, 1187, 0, 2441, 2441

Offset: 1

Ralf Steiner, Aug 28 2017

nonn

See A291528 (leaves) for equivalence classes.
If the conjecture of an inverse tree of primes with the leaves in A291528 using the same index n holds, except a(1)=0 all terms a(n) == 0 indicates that the branch point is not yet found.
This is a k-ary tree, k > 2, such as a(7) == a(12) == 233.
Maybe these simple Rowland-like recurrences giving all primes are related to a simple bounded physical quantum system with a "Hamiltonian for the zeros of the Riemann zeta function" (cf. Bender et al.) having degenerated energy eigenvalues a(n).
[Note: the editors feel that any such connection is extremely unlikely. - N. J. A. Sloane, Oct 30 2017]

			n=5: Some equivalence classes of prime sequences {s_n(k)} have the same tail for a constant C_n < k, such as {s_2(k)} = {7,13,29,59,131,...} and {s_5(k)} = {31,61,131,...} with common tail {a(5),...} = {131,...} and the branch 131 = a(5). Thus it seems that all terms != 0 are branches of a kind of an inverse prime-tree with the root at infinity.

Carl M. Bender, Dorje C. Brody, Markus P. Müller, Hamiltonian for the zeros of the Riemann zeta function, arXiv:1608.03679 [quant-ph], 2016.

Cf. A134162, A134734, A167168 (equivalence classes), A291528 (leaves)

For[i = 2; pl = {}; fp = {}; bp = {}, i < 350, i++,
ps = Union@FoldList[Max, 1, Rest@# - Most@#] &@
   FoldList[#1 + GCD[#2, #1] &, 2 i, Range[2, 10^5]];
p = Select[ps, (i <= #) && ! MemberQ[pl, #] &, 1];
If[p != {},
  fp = Join[fp, {p}];
  b = Select[Drop[ps, po = Position[ps, p[[1]]][[1]][[1]]],
    MemberQ[pl, #] &, 1];
  If[b != {}, bp = Join[bp, {b}], bp = Join[bp, {{0}}]];
  pl = Union[pl, Drop[ps, po - 1]]]]; Flatten@bp

a(n) > A291528(n) || a(n) == 0.

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

A132199 Rowland's prime-generating sequence: first differences of A106108.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

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

A137613 Omit the 1's from Rowland's sequence f(n) - f(n-1) = gcd(n,f(n-1)), where f(1) = 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A134744 First differences of A084663.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica

A134743 First differences of A134736.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula