A255853 -id:A255853 - 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

A255832 Least m > 0 such that gcd(m^(2n+1)+2, (m+1)^(2n+1)+2) > 1.

Original entry on oeis.org

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

Offset: 1

M. F. Hasler, Mar 08 2015

For n=0 one has gcd(m+2, m+3) = 1 for any m.
See A255852 for the sequence including also even exponents, for which the GCD is > 1 already for m=1 (because gcd(1^2k+2, 2^2k+2) = gcd(3, 2^2k-1) = gcd(3, 4^k-1) = 3), and also for m=4 (because gcd(4^2k+2, 5^2k+2) = gcd(4^2k+2, (5^k-4^k)(5^k+4^k)) >= 3), etc.
a(21) = 3585, a(22) = 5, a(25) = 16, a(28) = 22, a(29) = 4495, a(31) = 1291, a(32) = 108, a(33) = 220, a(34) = 218039, a(35) = 2112. - Chai Wah Wu, May 08 2024

Cf. A118119, A255853, A255853, ... for other variants, corresponding to different constant offsets (+1, +3, ...) in the arguments of gcd.

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

a(n,c=2,L=10^6)={n=n*2+1;for(a=1,L,gcd(a^n+c,(a+1)^n+c)>1&&return(n))}

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

a(n) = A255852(2n+1).

a(12)-a(18) 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

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

A255832 Least m > 0 such that gcd(m^(2n+1)+2, (m+1)^(2n+1)+2) > 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions