%I #56 Mar 19 2024 21:00:28
%S 7,29,61,223,127,761,307,911,617,1741,1171,2927,3181,2593,1667,4519,
%T 2927,10781,5167,6491,8419,7177,5501,7307,9829,11117,12703,20011,
%U 10789,13249,18217,22271,14771,29629,13691,18773,22543,21601,19927,46411,18749,32957,35281,67391,34499,63601,32341
%N Largest prime number p such that x^n + y^n mod p does not take all values on Z/pZ.
%C As discussed in the link below, the Hasse-Weil bound assures that x^n + y^n == k (mod p) always has a solution when p - 1 - 2*g*sqrt(p) > n, where g = (n-1)*(n-2)/2 is the genus of the Fermat curve. For example, p > n^4 is large enough to satisfy this condition, so we only need to check finitely many p below n^4.
%H MathOverflow, <a href="https://mathoverflow.net/questions/356270">Does the expression x^4+y^4 take on all values in Z/pZ?</a>
%H Azuma Seiichi, <a href="https://colab.research.google.com/drive/1LzZa-uf0U2clOW_reov1iXwZuZSMetym?usp=sharing">Python code for calculating a(n) (Google Colab)</a>
%e a(3) = 7 because x^3 + y^3 == 3 (mod 7) does not have a solution, but x^3 + y^3 == k (mod p) always has a solution when p is a prime greater than 7.
%o (Python)
%o import sympy
%o def a(n):
%o g = (n - 1) * (n - 2) / 2
%o plist = list(sympy.primerange(2, n ** 4))
%o plist.reverse()
%o for p in plist:
%o # equivalent to p-1-2*g*p**0.5 > n:
%o if (p - 1 - n) ** 2 > 4 * g * g * p:
%o continue
%o solution = [False] * p
%o r = sympy.primitive_root(p)
%o rn = r ** n % p # generator for subgroup {x^n}
%o d = sympy.n_order(rn, p) # size of subgroup {x^n}
%o nth_power_list = []
%o xn = 1
%o for k in range(d):
%o xn = xn * rn % p
%o nth_power_list.append(xn)
%o for yn in nth_power_list:
%o solution[(xn + yn) % p] = True
%o for yn in nth_power_list: # consider the case x=0
%o solution[yn] = True
%o solution[0] = True
%o if False in solution:
%o return p
%o return -1
%o print([a(n) for n in range(3, 18)])
%Y Cf. A289559.
%K nonn
%O 3,1
%A _Azuma Seiichi_, Jul 21 2022
%E a(13)-a(25) from _Jinyuan Wang_, Jul 22 2022
%E a(26)-a(27) from _Chai Wah Wu_, Sep 13 2022
%E a(28)-a(33) from _Chai Wah Wu_, Sep 14 2022
%E a(34)-a(40) from _Robin Visser_, Dec 09 2023
%E a(41)-a(49) from _Robin Visser_, Mar 18 2024
|