cp's OEIS Frontend

A371729 The number of pseudoprimes to base n that are smaller than n.

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