A394177 Odd k such that there are exactly 2 bases 1 <= b <= k-1 in which k is a strong pseudoprime.

3, 9, 15, 21, 27, 33, 35, 39, 45, 51, 55, 57, 63, 69, 75, 77, 81, 87, 93, 95, 99, 105, 111, 115, 117, 119, 123, 129, 135, 141, 143, 147, 153, 155, 159, 161, 165, 171, 177, 183, 187, 189, 195, 201, 203, 207, 209, 213, 215, 219, 225, 235, 237, 243, 245, 249, 253, 255, 261, 267

Offset

1,1

Comments

In other words, odd k>1 such that there are no bases 2 <= b <= k-2 in which k is a strong pseudoprime.

Odd k = 2*m+1 such that A071294(m) = 2.

According to the formula of A071294, k is a term if and only if k has a prime factor congruent to 3 modulo 4 and gcd(p-1,k-1) is a power of 2 for every prime factor p of k.

Links

Jianing Song, Table of n, a(n) for n = 1..10000

Example

105 = 3*5*7 is a term since gcd(3-1,105-1) = 2, gcd(5-1,105-1) = 4, and gcd(7-1,105-1) = 2 are all powers of 2.
231 = 3*7*11 is not a term since gcd(11-1,231-1) = 10. Indeed, A071294((231-1)/2) = 10.
221 = 13*17 is not a term: even if gcd(13-1,221-1) = 4 and gcd(17-1,221-1) = 4, it does not have a prime factor congruent to 3 modulo 4. Indeed, A071294((221-1)/2) = 6.

Prog

(PARI) isA394177(k) = if(k%2==0, return(0)); my(f=factor(k), r=#f~, found_3_mod_4=0); for(i=1, r, if(!isprimepower(2*gcd(f[i, 1]-1, k-1)), return(0)); if(f[i, 1]%4==3, found_3_mod_4=1)); return(found_3_mod_4)

Crossrefs

Cf. A071294 (number of bases), A329759 (numbers with the most bases possible).

A394182, which is the sequence where "strong pseudoprime" is replaced by "Euler-Jacobi pseudoprime", is a supersequence.

Sequence in context: A299790 A030594 A032676 * A394182 A366849 A228935

Adjacent sequences: A394174 A394175 A394176 * A394178 A394179 A394180

Keyword

nonn,easy

Author

Jianing Song, Mar 11 2026

Status

approved