A338136 a(n) is the least k >= 2 such that (n+1)^k mod n^j is a perfect power > 1 for some j >= 2 with n^j < (n+1)^k.

6, 4, 2, 3, 4, 3, 3, 7, 8, 9, 2, 2, 10, 8, 3, 15, 16, 17, 4, 3, 11, 21, 2, 23, 20, 25, 6, 27, 4, 4, 7, 3, 32, 24, 4, 27, 9, 5, 2, 39, 4, 5, 10, 8, 44, 45, 6, 47, 48, 5, 12, 51, 52, 8, 3, 6, 56

Offset

2,1

Comments

a(n) <= n-2 for n >= 4, because (n+1)^(n-2) == (n-1)^2 (mod n^2).

If 2*n+1 is a perfect power, a(n) = 2.

Is there a characterization of the numbers n where a(n) = n-2? Conjecture I: if n <> 7 is a safe prime (A005385), then a(n) = n-2. Conjecture II: if n <> 22, n <> 1822 and n+1 is a safe prime, then a(n) = n-2. - Chai Wah Wu, Oct 13 2020

If n is in the sequence with recurrence b(n+2) = 98*b(n+1)-b(n)+32, b(0)=0, b(1)=36, then (n+1)^4 mod n^3 = 1 + 4*n + 6*n^2 is a square, so a(n) <= 4. - Robert Israel, Oct 14 2020

Links

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

Formula

(n+1)^a(n) mod n^A338150(n) = A338151(n).

Example

a(2) = 6 because 3^6 mod 2^4 = 3^2.
a(13) = 2 because 14^2 mod 13^2 = 3^3.

Maple

f:= proc(n) local k, x, j, F;
  for k from 2 to n-2 do
   x:= (n+1)^k;
    for j from 2 to floor(k*log[n](n+1)) do
     F:= ifactors(x mod (n^j))[2];
     if igcd(op(map(t -> t[2], F))) > 1 then return k fi
  od od
end proc:
f(2):= 6: f(3):= 4:
map(f, [$2..40]);

Mathematica

f[n_] := Module[{k, x, j, F}, For[k = 2, k <= n-2, k++, x = (n+1)^k; For[j = 2, j <= Floor[k*Log[n, n+1]], j++, F = FactorInteger[Mod[x, n^j]]; If[GCD@@F[[All, 2]] > 1, Return[k] ]]]];
f[2] = 6; f[3] = 4;
Map[f, Range[2, 40]] (* Jean-François Alcover, May 28 2023, after Maple program *)

Prog

(Python)
from gmpy2 import is_power
def A338136(n):
    k, n2, m = 2,  n**2, (n+1)**2
    while True:
        j, nj = 2, n2
        while nj < m:
            r = m % nj
            if r > 1 and is_power(r):
                return k
            nj *= n
        k += 1
        m *= n+1 # Chai Wah Wu, Oct 13 2020

Crossrefs

Cf. A338150, A338151.

Sequence in context: A199741 A125214 A114062 * A028975 A145011 A173625

Adjacent sequences: A338133 A338134 A338135 * A338137 A338138 A338139

Keyword

nonn

Author

J. M. Bergot and Robert Israel, Oct 12 2020

Status

approved