A255869 -id:A255869 - cp's OEIS frontend

A118119 Smallest integer m for which gcd(m^n + 1, (m+1)^n + 1) > 1.

2, 5, 8, 6, 2, 4, 5, 2, 2, 10, 8, 6, 2, 3, 6, 14, 2, 37, 6, 2, 2, 10, 2, 6, 2, 2, 6, 10, 2, 52, 22, 2, 2, 4, 8, 26, 2, 3, 5, 5, 2, 24, 6, 2, 2, 32, 6, 4, 2, 2, 8, 5, 2, 6, 5, 4, 2, 230, 2, 44, 2, 2, 17, 4, 2, 55, 5, 2, 2, 34, 2, 9, 2, 3, 8, 4, 2, 6, 6, 2, 2, 2, 3

Offset: 2

Adam Kertesz, May 12 2006; May 13 2006

nonn

Let f(x) := x^n + c and g(x) := (x+1)^n + c. It can be shown that there exists an integer polynomial s(x) and t(x) such that s(x) f(x) + t(x) g(x) = resultant(f, g) for all x. Let p be a prime number such that f(x_0) == 0 (mod p) and g(x_0) == 0 (mod p) for some x_0 in Z/pZ. Then, s(x_0) f(x_0) + t(x_0) g(x_0) == 0 == resultant(f,g) (mod p). So, p|resultant(f,g). If gcd(f(x_0), g(x_0)) > 1 for some integer x_0, there exists a prime number p which divides gcd(f(x_0), g(x_0)). We can assume that p is a prime factor of resultant(f,g). Let S be a set of x (in Z/pZ) such that x^n == -c (mod p). If we are able to find consecutive terms y, y+1 in S, then y is one of the solutions such that gcd(f(y),g(y)) > 1. - Hiroaki Yamanouchi, Mar 11 2015

			a(3)=5 because gcd(2 = 1^3 + 1, 9 = 2^3 + 1) = gcd(9, 28) = gcd(28, 65) = gcd(65, 126) = 1 and gcd(126 = 5^3 + 1, 217 = 6^3 + 1) = 7 > 1.

Chai Wah Wu, Table of n, a(n) for n = 2..10000

Sequences of smallest m with gcd(m^n + c, (m+1)^n + c) > 1: A255852 (c=2), A255853 (c=3), A255854 (c=4), A255855 (c=5), A255856 (c=6), A255857 (c=7), A255858 (c=8), A255859 (c=9), A255860 (c=10), A255861 (c=11), A255862 (c=12), A255863 (c=13), A255864 (c=14), A255865 (c=15), A255866 (c=16), A255867 (c=17), A255868 (c=18), A255869 (c=19)

A118119 := proc(n) local k ,g; for k from 1 do g := igcd(k^n+1,(k+1)^n+1) ; if g>1 then return k ; end if; end do: end proc: # R. J. Mathar, Mar 07 2011

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

{ a(n,c=1) = my(f,g); g=gcdext(x^n+c,(x+1)^n+c); f = factor(lcm(denominator(content(g[1])),denominator(content(g[2]))))[,1]; g=[]; for(i=1,#f, g=concat(g, apply(lift, polrootsmod( gcd([x^n+c,(x+1)^n+c]*Mod(1,f[i])), f[i] ) )); );vecmin(g); }  \\ Max Alekseyev, Aug 06 2015

\\ This naive form is typically faster than the polynomial gcd method above. Perhaps a combined algorithm which tries this first before calling the other would be fastest.
a(n)=for(m=2,oo, if(gcd(m^n + 1, (m+1)^n + 1)>1, return(m))) \\ Charles R Greathouse IV, May 08 2024

from itertools import count
from math import gcd
def A118119(n): return next(filter(lambda m:gcd(m**n+1,(m+1)**n+1)>1,count(1))) # Chai Wah Wu, May 08 2024

Edited by Max Alekseyev, Aug 06 2015

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

Original entry on oeis.org

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

M. F. Hasler, Mar 08 2015

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

			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.

Cf. A118119, A255832, A255853-A255869

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}]]

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))}

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

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).

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

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

Original entry on oeis.org

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

M. F. Hasler, Mar 08 2015

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

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

			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.

Cf. A118119, A255832.

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

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 *)

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))}

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

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.

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

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

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

Original entry on oeis.org

1, 0, 2, 1, 48, 9, 1, 19, 14, 1, 2, 77364635, 1, 1943, 2, 1, 5, 299788383228819788, 1, 1578270389554680057141787800241971645032008710129107338825798, 9, 1, 2, 6676, 1, 415, 2, 1, 39, 168338080349, 1, 305, 6806, 1, 2, 9, 1

Offset: 0

M. F. Hasler, Mar 08 2015

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

			For n=1, gcd(k^n+6, (k+1)^n+6) = gcd(k+6, k+7) = 1, therefore a(1)=0.
For n=2, we have gcd(2^2+6, 3^2+6) = gcd(10, 15) = 5, and the pair (k,k+1)=(2,3) is the smallest which yields a gcd > 1, therefore a(2)=2.
For n=3k, see formula.

Cf. A118119, A255832, A255852-A255869

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

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

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

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

a(11)-a(36) from Hiroaki Yamanouchi, Mar 13 2015

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

Original entry on oeis.org

1, 0, 14, 320, 56, 675113, 224, 13, 5, 283, 33, 192, 26, 242, 5, 2, 10, 140, 5, 50, 142, 29, 18, 605962, 11, 97, 234881024, 951, 5, 3332537854, 14

Offset: 0

M. F. Hasler, Mar 08 2015

nonn

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

			For n=0, gcd(k^0+7, (k+1)^0+7) = gcd(8, 8) = 8 for any k > 0, therefore a(0)=1 is the smallest possible positive value.
For n=1, gcd(k^n+7, (k+1)^n+7) = gcd(k+7, k+8) = 1, therefore a(1)=0.
For n=2, we have gcd(14^2+7, 15^2+7) = gcd(203, 232) = 29, and the pair (k,k+1)=(14,15) is the smallest which yields a gcd > 1, therefore a(2)=14.

Hiroaki Yamanouchi, Table of n, a(n) for n = 0..36

Cf. A118119, A255832, A255852-A255869

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

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

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

a(26)-a(36) from Hiroaki Yamanouchi, Mar 12 2015

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

Original entry on oeis.org

1, 0, 1, 5, 1, 5238149, 1, 24747, 1, 5, 1, 1042068640211853141849723, 1, 28913777, 1, 5, 1, 9380, 1, 87940, 1, 5, 1, 677083547, 1, 1584, 1, 5, 1, 5355, 1, 257, 1, 5, 1, 118, 1, 3250, 1, 5, 1, 78609080, 1, 1807714890, 1, 5, 1

Offset: 0

M. F. Hasler, Mar 08 2015

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

			For n=1, gcd(k^n + 8, (k+1)^n + 8) = gcd(k+8, k+9) = 1, therefore a(1)=0.
For n=2*k, see formula.
For n=3, we have gcd(5^3 + 8, 6^3 + 8) = gcd(133, 224) = 7, and the pair (k,k+1)=(5,6) is the smallest which yields a GCD > 1, therefore a(3)=5.

Cf. A118119, A255832, A255852-A255869.

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

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

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

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

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

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

Original entry on oeis.org

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

M. F. Hasler, Mar 08 2015

nonn

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

			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.

Cf. A118119, A255832.

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

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 *)

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))}

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

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

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

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

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

Original entry on oeis.org

1, 0, 1, 5, 1, 533360, 1, 55, 1, 7, 1, 796479131355665831357, 1, 41, 1, 5, 1, 3775, 1, 42296, 1, 7, 1, 653246700175064613889, 1, 21, 1, 5, 1, 1619, 1, 42842, 1, 7, 1, 2945, 1, 323371, 1, 5, 1, 1102221, 1, 633524110177, 1, 7, 1

Offset: 0

M. F. Hasler, Mar 08 2015

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

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

Cf. A118119, A255832.

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

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

a(n,c=5,L=10^7,S=1)->for(a=S,L,gcd(a^n+c,(a+1)^n+c)>1&&return(a))

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

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

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

A255859 Least m > 0 such that gcd(m^n+9,(m+1)^n+9) > 1, or 0 if there is no such m.

Original entry on oeis.org

1, 0, 18, 533, 1, 32, 288, 484, 1, 364, 6, 176427, 1, 31239, 533, 8, 1, 8424432925592889329288197322308900672459420460792433, 30, 16561, 1, 4, 6, 349, 1, 32, 546, 2579, 1, 375766, 11, 5061867704425915, 1, 5620, 6, 8, 1

Offset: 0

M. F. Hasler, Mar 08 2015

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

			For n=1, gcd(m^n+9, (m+1)^n+9) = gcd(m+9, m+10) = 1, therefore a(1)=0.
For n=2, we have gcd(18^2+9, 19^2+9) = gcd(333, 370) = 37, and the pair (m,m+1)=(18,19) is the smallest which yields a GCD > 1, therefore a(2)=37.
For n=4k, see formula.

Will Wei, Patterns that appear to hold, but don't - 8424432925592889329288197322308900672459420460792433, video (2020)

Cf. A118119, A255832, A255852-A255869

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

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

a(4k)=1 for k>=0, because gcd(1^(4k)+9, 2^(4k)+9) = gcd(10, 16^k-1) = 5.

a(17)-a(30) from Hiroaki Yamanouchi, Mar 12 2015

a(31)-a(36) from Max Alekseyev, Aug 06 2015

A255868 Least m > 0 such that gcd(m^n+18, (m+1)^n+18) > 1, or 0 if there is no such m.

Original entry on oeis.org

1, 0, 36, 5, 8, 193801631, 7, 16280817091929, 5, 4, 9216, 815167161742047217904392262, 7, 46, 20, 5, 19, 1837, 1, 224, 8, 7, 56, 13215457, 5, 130689, 221, 4, 5, 1167507, 7, 9708, 65, 7, 20, 63, 1, 4248, 5, 5, 5, 527010, 7

Offset: 0

M. F. Hasler, Mar 09 2015

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

			For n=0, gcd(m^0+18, (m+1)^0+18) = gcd(19, 19) = 19, therefore a(0)=1, the smallest possible (positive) m-value.
For n=1, gcd(m^n+18, (m+1)^n+18) = gcd(m+18, m+19) = 1, therefore a(1)=0.
For n=2, gcd(36^2+18, 37^2+18) = 73 and (m, m+1) = (36, 37) is the smallest pair which yields a GCD > 1 here.

Cf. A118119, A255832, A255852-A255869

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

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

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

cp's OEIS Frontend

A118119 Smallest integer m for which gcd(m^n + 1, (m+1)^n + 1) > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions