A064526 Define a pair of sequences by p(0) = 0, q(0) = p(1) = q(1) = 1, q(n+1) = p(n)*q(n-1), p(n+1) = q(n+1) + q(n) for n > 0; then a(n) = p(n) and A064183(n) = q(n).

0, 1, 2, 3, 5, 13, 49, 529, 21121, 10369921, 213952189441, 2214253468601687041, 473721461635593679669210030081, 1048939288228833101089604217183056027094304481281

Offset: 0

Author

Michael Somos, Oct 07 2001

Keywords

• nonn
• easy

Comments

Every nonzero term is relatively prime to all others (which proves that there are infinitely many primes). See A236394 for the primes that appear.

Links

• R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - _N. J. A. Sloane_, Jun 13 2012
• Michael Somos and R. Haas, A linked pair of sequences implies the primes are infinite, Amer. Math. Monthly, 110(6) (2003), 539-540.

Crossrefs

Cf. A001685, A003686, A064183, A064847, A070231, A070233, A070234, A094303.

See A236394 for the primes that are produced.

Programs

Mathematica

Flatten[{0,1, RecurrenceTable[{a[n]==(a[n-1]^2 + a[n-2]^2 - a[n-1]*a[n-2] * (1+a[n-2]))/(1-a[n-2]), a[2]==2, a[3]==3},a,{n,2,15}]}] (* Vaclav Kotesovec, May 21 2015 *)

PARI

{a(n) = local(v); if( n<3, max(0, n), v = [1,1]; for( k=3, n, v = [v[2], v[1] * (v[1] + v[2])]); v[1] + v[2])}

PARI

{a(n) = if( n<4, max(0, n), (a(n-1)^2 + a(n-2)^2 - a(n-1) * a(n-2) * (1 + a(n-2))) / (1 - a(n-2)))}

Formula

a(n) = (a(n-1)^2 + a(n-2)^2 - a(n-1) * a(n-2) * (1 + a(n-2))) / (1 - a(n-2)) for n >= 2.

a(n) ~ c^(phi^n), where c = 1.2364241784241086061606568429916822975882631646194967549068405592472125928485... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, May 21 2015