cp's OEIS Frontend

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

%I A295997 #73 Jun 25 2021 23:38:18
%S A295997 4,341,6,341,4,561,6,341,6,561,10,561,4,561,561,341,4,561,6,561,6,561,
%T A295997 22,561,4,561,6,561,4,561,6,341,561,561,561,561,4,561,6,561,4,561,6,
%U A295997 561,561,341,46,561,6,561,91,561,4,561,10,561,6,341,15,561,4,341
%N A295997 Least composite k such that d^k == d (mod k) for every divisor d of n.
%C A295997 a(n) is the smallest weak pseudoprime k to all natural bases d|n.
%C A295997 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).
%C A295997 For n > 1, a(n) = 4 iff n has all prime divisors p == 1 (mod 4).
%C A295997 The sequence is bounded, namely 4 <= a(n) <= 561, see A002997.
%C A295997 All members of A108574 appear in the sequence. The last to appear is 538 = a(8110351). - _Robert Israel_, Feb 15 2018
%C A295997 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
%C A295997 Note that a(n) >= A000790(n). - _Thomas Ordowski_, Feb 16 2018
%C A295997 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
%H A295997 Robert Israel, <a href="/A295997/b295997.txt">Table of n, a(n) for n = 1..10000</a>
%H A295997 J. H. Conway, R. K. Guy, W. A. Schneeberger, and N. J. A. Sloane, <a href="http://neilsloane.com/doc/Me213.pdf">The Primary Pretenders</a>, Acta Arith. 78 (1997), 307-313.
%F A295997 a(n) = a(rad(n)), where rad(n) = A007947(n).
%F A295997 For prime p, a(p) = A000790(p). - _Max Alekseyev_, Feb 27 2018
%p A295997 f := n -> g(map(t -> t[1], ifactors(n)[2])):
%p A295997 g:= proc (P) local k; option remember;
%p A295997   for k from 4 do
%p A295997     if not isprime(k) and andmap(p -> (p &^ k - p mod k = 0), P)
%p A295997     then return k
%p A295997     end if
%p A295997   end do
%p A295997 end proc:
%p A295997 map(f, [$1..100]); # _Robert Israel_, Feb 14 2018
%t A295997 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 *)
%o A295997 (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
%o A295997 (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
%Y A295997 Cf. A000790, A002808, A002997, A007947, A108574.
%K A295997 nonn
%O A295997 1,1
%A A295997 _Thomas Ordowski_, Feb 14 2018
%E A295997 More terms from _Rémy Sigrist_, Feb 14 2018