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

A010034 Numbers k such that gcd(k^17 + 9, (k+1)^17 + 9) > 1.

Original entry on oeis.org

8424432925592889329288197322308900672459420460792433, 17361015163508605989239159575667846308252873717727992, 26297597401424322649190121829026791944046326974663551, 35234179639340039309141084082385737579839780231599110

Offset: 1

Ilan Vardi, Stan Wagon

In other words, let f(n) = gcd(n^17 + 9, (n+1)^17 + 9). Then f(n) = 1 for all n <= 8424432925592889329288197322308900672459420460792432, but f(8424432925592889329288197322308900672459420460792433) > 1.

In fact f(8424432925592889329288197322308900672459420460792433) = 8936582237915716659950962253358945635793453256935559.

M. F. Hasler, Table of n, a(n) for n = 1..100
Tanya Khovanova, Recursive Sequences
Stan Wagon, Macalester College Problem of the week # 805, MacPOW archive on MathForum.org. Spring 1996.
Péter E. Frenkel, József Pelikán, On the greatest common divisor of the value of two polynomials, Amer. Math. Monthly 124:5 (2017), 446-450. arXiv:1608.07936 [math.NT]
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A118119, A255859.

Table[8424432925592889329288197322308900672459420460792433+ 8936582237915716659950962253358945635793453256935559(n-1),{n,5}] (* or *) LinearRecurrence[{2,-1},{8424432925592889329288197322308900672459420460792433,17361015163508605989239159575667846308252873717727992},5] (* Harvey P. Dale, Jun 12 2014 *)

A010034(n)=8936582237915716659950962253358945635793453256935559*n-512149312322827330662764931050044963334032796143126 \\ M. F. Hasler, Mar 17 2015

\\ The values (a(1),p) can also be found using:
{p=polresultant(x^17+9,(x+1)^17+9);s=vector(2,i,Mod(-9,p)^(1/17));(u=s[2]/s[1])!=1&&until(setsearch(Set(s=concat(s,s[#s]*u)),s[#s]+1),)}
\\ Then the last element s[#s] equals Mod(a(1),p). - M. F. Hasler, Mar 26 2015

a(n) = 8424432925592889329288197322308900672459420460792433 + 8936582237915716659950962253358945635793453256935559*(n-1). - Max Alekseyev, Jul 26 2009

a(1) = A255859(17). - M. F. Hasler, Mar 17 2015

More terms from Max Alekseyev, Jul 26 2009

A255831 Square array A(m,n) = Resultant(X^m+n,(X+1)^m+n), read by (falling) antidiagonals, m >= 1, n >= 0.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 9, 28, 1, 1, 13, 109, 153, 1, 1, 17, 244, 1617, 3751, 1, 1, 21, 433, 5929, 52501, 175760, 1, 1, 25, 676, 14625, 258751, 3261249, 6835648, 1, 1, 29, 973, 29241, 810001, 19763200, 148756357, 1051779953, 1, 1, 33, 1324, 51313, 1968751, 73559825, 1086478912, 23937893793, 364668913756, 1

Offset: 0

M. F. Hasler, Mar 17 2015

This polynomial resultant gives the period for solutions to the equations A255852 - A255869. For example, A010034(n) = A255859(17) + A(17,9)*(n-1). In general, there may be more than one starting solutions (cf. A118119).

			The square array starts at its upper left as follows:
[ 1      1       1        1        1         1         1 ... ]
[ 1      5       9       13       17        21        25 ... ]
[ 1     28     109      244      433       676       973 ... ]
[ 1    153    1617     5929    14625     29241     51313 ... ]
[ 1   3751   52501   258751   810001   1968751   4072501 ... ]
[ 1 175760 3261249 19763200 73559825 207499536 488999665 ... ]
[ :     :       :        :        :         :         :  ·.  ]
[ :     :       :        :        :         :         :    ·.]

A255831(m,n)=polresultant('x^m+n,('x+1)^m+n)

from sympy import resultant
from sympy.abc import x
def A255831_T(m,n): return resultant(x**m+n,(x+1)**m+n) # Chai Wah Wu, May 08 2024

Edited by Max Alekseyev, Aug 07 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

A010034 Numbers k such that gcd(k^17 + 9, (k+1)^17 + 9) > 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A255831 Square array A(m,n) = Resultant(X^m+n,(X+1)^m+n), read by (falling) antidiagonals, m >= 1, n >= 0.

Views

Author

Keywords

Comments

Examples

Programs

PARI

Python

Extensions