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

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,1

Comments

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

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

Maple

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;

Mathematica

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

Prog

(Haskell)
a084663 n = a084663_list !! (n-1)
a084663_list =
   8 : zipWith (+) a084663_list (zipWith gcd a084663_list [2..])
-- Reinhard Zumkeller, Nov 15 2013
(SageMath)
@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

Crossrefs

Cf. A084662, A106108.

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

Sequence in context: A043624 A043697 A043425 * A242857 A031037 A006757

Adjacent sequences: A084660 A084661 A084662 * A084664 A084665 A084666

Keyword

nonn

Author

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

Status

approved