Problems & Puzzles: Puzzles

Puzzle 1086 Take the representation of a prime p in the bases from 2 to 9, and... Paolo Lava sent the following nice puzzle Take the representation of a prime p in the bases from 2 to 9, consider these numbers as they were in base 10 and check if some of them are multiples of p. We have banal cases for the one digit primes 2, 3, 5 and 7: 2 has 8 multiples because in base 2 is 10 and 10/2=5 and in the other ones is always 2. 3 in bases from 4 to 9 is always 3, therefore 6 cases 5 in base 5 is 10 and 10/5=2 and in bases from 6 to 9 is always 5, therefore 5 cases 7 in base 3 is 21 and 21/7=3 and in base 8 and 9 is always 7, therefore 3 cases Apart from the previous ones, I found other primes of this kind but all with just 1 multiple. Here below the first {p, base and ratio}: 2753, 7, 4   2927, 4, 79   9431, 4, 223   10861, 7, 4   34217, 8, 3   70537, 8, 3   104891, 8, 3   1200341, 2, 83393053307361   3427673, 2, 321209199392737   3583417, 4, 8713 22772791, 7, 16 I stopped my search at 10^7. Q1. Other primes? Q2. Are there other primes with more than one multiple?

---

During the week from 15 to 20 of May, contributions came from Giorgio Vecchi, Seongjae Choi, Jeff Heleen, Giorgos Kalogeropoulos, Oscar Volpatti, Emmanuel Vantieghem. 

***

Giorgio Vecchi wrote:

I have a little contribution for the puzzle of the week.

323869489, 7, 34

***

Seongjae Choi, South Korea, wrote:

I found 323869489 with base 7

it is 11011562626(7) and the ratio is 34.

I searched until 1.6*10^10. but I couldn't find the other examples yet. 

***

Jeff Heleen wrote:

The only other one I found up to 10^9 was

 

num = 323869489, base = 7, ratio = 34.

 

***

Giorgos Kalogeropoulos wrote:

Q1.  323869489, 7, 34

Next term is bigger than 2*10^11,

***

Oscar Volpatti wrote:

I found eight more primes; each of them has just one multiple.
Solutions are listed using the format b,p,q,r:
b is the base (between 2 and 9 inclusive)
p is the prime,
q is the base-b representation of p, viewed as a base-10 integer,
r is the integer ratio q/p.


7
323869489
11011562626
34


6
168950820849211
1355154534031521431
8021


6
204637092293440284607
111104230430154414042532331
542933


8
392782357212551415517912019
242346714400144223374551715723
617


9
30063287732498714197576402090287180408266765016439835351
13167720026834436818538464115545785018820843077200647883738
438


9
1095489576920513404746831781587222924036821426230166020279
543362830152574648754428563667262570322263427410162346058384
496


9
2009771945588626494054661848934193641902009473302882181488788433
2084133507575405674334684337344758806652383823815088822203873605021
1037


9
425444638010168360837096526363437370880469734342431387508841374916639239098315970239747329
7584827006445281537003756872007361448057014423856866776507624032013844354644777117434215381412
17828


For b = 2 and b = 3, the best that we can do is to check each prime p in ascending order.
For b > 3, a nice trick allows to discard many primes with bad base-b representations.
As an example with b = 7, consider primes p whose base-7 representation has 11 digits and starts with "115":

351652861 <= p <= 357417661,

11500000000 <= q <= 11566666666;
We have the bounds  r_1 < q/p < r_2, with:
r_1 = 11500000000/357417661 ~ 32.175
r_2 = 11566666666/351652861 ~ 32.892
Hence the ratio q/p can never be integer within the given interval.
Again 11 digits, but starting with "110":

322828856 <= p <= 328593656

11000000000 <= q <= 11066666666

r_1 = 11000000000/328593656 ~ 33.476

r_2 = 11066666666/322828856 ~ 34.280
Now there can be solutions with integer ratio r = 34, and one such solution was actually found.


The speedup dramatically increases with b.
Depending on the chosen base, I checked primes up to the following bounds:



b  pmax
2  10^12
3  10^12
4  10^14
5  10^20
6  10^28
7  10^40
8  10^60
9  10^100

***

Emmanuel Vantieghem wrote:

Q1.

I found the prime number 323869489. In base 7  it reads : 11011562626, which is  34*323869489.
There is no other such prime below  3-10^11.

 

***