login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 17:01 EDT 2021. Contains 343050 sequences. (Running on oeis4.)