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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles