OFFSET
0,1
COMMENTS
Note that if p is an odd prime, then n^((p+1)/2) == +-n (mod p) for all n.
a(n) is the least Euler weak pseudoprime to base n, as A000790(n) is the least Fermat weak pseudoprime to base n.
This sequence is bounded, namely a(n) <= 1729, the smallest absolute Euler pseudoprime, because n^((1729+1)/2) == n (mod 1729) for every n, see A033181.
The set A = {a(n)} of terms contains all odd semiprimes pq < 1729 such that p-1 | q-1. Other numbers in the set are 561, 645, 1065, 1247, and 1729. Probably complete. Cf. A108574.
This sequence is periodic with a very long period P = LCM(A) = p#*q#/2^2, where p and q are the largest primes such that p^2 < 1729 and 3q < 1729. Such primes are p = 41 and q = 571, so the period P = 41#*571#/4 (248 digits) is much longer than period of the (Fermat) primary pretenders.
Problem: is P the fundamental period of this sequence?
Records of a(n) are 9, 341, 561, 703, 793, 1145, 1263, 1477, and 1729; for n = 0, 2, 383, 1822, 3308, 4702, 10103, 12252, and 21821. - Amiram Eldar, Jul 24 2019
FORMULA
a(n) = 9 if and only if n == {-1,0,1} (mod 9).
a(n + P) = a(n), where the period P = 41#*571#/4.
EXAMPLE
a(2) = 341 since 2^((341+1)/2) = 2^171 == 2 (mod 341) and 341 is the smallest odd composite number satisfying this congruence.
a(5) = 15 since 5^((15+1)/2) = 5^8 == -5 (mod 15) and 15 is the smallest odd composite number with this property.
a(8) = 9 since 8^((9+1)/2) = 8^5 == 8 (mod 9) and 9 is the smallest odd composite number.
MAPLE
f:= proc(n) local k, r;
for k from 9 by 2 do
if isprime(k) then next fi;
r:= n &^ ((k+1)/2) mod k;
if r = (n mod k) or r = (-n mod k) then return k fi
od
end proc:
map(f, [$0..100]); # Robert Israel, Jul 23 2019
MATHEMATICA
a[n_] := Module[{k=9}, While[!CompositeQ[k] || ((m = PowerMod[n, (k+1)/2, k]) != Mod[n, k] && m != Mod[-n, k]), k+=2]; k]; Array[a, 100, 0] (* Amiram Eldar, Jul 23 2019 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Ordowski, Jul 23 2019
EXTENSIONS
More terms from Amiram Eldar, Jul 23 2019
STATUS
approved