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

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

Offset: 1

Author

Thomas Ordowski, Feb 14 2018

Keywords

• nonn

Comments

a(n) is the smallest weak pseudoprime k to all natural bases d|n.

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 p|n (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 Conway-Guy-Schneeberger-Sloane (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), 307-313.

Crossrefs

Cf. A000790, A002808, A002997, A007947, A108574.

Programs

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 *)

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

Formula

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

For prime p, a(p) = A000790(p). - Max Alekseyev, Feb 27 2018

Extensions

More terms from Rémy Sigrist, Feb 14 2018