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

1, 0, 8, 210, 1, 82, 128, 4763358550, 1, 22, 8, 4050643070777669523228, 1, 1010633974733, 7784, 100, 1, 26627469676193276478340, 8, 179, 1, 4082, 48, 1293523748876425462850, 1, 173, 8, 5, 1, 2423, 320, 342, 1, 1162, 8, 93, 1, 455207, 128, 22, 1, 11383, 8, 58768, 1, 91, 96, 306824898, 1, 187751, 8, 84, 1

Offset: 0

Author

M. F. Hasler, Mar 08 2015

Keywords

• nonn

Comments

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

Examples

			For n=1, gcd(k^n+4, (k+1)^n+4) = gcd(k+4, k+5) = 1, therefore a(1)=0.
For n=2, we have gcd(8^2+4, 9^2+4) = gcd(68, 85) = 17, and the pair (k,k+1)=(8,9) is the smallest with this property, therefore a(2)=8.
More generally, a(8k+2)=8 because gcd(8^(8k+2)+4, 9^(8k+2)+4) = gcd(64^(4k+1)+4, 81^(4k+1)+4) >= 17, since 64 = 81 = 13 (mod 17) and 13^4 = 1 (mod 17).
Also a(4k)=1, because gcd(1^(4k)+4, 2^(4k)+4) = gcd(5, 16^k-1) = 5.
		

Crossrefs

Cf. A118119, A255832.

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

Programs

Mathematica

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

PARI

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

Formula

a(4k)=1, a(8k+2)=8 (k>=0), cf. examples.

Extensions

a(7)-a(46) from Hiroaki Yamanouchi, Mar 13 2015

a(47)-a(52) from Max Alekseyev, Aug 06 2015