A367566 - OEIS

%I #39 Nov 25 2023 03:53:54

%S 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,

%T 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,

%U 15,14,177,6,61,6,3,2,15,66,4355,6,3,14,213,6,73,6

%N 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.

%C By definition, all terms are squarefree. However, not all squarefree numbers are present.

%C a(n) = 1 first occurs at n = 252.

%C 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).

%C 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.

%C 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.)

%H Jon E. Schoenfield, <a href="/A367566/b367566.txt">Table of n, a(n) for n = 1..10000</a>

%H Jon E. Schoenfield, <a href="/A367566/a367566.txt">Magma program</a>.

%e 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.

%o (Python)

%o from math import prod

%o from sympy import primerange

%o 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

%Y Cf. A000040, A239735, A367576.

%K nonn

%O 1,1

%A _Jon E. Schoenfield_, Nov 23 2023