cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

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

Original entry on oeis.org

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

Views

Author

Adam Kertesz, May 12 2006; May 13 2006

Keywords

Comments

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

Examples

			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.

Links

Crossrefs

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)

Programs

  • Maple
    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
  • Mathematica
    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 *)
  • PARI
    { 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
  • PARI
    \\ 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
  • Python
    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

Extensions

Edited 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

Views

Author

M. F. Hasler, Mar 08 2015

Keywords

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

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

Views

Author

M. F. Hasler, Mar 08 2015

Keywords

Comments

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

Examples

			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.

Crossrefs

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

Programs

  • Mathematica
    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}]]
  • PARI
    a(n,c=5,L=10^7,S=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 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

Formula

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

Extensions

a(11)-a(46) from Hiroaki Yamanouchi, Mar 12 2015
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.