A316940 Smallest "anti-Carmichael pseudoprime" to base n.

35, 7957, 16531, 1247, 17767, 35, 817, 2501, 697, 4141, 2257, 143, 9577, 2257, 4187, 1247, 3991, 221, 7957, 2059, 55, 161, 1027, 115, 403, 475, 247, 4553, 35, 247, 6289, 697, 1853, 35, 1247, 35, 589, 221, 95, 533, 35, 559, 77, 215, 253, 235, 221, 329, 247, 119

Offset

1,1

Comments

a(n) is the smallest k such that n^(k-1) == 1 (mod k) and p-1 does not divide k-1 for every prime p dividing k.

All listed terms are semiprime and squarefree, except a(26) = 475 = 5^2*19.

Links

Amiram Eldar, Table of n, a(n) for n = 1..10000

Mathematica

Table[Block[{k = 2}, While[Nand[PowerMod[n, k - 1, k] == 1, AllTrue[FactorInteger[k][[All, 1]] - 1, Mod[k - 1, #] != 0 &]], k++]; k], {n, 50}] (* Michael De Vlieger, Jul 20 2018 *)

Prog

(PARI) isok(k, n) = {if (!isprime(k) && Mod(n, k)^(k-1) == 1, f = factor(k)[, 1]; for (j=1, #f~, if (!((k-1) % (f[j]-1)), return (0)); ); return (1); ); return (0); }
a(n) = {my(k=2); while(!isok(k, n), k++); k; } \\ Michel Marcus, Jul 17 2018

Crossrefs

Cf. A121707 (probably "anti-Carmichael numbers": n such that p-1 does not divide n-1 for every prime p dividing n).

Cf. A316907 ("anti-Carmichael pseudoprimes" to base 2).

Sequence in context: A224126 A249888 A212025 * A202066 A271071 A249889

Adjacent sequences: A316937 A316938 A316939 * A316941 A316942 A316943

Keyword

nonn

Author

Thomas Ordowski, Jul 17 2018

Extensions

More terms from Michel Marcus, Jul 17 2018

Status

approved