cp's OEIS Frontend

A367688 Number of primes p such that x^n + y^n mod p does not take all values on Z/pZ.

%I A367688 #27 May 18 2024 13:40:56
%S A367688 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,
%T A367688 53,49,87,26,130,27,85,56,69,56,170,36,74,68,140,40,175,43,124,105,91,
%U A367688 45,215,55,149,87,142,48,209,83,185,96,119,57,339,59,128,133
%N A367688 Number of primes p such that x^n + y^n mod p does not take all values on Z/pZ.
%C A367688 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.
%H A367688 MathOverflow, <a href="https://mathoverflow.net/questions/356270">Does the expression x^4+y^4 take on all values in Z/pZ?</a>
%e A367688 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.
%e A367688 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.
%e A367688 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.
%o A367688 (Sage)
%o A367688 def a(n):
%o A367688     ans = 0
%o A367688     for p in prime_range(1, n^4):
%o A367688         nth_powers = set([power_mod(x,n,p) for x in range(p)])
%o A367688         for k in range(p):
%o A367688             for xn in nth_powers:
%o A367688                 if (k-xn)%p in nth_powers: break
%o A367688             else: ans += 1; break
%o A367688     return ans
%o A367688 (Sage)  # This is very slow for n larger than 7
%o A367688 def a(n):
%o A367688     ans = 0
%o A367688     for p in prime_range(1,n^4):
%o A367688         all_values = set()
%o A367688         for x in range(p):
%o A367688             for y in range(p):
%o A367688                 all_values.add((x^n+y^n)%p)
%o A367688         if len(all_values) < p: ans += 1
%o A367688     return ans
%o A367688 (Python)
%o A367688 from itertools import combinations_with_replacement
%o A367688 from sympy import sieve
%o A367688 def A367688(n):
%o A367688     c = 0
%o A367688     for p in sieve.primerange(n**4+1):
%o A367688         s = set()
%o A367688         for k in combinations_with_replacement({pow(x,n,p) for x in range(p)},2):
%o A367688             s.add(sum(k)%p)
%o A367688             if len(s) == p:
%o A367688                 break
%o A367688         else:
%o A367688             c += 1
%o A367688     return c # _Chai Wah Wu_, Nov 27 2023
%Y A367688 Cf. A355920, A367689.
%K A367688 nonn
%O A367688 1,4
%A A367688 _Robin Visser_, Nov 26 2023
%E A367688 a(36)-a(63) from _Jason Yuen_, May 18 2024