A133058 a(0) = a(1) = 1; for n > 1, a(n) = a(n-1) + n + 1 if a(n-1) and n are coprime, otherwise a(n) = a(n-1)/gcd(a(n-1),n).

1, 1, 4, 8, 2, 8, 4, 12, 3, 1, 12, 24, 2, 16, 8, 24, 3, 21, 7, 27, 48, 16, 8, 32, 4, 30, 15, 5, 34, 64, 32, 64, 2, 36, 18, 54, 3, 41, 80, 120, 3, 45, 15, 59, 104, 150, 75, 123, 41, 91, 142, 194, 97, 151, 206, 262, 131, 189, 248, 308, 77, 139, 202, 266, 133, 199, 266, 334, 167

Offset: 0

Author

Ctibor O. Zizka, Dec 16 2007

Keywords

• nonn
• look
• nice
• easy

Comments

Remarkably, at n = 638 the sequence settles down and becomes quasi-periodic. - N. J. A. Sloane, Feb 22 2015. (Whenever I look at this sequence I am reminded of the great "Fly straight, dammit" scene in the movie "Avatar". - N. J. A. Sloane, Aug 06 2019)

For every choice of initial term a(0) there exist integers r and t >= 0 such that a(2*r+4*t+0) = 1, a(2*r+4*t+1) = 2*r+4*t+3, a(2*r+4*t+2) = 2*(2*r+4*t+3), a(2*r+4*t+3) = 2. - Ctibor O. Zizka, Dec 26 2007

See also the variants A255051 (which starts immediately with the same (1, x, 2x, 2) loop that the present sequence enters at n >= 641) and A255140 (which enters a different loop at n = 82). - M. F. Hasler, Feb 15 2015

With the recurrence used here (but with different starting values), if at some point we find a(2k) = 1, then from that point on the sequence looks like (1, x, 2x, 2), (1, x+4, 2(x+4), 2), (1, x+8, 2(x+8), 2), (1, x+12, 2(x+12), 2), ... where x = 2k+3. This is just a restatement of Zizka's comment above (although I have not seen a proof that this must always happen). - N. J. A. Sloane, Feb 22 2015

It is conjectured that quasi-periodic sequences exist only for R = 0, 1, 2 or 3 in a(n) = a(n-1) + n + R and that for R >= 4 the recurrence is not quasi-periodic. For R = 0, 1, 2 all starting values give a quasi-periodic sequence. The respective loop is (1, x) for R = 0, (1, x, 2x, 2) for R = 1 (this sequence), (1, x, 2x, x) or (2x, x) for R = 2. For R = 3 only some starting values converge to a 6-loop (4x+2, 2x+1, 3x+6, x+2, 2x+9, 3x+17). - Ctibor O. Zizka, Oct 27 2015

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..10000, May 26 2016 [First 1000 terms from Harvey P. Dale]
• Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
• N. J. A. Sloane, Graph of the first 1000 terms, showing the transition from chaos to order more dramatically.
• N. J. A. Sloane and Brady Haran, Amazing Graphs, Numberphile video (2019).
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Crossrefs

Cf. A091508, A133579, A133580; A255051, A255140, A262922.

Quadrisections: A326991, A326992, A326993, A326994.

Programs

Magma

a:=[1]; for n in [2..70] do if Gcd(a[n-1],n) eq 1 then Append(~a, a[n-1] + n + 1); else Append(~a, a[n-1] div Gcd(a[n-1],n)); end if; end for; [1] cat a; // Marius A. Burtea, Jan 12 2020

Maple

A[0]:= 1: A[1]:= 1:
for n from 2 to 1000 do
  g:= igcd(A[n-1],n);
  A[n]:= A[n-1]/g + `if`(g=1, n+1, 0);
od:
seq(A[i],i=0..1000); # Robert Israel, Nov 06 2015

Mathematica

nxt[{n_,a_}]:={n+1,If[CoprimeQ[a,n+1],a+n+2,a/GCD[a,n+1]]}; Join[{1}, Transpose[ NestList[nxt,{1,1},70]][[2]]] (* Harvey P. Dale, Feb 14 2015 *)

PARI

(A133058_upto(N)=vector(N, n, if(gcd(N,n-1)>1 || n<3, N\=gcd(N,n-1), N+=n)))(100) \\ M. F. Hasler, Feb 15 2015, simplified Jan 11 2020

Python

from itertools import count, islice
from math import gcd
def A133058_gen(): # generator of terms
    a = 1
    yield from (1,1)
    for n in count(2):
        yield (a:=a+n+1 if (b:=gcd(a,n)) == 1 else a//b)
A133058_list = list(islice(A133058_gen(),30)) # Chai Wah Wu, Mar 18 2023

Extensions

More terms from Ctibor O. Zizka, Dec 26 2007

Offset and definition corrected by N. J. A. Sloane, Feb 13 2015