A255852 - OEIS

%I #33 May 10 2024 02:33:04

%S 1,0,1,51,1,40333,1,434,1,16,1,1234,1,78607,1,8310,1,817172,1,473,1,

%T 116,1,22650,1,736546059,1,22,1,1080982,1,252,1,7809,1,644,1,

%U 1786225573,1

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

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

%C a(39) <= 8105110304875691067. - _Max Alekseyev_, Aug 06 2015

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

%C 99455164873287615636327176797646292254029648497024652505965417768073756378034012\

%C 80883965289152013363422286845290874810700297549641281106223286199677401563701715\

%C 56997846264124867393209579875386439424082082891813462700417531719383529314983727. - _Hiroaki Yamanouchi_, Mar 10 2015

%C 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

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

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

%e For n=1, gcd(k^n+2,(k+1)^n+2) = gcd(k+2,k+3) = 1, therefore a(1)=0.

%e For n=2k, see formula.

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

%t A255852[n_] := Module[{m = 1}, While[GCD[m^n + 2, (m + 1)^n + 2] <= 1, m++]; m];

%t Join[{1, 0}, Table[A255852[n], {n, 2, 24}]]

%o (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))}

%o (Python)

%o from sympy import primefactors,resultant, nthroot_mod

%o from sympy.abc import x

%o def A255852(n):

%o     if n == 0: return 1

%o     k = 0

%o     for p in primefactors(resultant(x**n+2,(x+1)**n+2)):

%o         for d in (a for a in sorted(nthroot_mod(-2,n,p,all_roots=True)) if pow(a+1,n,p)==-2%p):

%o             k = min(d,k) if k else d

%o             break

%o     return k # _Chai Wah Wu_, May 08 2024

%Y Cf. A118119, A255832, A255853-A255869

%K nonn,hard,more

%O 0,4

%A _M. F. Hasler_, Mar 08 2015

%E a(25),a(37),a(41),a(47) conjectured by _Hiroaki Yamanouchi_, Mar 10 2015; confirmed by _Max Alekseyev_, Aug 06 2015