Problems & Puzzles: Puzzles

Puzzle 24.- Primes in several bases

Let’s convert a prime base 10 (P₁₀) to it’s corresponding numbers M_b in bases b, such that 2<=b<=9 :

P₁₀ à {M₂ , M₃, M₄, M₅ , M₆, M₇, M₈, M₉ }

Now let’s forget that all these M_b numbers are in a bases b other than 10 and let’s ask how many of them keep being primes base 10.

I have found 3 primes base 10 (2₁₀, 3₁₀ & 379081₁₀) that remain primes in other seven bases of the eight available.

For example, 379081 is a prime base 10 that remains prime for his representation in bases 9, 8, 7, 6, 5, 4 & 3 and that it’s composite only in his representation base 2 :

Prime =379081₁₀ à Primes{637001₉, 1344311₈, 3136123₇, 12043001₆, 44112311₅, 1130203021₄, 201021000001₃}, Composite={1011100100011001001₂ }

a)Can you find 3 more primes base 10 that remain primes in 7 bases b of the other 8 available 2<=b<=9 ?

b) Can you find a prime that remains prime in all the 9 bases 2<=b<=10, or give a theoretical reason why this can not be possible ?

Solution

Question a)

Jack Brennen, found (1-2 October, 1998) not 3 but 4 primes base 10 that remain primes in other 7 bases less than 10:

59771671 is prime in all bases <=10 except in base 4.
146752831 is prime in all bases <=10 except in base 6.
764479423 is prime in all bases <=10 except in base 4.
1479830551 is prime in all bases <=10 except in base 3.

***

Jack Brennen (who else?) found the 13/7/2001 the least example of prime numbers in base 10 that remains prime when it's expressed in all the bases from 2 to 9 supposing they are in base 10.

This the prime-gem 50006393431 that forces to say: "My goodness!... they exist":

In base 10: 50006393431:
In base 9: 153060758677
In base 8: 564447201127
In base 7: 3420130221331
In base 6: 34550030320411
In base 5: 1304403114042211
In base 4: 232210213100021113
In base 3: 11210002000211222202121
In base 2: 101110100100100111010000001001010111

Proved as it has been that they exist the next challenge is to find 3 more in order to be published in the Nei'ls sequences database. Who says I will try?

As a follow up of this result, can somebody calculate how fortunate was Jack in finding this prime number, that is to say the probability of finding a prime like 50006393431 with these properties?

***

Giovanni Resta wrote (5/5/03):

I would like to submit 3 new numbers (as requested!) that are solution of puzzle 24. They are: 727533146383, 2250332130313, 2651541199513, and my search was interrupted around n = 3,103,417,510,867.

Well done! Does anybody wants to add some more entries?

***

Giovanni Resta wrote (29/07/18):

The smallest prime which gives primes in all the bases from 2 to 11
is 181395559296673:

101001001111101001110001111000000010111010100001, 
212210021020122102012020121221, 221033221301320002322201, 
142233441101134443143, 1441443545230215041, 53131253026500001, 
5117516170027241, 783236572166557, 181395559296673, 52886474283457.

Note that all its digits in base 11 are smaller than 10, i.e., it gives a legitimate 
base 10 number: 181395559296673 = (5, 2, 8, 8, 6, 4, 7, 4, 2, 8, 3, 4, 5, 7)_11. 

Extending to base 12 seems difficult. If such a prime exists it is larger than 6*10^15.

***