Puzzle 808. Palprimes that remain...

Problems & Puzzles: Puzzles

Puzzle 808. Palprimes that remain...

Dmitry Kamenetsky sent the following nice puzzle:

Here we ask for palprimes base 10 that remain palindrome in several other bases.

Example:

191, base=10 -> 515, base=6 and 232, base=9

Simplifying: 191(10) -> 515(6), 232(9)

Q. Find other palprimes base 10 that remain palindrome in more bases than 191.

Contributions came from Emmanuel Vantighem, Jan van Delden, T. D, Noe, Ramón David Aznar

***

Emmanuel wrote:

There are many palprimes that remain palprime in other bases than 10.

Here I a made a record list(*) of the palprime p (< 3*10^10) followed by the set S of all bases (less than p) for which p is palprime :

151, {3, 10}

191, {6, 9, 10}

373, {4, 8, 9, 10}

10301, {10, 27, 30, 44, 100}

18481, {10, 105, 110, 112, 120, 132}

19891, {10, 31, 32, 61, 102, 117, 130}

96769, {10, 47, 67, 209, 224, 252, 256, 288}

1008001, {10, 119, 221, 326, 720, 750, 800, 840, 875, 896, 900, 960, 1000}

1062601, {10, 160, 173, 255, 422, 489, 759, 770, 805, 825, 840, 920, 924, 966, 1012}

1670761, {10, 121, 161, 348, 591, 918, 936, 945, 952, 1020, 1071, 1080, 1092, 1105, 1170, 1190, 1224, 1260}

101474101, {10, 824, 1000, 1619, 1983, 6029, 7350, 7434, 7644, 7670, 7965, 8190, 8260, 8673, 8775, 8820, 8850, 9100, 9204, 9450, 9555, 9828}

10008180001, {10, 3329, 12715, 70980, 71487, 72800, 73125, 73320, 74025, 76050, 76375, 76986, 78000, 78750, 78960, 79430, 81120, 81900, 82250, 84000, 84500, 84600, 85176, 85540, 87984, 88125, 88725, 90000, 91000, 91650, 93600, 94000, 94640, 94752, 95316, 97500, 97760, 98700}

12137973121, {10, 3022, 3651, 15684, 37033, 56629, 78120, 78435, 78624, 79680, 80352, 82336, 83328, 83664, 84240, 84630, 86320, 87048, 87360, 87399, 87885, 89280, 89640, 90055, 90272, 90636, 90720, 92628, 92960, 93744, 94122, 95616, 96720, 97110, 98280, 100347, 100440, 101556, 102920, 103584, 104160, 104580, 104832, 107136, 107568, 108066, 108810}

14063936041, {10, 3339, 5350, 9961, 84645, 85140, 85785, 86184, 86526, 86940, 87032, 87780, 88236, 89010, 89397, 89870, 91080, 91770, 92340, 93555, 93955, 94392, 95634, 96140, 97524, 97911, 98040, 99330, 100947, 101574, 102168, 102465, 102942, 103845, 104328, 104490, 105336, 106191, 106260, 106812, 106920, 107730, 107844, 108360, 108790, 110124, 110295, 111780, 112746, 112860, 114380, 114939, 115368, 117990, 118503}

1000605060001, {10, 100, 50257, 709800, 711200, 714375, 721500, 733044, 739375, 740000, 742950, 750360, 751205, 751840, 757575, 760500, 762000, 772668, 777000, 780000, 781625, 787878, 789432, 792480, 794131, 800100, 808080, 819000, 822325, 825500, 832104, 832500, 841750, 845000, 845820, 851760, 855218, 858520, 865800, 866775, 875420, 887250, 889000, 900432, 901446, 901875, 910000, 914400, 916305, 924560, 932400, 937950, 939800, 946400, 950625, 952500, 962000, 965835, 969696, 971250, 977392, 986790, 990600, 1000125}

1002113112001, {10, 20191, 36897, 112606, 708000, 708708, 715080, 722150, 722750, 726880, 728000, 735280, 736320, 742350, 744875, 746592, 750750, 751660, 763224, 764400, 767000, 772044, 774670, 777700, 778800, 786588, 787800, 791840, 795025, 800800, 805350, 808000, 808500, 808808, 809952, 816585, 826000, 826826, 833250, 834260, 840840, 843700, 848400, 852137, 858000, 859040, 862400, 866580, 867300, 871024, 872256, 875875, 875973, 882336, 885885, 888800, 893850, 901992, 908600, 917686, 919100, 920400, 924000, 924352, 925120, 929604, 933240, 939575, 944944, 950208, 953440, 954030, 955500, 960960, 965055, 972125, 973500, 983235, 984750, 989800, 991200, 1001000} (82 bases)

(*) That p, S figures in this list means that for any palprime q < p the number of bases for which q remains palprime is strictly less than the number of elements in S

I also found only two palprimes below 10^15 that remain palprime in base 2 :

313 = (100111001)(2)

7284717174827 = (1101010000000011010111110101100000000101011)(2)

***

Jan wrote:

I searched all palprimes p with a maximum of 17 digits.

Longest sequence of representations in bases b, b<10:

373(10): 454(9),565(8),11311(4)

I found no other palprime p with more than 1 other representation.
I found no palprime p with a representation in base 5.

Representation in other bases b, b>10:

If b>p we have the trivial solution p(b).
Every representation, except the trivial representation [1,1](p-1), consists of an odd number of digits in base b:

If we have a representation with an even number of digits in base b: [a[0],a[1],..,a[n-1],a[n-1],...,a[1],a[0]](b) we have p=a[0]*(1+b^(2n-1))+a[1]*b*(1+b^(2n-3))+..+a[n-1]*b^(n-1)*(1+b).
Since b+1 is a divisor of b^(2k-1)+1, p has a divisor b+1. So p can only be prime if p=b+1 (or b=p-1 having representation [1,1](b)).

Representations with an odd number of digits 2k+1, k>0, have necessarily   p^(1/(2k+1))<b<p^(1/(2k)). Strict inequalities since p is prime.

If p^(1/3)<b<p^(1/2) we have three digits. The representation is of the form [a,c,a](b). Hence p-a=b(ab+c). If a=1 and p-1 has many prime factors, we expect many solutions.
For instance: p=14063936041 with 14063936040=2^3*3^5*5*7*11*19*23*43 has 51 representations of the form [1,c,1](b) and 3 of the form [a,c,a] with a>1.

Some interesting representations where all digits and the base are prime:

155292551(10): [3,5,13,11,13,5,3](19)

1551551(10):     [11,17,3,17,11](19)

15551(10):         [11,13,11](37) =[2,67,2](73) This one is for Sheldon:

"The best number is 73. Why? 73 is the 21st prime number. Its mirror, 37, is the 12th and its mirror, 21, is the product of multiplying 7 and 3... and in binary 73 is a palindrome, 1001001, which backwards is 1001001."

***

Tony wrote:

How appropriate that the number of this puzzle - 808 - is also a palindrome!

If one works with just the bases 2 to 10, then it appears that 373 is the
base-10 palindrome that has the most bases that also produce palindromes:
4, 8, 9, and 10. We have 373(10) = 454(9) = 565(8) = 11311(4).

However, a number can be palindromic in bases higher than 10. As an
extreme example, every number n > 1 is palindromic in base n-1. Here is a
list of numbers palindromic in base 10 that have an increasing number of
palindromes in other bases:

5, {2,4}

151, {3,10,150}

191, {6,9,10,190}

373, {4,8,9,10,372}

10301, {10,27,30,44,100,10300}

18481, {10,105,110,112,120,132,18480}

19891, {10,31,32,61,102,117,130,19890}

96769, {10,47,67,209,224,252,256,288,96768}

1008001, {10,119,221,326,720,750,800,840,875,896,900,960,1000,1008000}

1062601, {10,160,173,255,422,489,759,770,805,825,840,920,924,966,1012,1062600}

1670761,
{10,121,161,348,591,918,936,945,952,1020,1071,1080,1092,1105,1170,1190,1224,1260,1670760}

There appears to be no limit to the number of such palindromes.

***

Ramón wrote:

nº bases Palprime Bases 1 11 10 2 151 3 10 3 191 6 9 10 4 373 4 8 9 10 5 10301 10 27 30 44 100 6 18481 10 105 110 112 120 132 7 19891 10 31 32 61 102 117 130 8 96769 10 47 67 209 224 252 256 288 13 1008001 10 119 221 326 720 750 800 840 875 896 900 960 1000 15 1062601 10 160 173 255 422 489 759 770 805 825 840 920 924 966 1012 18 1670761 10 121 161 348 591 918 936 945 952 1020 1071 1080 1092 1105 1170 1190 1224 1260 22 101474101 10 824 1000 1619 1983 6029 7350 7434 7644 7670 7965 8190 8260 8673 8775 8820 8850 9100 9204 9450 9555 9828

***

Hakan Summakoglu wrote:
373(10) -> (11311)4, (565)8, (454)9
***

Records | Conjectures | Problems | Puzzles