

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
Note that a(n) >= A000790(n).  Thomas Ordowski, Feb 16 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

Robert Israel, Table of n, a(n) for n = 1..10000
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).
For prime p, a(p) = A000790(p).  Max Alekseyev, Feb 27 2018


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:
map(f, [$1..100]); # Robert Israel, Feb 14 2018


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

Cf. A000790, A002808, A002997, A007947, A108574.
Sequence in context: A214161 A265868 A239293 * A090086 A007535 A000783
Adjacent sequences: A295994 A295995 A295996 * A295998 A295999 A296000


KEYWORD

nonn


AUTHOR

Thomas Ordowski, Feb 14 2018


EXTENSIONS

More terms from Rémy Sigrist, Feb 14 2018


STATUS

approved



