OFFSET
1,1
COMMENTS
For each odd composite number m > 9 the number of witnesses <= phi(m)/4. For numbers in this sequence the ratio reaches the maximal possible value 1/4.
The semiprime terms of this sequence are of the form (2*m+1)*(4*m+1) where 2*m+1 and 4*m+1 are primes and m is odd.
From Jianing Song, Mar 11 2026: (Start)
Each term is a product of 2 or 3 distinct primes and is congruent to 3 modulo 4. The terms that are not semiprimes are exactly those terms in A329468 with 3 factors.
In general, let S(k) be the number of witnesses for strong pseudoprimality of k. If omega(k) = r, then S(k)/phi(k) <= 1/2^(r-1), where the equality holds if and only if k is a Carmichael number (A002997) whose prime factors are all congruent to 3 modulo 4.
Proof. For k = Product_{i=1..r} (p_i)^(e_i), write p_i = 2^(s_i)*d_i for odd d_i. Then the formula of A071294 gives
|S(k)| = (Product_{i=1..r} gcd(d_i,k-1)) * (1 + (2^(r*min{s_i})-1)/(2^r-1)),
and so
|S(k)|/phi(k) = (Prod_{i=1..r} gcd(d_i,k-1) / (d_i*p_i^(e_i-1))) * [(1 + (2^(r*min{s_i})-1) / (2^r-1)) / 2^(Sum_{i=1..r} s_i)] <= (Prod_{i=1..r} gcd(d_i,k-1)/d_i) * [(1 + (2^(r*min{s_i})-1) / (2^r-1)) / 2^(Sum_{i=1..r} s_i)].
Without loss of generality, suppose that min{s_i} = s_1. Then
|S(k)|/phi(k) <= (Product_{i=1..r} gcd(d_i,k-1)/d_i) * [(1 + (2^(r*min{s_i})-1)/(2^r-1))/2^(r*s_i)] <= (1 + (2^(r*min{s_i})-1)/(2^r-1))/2^(r*s_i).
Now:
- We have (1 + (2^(r*min{s_i})-1)/(2^r-1))/2^(r*s_i) <= 1/2^(r-1), and the equality is strict if s_1 > 1.
- If s_1 = 1, then |S(k)|/phi(k) <= (Product_{i=1..r} gcd(d_i,k-1)/d_i) / 2^(-1+Sum_{i=1..r} s_i). As a result, S(k)/phi(k) = 1/2^(r-1) if and only if all s_i are equal to 1, k is squarefree, and d_i-1|k-1 for every d. This is equivalent to k being a Carmichael number with only prime factors congruent to 3 modulo 4. (End)
REFERENCES
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.
LINKS
Amiram Eldar, Table of n, a(n) for n = 1..350
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
EXAMPLE
15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.
MATHEMATICA
o[n_] := (n - 1)/2^IntegerExponent[n - 1, 2];
a[n_?PrimeQ] := n - 1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2] & /@ (p - 1)]) - 1)/(2^om - 1))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]
CROSSREFS
KEYWORD
nonn
AUTHOR
Amiram Eldar, Nov 20 2019
STATUS
approved