Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #7 Apr 10 2024 09:41:18
%S 0,0,0,1,0,1,0,2,1,1,0,3,0,1,1,4,0,4,0,3,1,1,0,5,3,1,2,5,0,4,1,4,3,2,
%T 1,7,0,1,1,8,0,6,2,3,3,1,0,9,2,3,1,8,0,6,3,6,1,2,0,9,3,1,7,7,1,6,2,4,
%U 1,9,0,11,2,1,7,6,1,7,3,10,5,3,0,8,4,1,1
%N The number of pseudoprimes to base n that are smaller than n.
%H Amiram Eldar, <a href="/A371729/b371729.txt">Table of n, a(n) for n = 2..10001</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoprime">Pseudoprime</a>.
%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>.
%F a(n) = 0 if and only if A090086(n) > n, or equivalently, n-1 is in A316504.
%e a(2) = 0 since the smallest pseudoprime to base 2 (A001567) is 341 which is larger than 2.
%e a(5) = 1 since there is one pseudoprime to base 5 (A005936) that is smaller than 5: 4.
%e a(9) = 2 since there are 2 pseudoprimes to base 9 (A020138) that are smaller than 9: 4 and 8.
%t a[n_] := Count[Range[4, n-1], _?(CompositeQ[#] && PowerMod[n, # - 1, #] == 1 &)]; Array[a, 100, 2]
%o (PARI) a(n) = {my(c = 0); forcomposite(k = 4, n-1, if(Mod(n, k)^(k-1) == 1, c++)); c;}
%Y Cf. A001567, A005936, A020138, A090086, A316504, A371730.
%K nonn,easy
%O 2,8
%A _Amiram Eldar_, Apr 05 2024