cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A367689 Smallest prime number p such that x^n + y^n mod p does not take all values on Z/pZ.

Original entry on oeis.org

7, 5, 11, 7, 29, 5, 7, 11, 23, 5, 53, 29, 7, 5, 103, 7, 191, 5, 7, 23, 47, 5, 11, 53, 7, 5, 59, 7, 311, 5, 7, 103, 11, 5, 149, 191, 7, 5, 83, 7, 173, 5, 7, 47, 283, 5, 29, 11, 7, 5, 107, 7, 11, 5, 7, 59, 709, 5, 367, 311, 7, 5, 11, 7, 269, 5, 7, 11, 569, 5, 293, 149, 7, 5, 23, 7, 317, 5
Offset: 3

Views

Author

Robin Visser, Nov 26 2023

Keywords

Comments

If there exists some prime p > 3 such that p-1 divides n, then x^n (mod p) is either 0 or 1 for all integers x, therefore giving an upper bound of a(n) <= p.

Examples

			For n = 3, x^3 + y^3 attains all values on Z/2Z, Z/3Z, and Z/5Z, but x^3 + y^3 == 3 (mod 7) has no solution, so a(3) = 7.
For n = 4, x^4 + y^4 attains all values on Z/2Z and Z/3Z, but x^4 + y^4 == 3 (mod 5) has no solution, so a(4) = 5.

Links

Crossrefs

Cf. A355920, A367688.

Programs

  • PARI
    a(n) = my(p=2); while (#setbinop((x,y)->Mod(x,p)^n+Mod(y,p)^n, [0..p-1]) == p, p=nextprime(p+1)); p; \\ Michel Marcus, Nov 27 2023
  • Python
    from itertools import combinations_with_replacement
from sympy import sieve
def A367689(n):
    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:
            return p # Chai Wah Wu, Nov 27 2023
  • Sage
    def a(n):
    for p in Primes():
        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: return p

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

Original entry on oeis.org

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

Views

Author

Robin Visser, Nov 26 2023

Keywords

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.

Examples

			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.

Links

Crossrefs

Cf. A355920, A367689.

Programs

  • 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
  • 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

Extensions

a(36)-a(63) from Jason Yuen, May 18 2024

A371670 Largest prime number p such that x^n + y^n + z^n mod p does not take all values on Z/pZ.

Original entry on oeis.org

5, 11, 31, 43, 41, 37, 61, 89, 229, 79, 127, 61, 257, 137, 397, 419, 521, 337, 463, 277, 577, 251, 599, 541, 617, 349, 661, 373, 769, 727, 953, 631, 1117, 593, 761, 1483, 761, 739, 1597, 1033, 1409, 1171, 1289, 1693, 2113, 883, 1301, 1327, 2861, 1697, 2269, 1871, 2633, 1483, 2089, 2243, 2221, 1709, 1861, 2143
Offset: 4

Views

Author

Robin Visser, Apr 02 2024

Keywords

Comments

a(n) is well-defined for all n >= 4, following a similar discussion given in A355920. Indeed for any integer k, by fibering the surface C : x^n + y^n + z^n == k (mod p) into curves and applying the Hasse-Weil bound, we obtain that the number of points N on C must satisfy |N - p(p+1)| <= 2*g*p*sqrt(p), where g = (n-1)(n-2)/2 is the genus of the Fermat curve x^n + y^n = 1. Thus, N is nonzero if p+1 > (n-1)(n-2)*sqrt(p). In particular, x^n + y^n + z^n mod p takes all values on Z/pZ for all primes p > n^4.
a(n) <= A355920(n). - Jason Yuen, May 30 2024

Examples

			For n = 4, the equation x^4 + y^4 + z^4 == 4 (mod 5) does not have a solution, but x^4 + y^4 + z^4 == k (mod p) does have a solution for any integer k and prime p greater than 5, thus a(4) = 5.
For n = 5, the equation x^5 + y^5 + z^5 == 4 (mod 11) does not have a solution, but x^5 + y^5 + z^5 == k (mod p) does have a solution for any integer k and prime p greater than 11, thus a(5) = 11.

Links

Crossrefs

Cf. A355920, A368055.

Programs

  • Python
    from itertools import combinations_with_replacement
from sympy import prevprime
def A371670(n):
    p = n**4
    while (p:=prevprime(p)):
        pset = set(q:=tuple(pow(x,n,p) for x in range(p)))
        if not all(any((k-a[0]-a[1])%p in pset for a in combinations_with_replacement(q,2)) for k in range(p)):
            return p # Chai Wah Wu, Apr 04 2024
  • SageMath
    def a(n):
    p = Integer(n^4).previous_prime()
    while True:
        nth_powers = set([power_mod(x, n, p) for x in range(p)])
        for k in range(p):
            for xn, yn in ((x,y) for x in nth_powers for y in nth_powers):
                if (k-xn-yn)%p in nth_powers: break
            else: return p
        p = p.previous_prime()

Extensions

a(36)-a(63) from Jason Yuen, May 30 2024
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.