A134162 -id:A134162 - cp's OEIS frontend

A167493 a(1) = 2; thereafter a(n) = a(n-1) + gcd(n, a(n-1)) if n is odd, and a(n) = a(n-1) + gcd(n-2, a(n-1)) if n is even.

2, 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 19, 20, 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39, 52, 53, 54, 55, 60, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 124, 125, 126

Offset: 1

Vladimir Shevelev, Nov 05 2009

nonn

Conjectures. 1) For n >= 2, every difference a(n) - a(n-1) is 1 or prime; 2) Every record of differences a(n) - a(n-1) greater than 3 belongs to the sequence of the greater of twin primes (A006512).
Conjecture #1 above fails at n = 620757, with a(n) = 1241487 and a(n-1) = 1241460, difference = 27. Additionally, the terms of related A167495(m) quickly tend to index n/2. So for example, A167495(14) = 19141 is seen at n = 38284. - Bill McEachen, Jan 20 2023
It seems that, for n > 4, (3*n-3)/2 <= a(n) <= 2n - 3. Can anyone find a proof or disproof? - Charles R Greathouse IV, Jan 22 2023

Bill McEachen, Table of n, a(n) for n = 1..100000
E. S. Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, Vol.11 (2008), Article 08.2.8.
Vladimir Shevelev, A new generator of primes based on the Rowland idea, arXiv:0910.4676 [math.NT], 2009.
Vladimir Shevelev, Three theorems on twin primes, arXiv:0911.5478 [math.NT], 2009-2010.

Cf. A167197, A167195, A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.

Cf also A006512, A167494.

nxt[{n_,a_}]:={n+1,If[EvenQ[n],a+GCD[n+1,a],a+GCD[n-1,a]]}; Transpose[ NestList[nxt,{1,2},70]][[2]] (* Harvey P. Dale, Dec 05 2015 *)

lista(nn)=my(va = vector(nn)); va[1] = 2; for (n=2, nn, va[n] = if (n%2, va[n-1] + gcd(n, va[n-1]), va[n-1] + gcd(n-2, va[n-1]));); va; \\ Michel Marcus, Dec 13 2018

from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    an = 2
    for n in count(2):
        yield an
        an = an + gcd(n, an) if n&1 else an + gcd(n-2, an)
print(list(islice(agen(), 66))) # Michael S. Branicky, Jan 22 2023

For n > 3, n < a(n) < n*(n-1)/2. - Charles R Greathouse IV, Jan 22 2023

More terms from Harvey P. Dale, Dec 05 2015

A167494 List of first differences of A167493 that are different from 1.

Original entry on oeis.org

2, 3, 3, 5, 3, 13, 5, 3, 31, 61, 7, 5, 3, 7, 139, 5, 3, 283, 5, 3, 571, 7, 5, 3, 1153, 5, 3, 2311, 31, 4651, 17, 5, 13, 3, 3, 5, 3, 9343, 5, 3, 11, 3, 59, 3, 29, 3, 19, 7, 5, 3, 7, 19, 5, 3, 17, 3, 113

Offset: 1

Vladimir Shevelev, Nov 05 2009

nonn

Conjecture. All terms of the sequence are primes.

The conjecture is false: a(144)=27, a(146)=25, a(158)=45, etc., which are composite numbers. - Harvey P. Dale, Dec 05 2015

Michel Marcus, Table of n, a(n) for n = 1..211
E. S. Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8.
V. Shevelev, A new generator of primes based on the Rowland idea, arXiv:0910.4676 [math.NT], 2009.
V. Shevelev, Three theorems on twin primes, arXiv:0911.5478 [math.NT], 2009-2010. [From _Vladimir Shevelev_, Dec 03 2009]

Cf. A167493, A167197, A167195, A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.

nxt[{n_,a_}]:={n+1,If[EvenQ[n],a+GCD[n+1,a],a+GCD[n-1,a]]}; DeleteCases[ Differences[ Transpose[NestList[nxt,{1,2},20000]][[2]]],1] (* Harvey P. Dale, Dec 05 2015 *)

lista(nn) = {my(va = vector(nn)); va[1] = 2; for (n=2, nn, va[n] = if (n%2, va[n-1] + gcd(n, va[n-1]), va[n-1] + gcd(n-2, va[n-1]));); select(x->(x!=1), vector(nn-1, n, va[n+1] - va[n]));} \\ Michel Marcus, Dec 13 2018

A168143 a(17)=37; for n>=17, a(n)=3n-14 if gcd(n,a(n-1))>1 and all prime divisors of n more than 17; a(n)=a(n-1)+1, otherwise.

Original entry on oeis.org

37, 38, 43, 44, 45, 46, 55, 56, 57, 58, 59, 60, 61, 62, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157

Offset: 17

Vladimir Shevelev, Nov 19 2009

nonn

a(n+1)-a(n)+14 is either 15 or a prime > 17. For a generalization, see the second Shevelev link. - Edited by Robert Israel, Aug 21 2017

Robert Israel, Table of n, a(n) for n = 17..10000
E. S. Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8.
V. Shevelev, A new generator of primes based on the Rowland idea, arXiv:0910.4676 [math.NT], 2009.
V. Shevelev, Generalizations of the Rowland theorem, arXiv:0911.3491 [math.NT], 2009-2010.

Cf. A167495, A167494, A167493, A167197, A167195, A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.

A[17]:= 37:
q:= convert(select(isprime,[$2..17]),`*`);
for n from 18 to 100 do
  if igcd(n,A[n-1]) > 1 and igcd(n,q) = 1 then A[n]:= 3*n-14
    else A[n]:= A[n-1]+1 fi
od:
seq(A[i],i=17..100); # Robert Israel, Aug 21 2017

nxt[{n_,a_}]:={n+1,If[GCD[n+1,a]>1&&FactorInteger[n+1][[1,1]]>17,3(n+1)-14,a+1]}; NestList[nxt,{17,37},60][[All,2]] (* Harvey P. Dale, Aug 15 2017 *)

Corrected by Harvey P. Dale, Aug 15 2017

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.

A168144 First differences of A168143 which are different from 1, incremented by 14.

Original entry on oeis.org

19, 23, 31, 47, 79

Offset: 1

Vladimir Shevelev, Nov 19 2009

nonn

All terms of the sequence are primes greater than 17.

Are there more than 5 terms?

E. S. Rowland, A natural prime-generating recurrence, Journal of Integer Sequences, 11 (2008), Article 08.2.8.
V. Shevelev, An infinite set of generators of primes based on the Rowland idea and conjectures concerning twin primes, arXiv:0910.4676 [math.NT], 2009.
V. Shevelev, Generalizations of the Rowland theorem, arXiv:0911.3491 [math.NT], 2009-2010.

Cf. A168143, A167495, A167494, A167493, A167197, A167195, A167170, A167168, A106108, A132199, A167054, A167053, A166944, A166945, A116533, A163961, A163963, A084662, A084663, A134162, A135506, A135508, A118679, A120293.

A168143[17] = 37;
A168143[n_] := A168143[n] = If[GCD[n, A168143[n - 1]] > 1 && FactorInteger[n][[1, 1]] > 17, 3 n - 14, A168143[n - 1] + 1]
DeleteCases[Differences[A168143 /@ Range[17, 100]], 1] + 14 (* Eric Rowland, Jan 27 2019 *)

Corrected and edited by Eric Rowland, Jan 27 2019

cp's OEIS Frontend

A167493 a(1) = 2; thereafter a(n) = a(n-1) + gcd(n, a(n-1)) if n is odd, and a(n) = a(n-1) + gcd(n-2, a(n-1)) if n is even.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A167494 List of first differences of A167493 that are different from 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A168143 a(17)=37; for n>=17, a(n)=3n-14 if gcd(n,a(n-1))>1 and all prime divisors of n more than 17; a(n)=a(n-1)+1, otherwise.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A168144 First differences of A168143 which are different from 1, incremented by 14.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions