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

1, 0, 6, 56, 3, 29, 96, 1159823, 384, 9, 3, 1994117680, 13, 247, 6, 15, 3, 1256, 4, 25211925041, 15, 5785, 3, 93602696971, 24, 11, 6, 182, 3, 4644, 92, 12506, 9, 13, 3, 484, 2, 420, 6, 130, 3, 16032496, 12

Offset: 0

Author

M. F. Hasler, Mar 08 2015

Keywords

• nonn
• hard

Comments

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

a(43) <= 291613846670877. - Max Alekseyev, Aug 07 2015

Examples

			For n=1, gcd(k^n+3, (k+1)^n+3) = gcd(k+3, k+4) = 1, therefore a(1)=0.
For n=2, we have gcd(6^2+3, 7^2+3) = gcd(39, 52) = 13, and the pair (k,k+1)=(6,7) is the smallest which yields a GCD > 1, therefore a(2)=6.
		

Crossrefs

Cf. A118119, A255832.

Cf. A255852, A255854, A255855, A255856, A255857, A255858, A255869.

Programs

Mathematica

A255853[n_] := Module[{m = 1}, While[GCD[m^n + 3, (m + 1)^n + 3] <= 1, m++]; m]; Join[{1, 0}, Table[A255853[n], {n, 2, 10}]] (* Robert Price, Oct 15 2018 *)

PARI

a(n,c=3,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 A255853(n):
    if n == 0: return 1
    k = 0
    for p in primefactors(resultant(x**n+3,(x+1)**n+3)):
        for d in (a for a in sorted(nthroot_mod(-3,n,p,all_roots=True)) if pow(a+1,n,p)==-3%p):
            k = min(d,k) if k else d
            break
    return int(k) # Chai Wah Wu, May 08 2024

Formula

For k>=0, a(6k+4)=3 because gcd(3^(6k+4)+3, 4^(6k+4)+3) = gcd(9^(3k+2)+3, 16^(3k+2)+3) and 9 = 16 = 2 (mod 7) and 2^(3k+2)+3 = 2^2+3 = 0 (mod 7), so the GCD is a positive multiple of 7.

Extensions

a(11)-a(40) from Hiroaki Yamanouchi, Mar 12 2015

a(41)-a(42) from Max Alekseyev, Aug 06 2015