A255852 Least k > 0 such that gcd(k^n+2, (k+1)^n+2) > 1, or 0 if there is no such k.

1, 0, 1, 51, 1, 40333, 1, 434, 1, 16, 1, 1234, 1, 78607, 1, 8310, 1, 817172, 1, 473, 1, 116, 1, 22650, 1, 736546059, 1, 22, 1, 1080982, 1, 252, 1, 7809, 1, 644, 1, 1786225573, 1

Offset: 0

Author

M. F. Hasler, Mar 08 2015

Keywords

• nonn
• hard
• more

Comments

See A118119, which is the main entry for this class of sequences.

a(39) <= 8105110304875691067. - Max Alekseyev, Aug 06 2015

a(41) = 34290868, a(49) <= 2002111070, a(47) = 32286649814088452353414982038778088771611290478685407234712300075870593693164721\

99455164873287615636327176797646292254029648497024652505965417768073756378034012\

80883965289152013363422286845290874810700297549641281106223286199677401563701715\

56997846264124867393209579875386439424082082891813462700417531719383529314983727. - Hiroaki Yamanouchi, Mar 10 2015

a(43) = 3585, a(45) = 5, a(51) = 16, a(57) = 22, a(59) = 4495, a(63) = 1291, a(65) = 108, a(67) = 220, a(69) = 218039, a(71) = 2112. - Chai Wah Wu, May 08 2024

Examples

			For n=1, gcd(k^n+2,(k+1)^n+2) = gcd(k+2,k+3) = 1, therefore a(1)=0.
For n=2k, see formula.
For n=3, we have gcd(51^3+2,52^3+2) = 109, and the pair (k,k+1)=(51,52) is the smallest which yields a GCD > 1, therefore a(3)=51.
		

Crossrefs

Cf. A118119, A255832, A255853-A255869

Programs

Mathematica

A255852[n_] := Module[{m = 1}, While[GCD[m^n + 2, (m + 1)^n + 2] <= 1, m++]; m];
Join[{1, 0}, Table[A255852[n], {n, 2, 24}]]

PARI

a(n, c=2, L=10^7, S=1)={n!=1 && for(a=S, L, gcd(a^n+c, (a+1)^n+c)>1&&return(a))}

Python

from sympy import primefactors,resultant, nthroot_mod
from sympy.abc import x
def A255852(n):
    if n == 0: return 1
    k = 0
    for p in primefactors(resultant(x**n+2,(x+1)**n+2)):
        for d in (a for a in sorted(nthroot_mod(-2,n,p,all_roots=True)) if pow(a+1,n,p)==-2%p):
            k = min(d,k) if k else d
            break
    return k # Chai Wah Wu, May 08 2024

Formula

a(2k)=1 for k>=0, because gcd(1^(2k)+2,2^(2k)+2) = gcd(3,4^k-1) = 3.

a(2k+1) = A255832(k).

Extensions

a(25),a(37),a(41),a(47) conjectured by Hiroaki Yamanouchi, Mar 10 2015; confirmed by Max Alekseyev, Aug 06 2015