Problems & Puzzles: Puzzles

Puzzle 170. Pseudoprimemania

To Richard G. E. Pinch (*)

Composite n odd numbers are said to be pseudoprime base 2 [psp(2)] if:
2n-1 = 1 mod n 


1) Find a twin psp(2) other than 4369 and 4371

2) Find a pair of reversible psp(2) other than 15709 & 90751

3) Find three psp(2) palindromes other than 101101, 129921 & 1837381

I have found the earliest five psp(2) in arithmetic progression:
172081, 285541, 399001, 512461, 625921
(difference = 113460)
4) Find the earliest K psp(2) in A.P for K=6, 7, 8, ... 

I have found a 3x3 magic square having five psp(2) numbers (in bold letters in the Table)










5) Can you find a magic square composed of
nine psp(2)?

If you count the psp(2) numbers ending in each one of the five possible ending digits (1, 3, 5, 7, & 9), you will discover that psp(2) numbers ending in digit "1" are around four times more abundant than the average of other four possibilities.

For example: when we arrive to the psp(2)=10004681 there are 379, 95, 89, 105 & 83 psp(2) ending in the digit 1, 3, 5, 7, & 9, respectively.

6) Can you explain this statistic?

Composite n even numbers are also called even pseudoprimes base 2 if:
2n = 2 mod n.

7) Find the earliest even psp(2) ending in zero (divided by 10), or show that it can not exist.

Added questions:

Shyam (3/3/02):

Denote the Seq. of psp(2) by x1, x2, x3, ....xn, ...etc. where xn is the nth psp(2).

I find that the minimal ratio of xn/xn+1 is 0.58371, for x3=645 and x4=1105.

8)  Can this record of minimal ratio be ever beaten? I conjecture that this is the minimum possible. Can this be proved or disproved?

C. Rivera (9/3/02):

I have found three quadruplets of consecutive odd numbers that are primes or psp(2):

641, 643, 645, 647
656597, 656599, 656601, 656603
6212357, 6212359, 6212361, 6212363

9) Can you find quintuplets of these kind or to show that they can not exist?

I have found many pairs of consecutive numbers (n, n+1) being:
n=psp(2) and n+1=prime.

The first example is: 161038 & 161039

10) Can you find the first pair such that n=prime and n+1=psp(2), or to demonstrate that they can not exist?

Jean-Claude Rosa wrote:

About the question 10 of the puzzle 170 , I noticed this: We have 40 even psp(2) up 10^10 ( see the paper inside Richard Pinch site). Among these numbers 29 are ending by 6, 4 ending by 4,4 ending by 8 and 3 ending by 2.
But the most interesting is that all these numbers are equal to 1 mod 3 ,( except 196116194;377994926;2001038066 all equal to 2 mod 3). 

11) Is it possible to find an even psp(2) equal to 0 mod 3 ?


Jim Fougeron solved (3/3/02) the question 7)

#7 can't be done. The patterns of 2^n == x(mod n), for n=a*10 always alternate between 4 and 6 mod 10. Here is why:

for 2^k, an increase of k by 1 always doubles the result. That being the case, the least significant digit (base 10) will always be doubled (with possible carry). The pattern thus seen for 2^k%10 is 2, 4, 8, 6 (16) ... 2^10%10 falls into this "pattern" at 4. so 2^11%10 == 8, 2^12%10 == 6 ... (2^20%20)%10 will be at 6.

What we have is 2 modular "patterns", with the least common multiple being 20. The first pattern is is of lenth 4. Then second is of length 10 (the 2^n==x(mod n), n=10*a). The second "pattern" will only satisfy 2 out of the 4 possible from the first pattern. Thus, 2^n==a(mod n) if n%10=0 then a%10 = 4 or 6, always, so a can never be 2.


Joe K. Crump also solved this same question 7), the following way:

2^n = 2 (mod n). Question: Find an even n satisfying the above, but divisible by 10. Proof:

1: Since n is divisible by 10, which is 5*2, let's represent n as 5*z where z is EVEN: n=5z

2: Now 2^(5z) = 2 (mod 5z), so 2^(5z) = 2 (mod 5), which is 32^z = 2 (mod 5) or 2^z=2 (mod 5)

3: Now the order of 2 mod 5 is 4, and 2^1 = 2 (mod 5), so all z that satisfy this equation must be of the form 4x+1

4: This contradicts (1) because z must be even, and 4x+1 cannot be even.


One more solution for this question 7), came from J. C. Rosa:

Let n=10*k , k is integer. If n is a psp(2) then 2^n=2 mod n. So 2^(10*k)=2 mod 10*k,from where (2^10)^k=10*k*m+2 ,where m is integer. and so 1024^k=10*k*m+2. But 1024^k is a number with an ending digit equal to 4 ( if k is odd) or 6 (if k is even) and the ending digit of 10*k*m+2 is always 2 . Therefore an even psp(2) divisible by 10 can not exist.

Regarding the question 3), Patrick De Geest wrote (3/3/02) this:

About your interesting Pseudoprimemania puzzle, question 3, I have a similar WONplate 124. My own search brought me already to 'larger then 10000000000000001'. Maybe next week you can add a link in the solution section to my WONplate so one can follow the progress I make/don't make :)

According with this a new palindrome psp(2) must be larger than 10^16...


Shyam Sunder Gupta (10/3/02) got the fourth palindrome & psp(2) for the question 3:

127665878878566721 = 7*11*19*41*73*137*271*577*1361

But it happened that this fourth psp(2) & palindrome is also a Carmichael number (*), as a matter of fact the second palindromic Carmichael number (the first one is 101101)!!!

(*) C is Carmichael number if for all prime factor P of C happens that (C-1) mod (P-1)=0


J. C. Rosa wrote (14/4/2002):

I have proved that an even psp(2) divisible by 3 can not exist. Here is a proof:

Let N=10*d+2 (d is an integer ). We have: 2^N=2 mod N and we want N=0 mod 3.From where d=1 mod 3 ; d=3*k+1 and N=30*k+12 (k is an integer). The equality 2^N=2 mod N implies: 2^(30*k+12)=m*(30*k+12)+2 with m integer and after: 2^(30*k+11)=3*m*(5*k+2)+1 and therefore:

2^(30*k+11)=1 mod 3 (1)

But 2^(30*k)=1 mod 3 and 2^11=2 mod 3 from where:

2^(30*k+11)= 1*2=2 mod 3 (2).

The equality (2) contradicts the equality (1) and an even psp(2) of the form 10*d+2 is not divisible by 3. Using the same method for N=10*d+4:6 or 8 we can prove that an even psp(2) is never divisible by 3.


Shyam Sunder Gupta (19/10/02) got the fifth palindrome & psp(2) for the question 3:

Today I have cracked the fifth palindromic pseudoprime (base 2). This is 1037998220228997301= 41*101*211*251*757*1321*4733.

Unfortunately it is also not a strong pseudoprime(base 2)...(neither) it is not a carmichael number


Shyam wrote again in October 2013:

My solution to Q.9 of Puzzle 170. Pseudoprimemania is given below:

9) Can you find quintuplets of these kind or to show that they can not exist?

There can be infinity of quintuplets of these kinds. The smallest five examples are :



All these examples are of type where middle i.e. third number in sequence is pseudoprime(base 2). Obviously such pseudoprimes ends in 5. 
If such pseudoprime is denoted by k then k-4, k-2 is twin prime pair so also k+2 and k+4. This is a necessary condition if there is only
one pseudoprime and other four numbers are primes. other possibility of more than one pseudoprime in a quintuplets of these kinds is a 
remote view of this it is conjectured that sextuplets of these kinds does not exist.


Records   |  Conjectures  |  Problems  |  Puzzles