

A295997


Least composite k such that d^k == d (mod k) for every divisor d of n.


3



4, 341, 6, 341, 4, 561, 6, 341, 6, 561, 10, 561, 4, 561, 561, 341, 4, 561, 6, 561, 6, 561, 22, 561, 4, 561, 6, 561, 4, 561, 6, 341, 561, 561, 561, 561, 4, 561, 6, 561, 4, 561, 6, 561, 561, 341, 46, 561, 6, 561, 91, 561, 4, 561, 10, 561, 6, 341, 15, 561, 4, 341
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

a(n) is the smallest weak pseudoprime k to all natural bases dn.
For n > 1, a(n) is the smallest composite k such that p^k == p (mod k) for every prime p dividing n; so a(n) is the smallest weak pseudoprime k to all prime bases pn (thus it is enough to check this congruence only for all prime divisors p of n, see the second program in PARI).
For n > 1, a(n) = 4 iff n has all prime divisors p == 1 (mod 4).
The sequence is bounded, namely 4 <= a(n) <= 561, see A002997.
All members of A108574 appear in the sequence. The last to appear is 538 = a(8110351).  Robert Israel, Feb 15 2018
Conjecture: all distinct terms of the sequence are A108574.  Robert Israel and Thomas Ordowski, Feb 16 2018. The conjecture is true and can be established computationally, like in ConwayGuySchneebergerSloane (1997) paper.  Max Alekseyev, Feb 27 2018
The sequence is not eventually periodic: e.g., any arithmetic progression contains infinitely many terms divisible by a prime == 3 (mod 4), and thus with a(n) > 4, while on the other hand there are infinitely many terms with a(n) = 4.  Robert Israel, Feb 16 2018


LINKS

J. H. Conway, R. K. Guy, W. A. Schneeberger, and N. J. A. Sloane, The Primary Pretenders, Acta Arith. 78 (1997), 307313.


FORMULA

a(n) = a(rad(n)), where rad(n) = A007947(n).


MAPLE

f := n > g(map(t > t[1], ifactors(n)[2])):
g:= proc (P) local k; option remember;
for k from 4 do
if not isprime(k) and andmap(p > (p &^ k  p mod k = 0), P)
then return k
end if
end do
end proc:


MATHEMATICA

With[{c = Table[FixedPoint[n + PrimePi@ # + 1 &, n + PrimePi@ n + 1], {n, 561}]}, Table[With[{d = Divisors@ n}, SelectFirst[c, Function[k, AllTrue[d, PowerMod[#, k, k] == Mod[#, k] &]]]], {n, 62}]] (* Michael De Vlieger, Feb 17 2018, after Robert G. Wilson v at A066277 *)


PROG

(PARI) a(n) = forcomposite(k=1, , my (ok=1); fordiv (n, d, if (Mod(d, k)!=Mod(d, k)^k, ok=0; break)); if (ok, return (k))); \\ Rémy Sigrist, Feb 14 2018
(PARI) a(n)=my(f=factor(n)[, 1], p); forcomposite(k=4, 561, for(i=1, #f, p=f[i]; if(Mod(p, k)^k!=p, next(2))); return(k)); \\ Charles R Greathouse IV, Feb 14 2018


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



