login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A367688
Number of primes p such that x^n + y^n mod p does not take all values on Z/pZ.
2
0, 0, 1, 4, 4, 13, 5, 14, 11, 24, 9, 42, 14, 30, 26, 37, 17, 54, 17, 63, 33, 43, 25, 104, 31, 53, 49, 87, 26, 130, 27, 85, 56, 69, 56, 170, 36, 74, 68, 140, 40, 175, 43, 124, 105, 91, 45, 215, 55, 149, 87, 142, 48, 209, 83, 185, 96, 119, 57, 339, 59, 128, 133
OFFSET
1,4
COMMENTS
a(n) is finite for all positive integers n by the Hasse-Weil bound. Indeed, for any integer k, the number of solutions N to x^n + y^n == k (mod p) satisfies |N - (p+1)| <= 2*g*sqrt(p) where g = (n-1)(n-2)/2 is the genus of the Fermat curve X^n + Y^n = kZ^n. Thus, N is nonzero if p+1 > (n-1)(n-2)*sqrt(p). In particular, x^n + y^n mod p takes all values on Z/pZ for all primes p > n^4.
EXAMPLE
For n = 1, the equation x + y == k (mod p) always has a solution for any integer k and prime p, so a(1) = 0.
For n = 2, the equation x^2 + y^2 == k (mod p) always has a solution for any integer k and prime p, so a(2) = 0.
For n = 3, the equation x^3 + y^3 == 3 (mod 7) does not have a solution, but x^3 + y^3 == k (mod p) does have a solution for any integer k and prime p not equal to 7, thus a(3) = 1.
PROG
(Sage)
def a(n):
ans = 0
for p in prime_range(1, n^4):
nth_powers = set([power_mod(x, n, p) for x in range(p)])
for k in range(p):
for xn in nth_powers:
if (k-xn)%p in nth_powers: break
else: ans += 1; break
return ans
(Sage) # This is very slow for n larger than 7
def a(n):
ans = 0
for p in prime_range(1, n^4):
all_values = set()
for x in range(p):
for y in range(p):
all_values.add((x^n+y^n)%p)
if len(all_values) < p: ans += 1
return ans
(Python)
from itertools import combinations_with_replacement
from sympy import sieve
def A367688(n):
c = 0
for p in sieve.primerange(n**4+1):
s = set()
for k in combinations_with_replacement({pow(x, n, p) for x in range(p)}, 2):
s.add(sum(k)%p)
if len(s) == p:
break
else:
c += 1
return c # Chai Wah Wu, Nov 27 2023
CROSSREFS
Sequence in context: A183362 A353615 A088838 * A127403 A276423 A052993
KEYWORD
nonn
AUTHOR
Robin Visser, Nov 26 2023
EXTENSIONS
a(36)-a(63) from Jason Yuen, May 18 2024
STATUS
approved