|
%I #38 Nov 16 2017 02:42:50
%S 2,2,2,4,2,3,2,8,8,5,2,4,2,7,4,16,2,9,2,5,6,11,2,9,7,13,26,4,2,6,2,32,
%T 10,17,6,9,2,19,12,16,2,7,2,12,8,23,2,16,18,25,16,9,2,27,10,8,18,29,2,
%U 16,2,31,8,64,5,3,2,17,22,11,2,9,2,37,24,20,21
%N Smallest integer m > 1 such that m^n == m (mod n).
%C Composite n are Fermat weak pseudoprimes to base a(n).
%C If n > 2 is prime then a(n) = 2. The converse is false : a(341) = 2 and 341 isn't prime.
%C a(n) <= A105222(n). a(n) = A105222(n) if and only if a(n) is coprime to n.
%C For n > 1, a(n) <= n and if a(n) = n, then A105222(n) = n+1.
%C It seems that a(n) = n if and only if n = 2^k with k > 0, a(n) = n-1 if and only if n = 3^k with k > 0, a(2n) = n if and only if n = p^k where p is an odd prime and k > 0. - _Thomas Ordowski_, Oct 19 2017
%H Giovanni Resta, <a href="/A239452/b239452.txt">Table of n, a(n) for n = 1..10000</a>
%H Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm#weak">Weak pseudoprimes to base a</a>
%e We have 2^4 != 2, 3^4 != 3, but 4^4 == 4 (mod 4), so a(4) = 4.
%p L:=NULL:for n to 100 do for a from 2 while a^n - a mod n !=0 do od; L:=L,a od: L;
%t a[n_] := Block[{m = 2}, While[PowerMod[m, n, n] != Mod[m, n], m++]; m]; Array[a, 100] (* _Giovanni Resta_, Mar 19 2014 *)
%o (Haskell)
%o import Math.NumberTheory.Moduli (powerMod)
%o a239452 n = head [m | m <- [2..], powerMod m n n == mod m n]
%o -- _Reinhard Zumkeller_, Mar 19 2014
%o (Python)
%o L=[];
%o for n in range(1,101):
%o ...a=2
%o ...while (a**n - a) % n != 0:
%o ......a+=1
%o ...L=L+[a]
%o L
%o (PARI) a(n)=my(m=2); while(Mod(m,n)^n!=m, m++); m \\ _Charles R Greathouse IV_, Mar 21 2014
%Y Cf. A105222.
%K nonn
%O 1,1
%A _Robert FERREOL_, Mar 19 2014
%E a(20)-a(77) from _Giovanni Resta_, Mar 19 2014
|
