A367576 -id:A367576 - cp's OEIS frontend

A367566 a(n) is the product of the primes p <= n+1 such that n * k^n == +-1 (mod p) for every k that is not a multiple of p.

2, 3, 2, 15, 6, 35, 6, 3, 2, 33, 6, 13, 6, 15, 14, 255, 6, 19, 6, 3, 2, 69, 6, 5, 6, 15, 14, 87, 6, 31, 6, 3, 2, 15, 6, 1295, 6, 3, 2, 123, 6, 43, 6, 15, 22, 705, 6, 7, 6, 3, 2, 159, 6, 5, 6, 15, 14, 177, 6, 61, 6, 3, 2, 15, 66, 4355, 6, 3, 14, 213, 6, 73, 6

Offset: 1

Jon E. Schoenfield, Nov 23 2023

nonn

By definition, all terms are squarefree. However, not all squarefree numbers are present.
a(n) = 1 first occurs at n = 252.
If n+1 = p is a prime, then for every k that is not a multiple of p, k^n == 1 (mod p), so n * k^n == -1 (mod p), so p divides a(n).
a(n) is even iff n is odd; 3 | a(n) iff 3 !| n and n > 1; and for primes p > 3, p | a(n) iff n == +-(p-1) (mod p*(p-1)/2). It follows that no term is divisible by q*r where q and r are primes and 2*q | r-1.
If A239735(n) > 1 then a(n) divides A239735(n); this can make it practical to find large terms of A239735. E.g., A239735(46) = 15044700, but since a(46) = 705 (see Example section), only the first 15044700/705 = 21340 multiples of 705 need to be tested. (Additionally, almost 90% of those multiples can be quickly ruled out by testing whether (46 * k^46) mod q = 1 or q-1 for any prime q < 2500, leaving fewer than 2200 remaining numbers k for which to test whether 46 * k^46 - 1 and 46 * k^46 + 1 are probable primes.)

			For n = 46, n+1 = 47 is a prime, so 46 * k^46 == -1 (mod p) for every k that is not a multiple of 47, so 47 divides a(46). Additionally, 46 * k^46 == 1 (mod 3) if k !== 0 (mod 3), so 3 divides a(46), and 46 * k^46 == +-1 (mod 5) if k !== 0 (mod 5), so 5 also divides a(46). Since 3, 5, and 47 are the only primes p such that 46 * k^46 == +-1 (mod p) for all k !== 0 (mod p), a(46) = 3*5*47 = 705.

Jon E. Schoenfield, Table of n, a(n) for n = 1..10000
Jon E. Schoenfield, Magma program.

Cf. A000040, A239735, A367576.

from math import prod
from sympy import primerange
def A367566(n): return prod(p for p in primerange(n+2) if all((m:=n*pow(k,n,p)%p)==1 or m==p-1 for k in range(1,p))) # Chai Wah Wu, Nov 24 2023

A367577 a(n) is the first k such that A367566(k) = n, or -1 if no such k exists.

Original entry on oeis.org

252, 1, 2, -1, 24, 5, 48, -1, -1, -1, 450, -1, 12, 15, 4, -1, 1512, -1, 18, -1, -1, 45, 8118, -1, -1, -1, -1, -1, 840, -1, 30, -1, 10, -1, 6, -1, 1368, 189, -1, -1, 1680, -1, 42, -1, -1, 231, 2208, -1, -1, -1, 152, -1, 6942, -1, -1, -1, -1, -1, 27318, -1, 60

Offset: 1

Jon E. Schoenfield, Nov 24 2023

sign

a(n) = -1 iff n is nonsquarefree or is divisible by some term in A367576.

			a(1) = 252 because 1 first appears as a term in A367566 at A367566(252).
a(4) = -1 because 4 = 2^2 is nonsquarefree so it never appears in A367566.
a(10) = -1 because 10 is a term in A367576.
a(42) = -1 because 21 divides 42, and 21 is a term in A367576.

Cf. A367566, A367576.

cp's OEIS Frontend

A367566 a(n) is the product of the primes p <= n+1 such that n * k^n == +-1 (mod p) for every k that is not a multiple of p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python