cp's OEIS Frontend

A309316 Euler primary pretenders: a(n) is the smallest odd composite k such that n^((k+1)/2) == +-n (mod k).

%I A309316 #39 Jul 25 2019 09:08:29
%S A309316 9,9,341,121,341,15,15,21,9,9,9,33,33,21,15,15,15,9,9,9,15,15,21,33,
%T A309316 15,15,9,9,9,15,15,15,25,33,21,9,9,9,39,15,15,21,21,21,9,9,9,65,21,21,
%U A309316 15,15,39,9,9,9,21,21,57,15,15,15,9,9,9,15,15,33,25,15,15,9,9,9,15,15,15,21,21,39,9,9,9
%N A309316 Euler primary pretenders: a(n) is the smallest odd composite k such that n^((k+1)/2) == +-n (mod k).
%C A309316 Note that if p is an odd prime, then n^((p+1)/2) == +-n (mod p) for all n.
%C A309316 a(n) is the least Euler weak pseudoprime to base n, as A000790(n) is the least Fermat weak pseudoprime to base n.
%C A309316 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.
%C A309316 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.
%C A309316 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.
%C A309316 Problem: is P the fundamental period of this sequence?
%C A309316 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
%F A309316 a(n) = 9 if and only if n == {-1,0,1} (mod 9).
%F A309316 a(n + P) = a(n), where the period P = 41#*571#/4.
%e A309316 a(2) = 341 since 2^((341+1)/2) = 2^171 == 2 (mod 341) and 341 is the smallest odd composite number satisfying this congruence.
%e A309316 a(5) = 15 since 5^((15+1)/2) = 5^8 == -5 (mod 15) and 15 is the smallest odd composite number with this property.
%e A309316 a(8) = 9 since 8^((9+1)/2) = 8^5 == 8 (mod 9) and 9 is the smallest odd composite number.
%p A309316 f:= proc(n) local k,r;
%p A309316   for k from 9 by 2 do
%p A309316     if isprime(k) then next fi;
%p A309316     r:= n &^ ((k+1)/2) mod k;
%p A309316     if r = (n mod k) or r = (-n mod k) then return k fi
%p A309316   od
%p A309316 end proc:
%p A309316 map(f, [$0..100]); # _Robert Israel_, Jul 23 2019
%t A309316 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 *)
%Y A309316 Cf. A000790, A033181, A108574.
%K A309316 nonn
%O A309316 0,1
%A A309316 _Thomas Ordowski_, Jul 23 2019
%E A309316 More terms from _Amiram Eldar_, Jul 23 2019