Problems & Puzzles: Puzzles

Puzzle 706 Palindromes generating palindromes Let C to be a composite palindrome such that the ordered (from smaller to larger) concatenation of its prime factors produces another palindrome F. Example: C=10001 = 73*137 -> F=73137 The following are the first few composite elements of this sequence C: C: 4, 8, 9, 121, 343, 1331, 10001, 10201, 14641, 36763, 1030301, 1037301, 1226221, 9396939, 104060401, ... (See A046450) and the produced palindromes are in the sequences F: F: 22, 222, 33, 1111, 777, 111111, 73137, 101101, 11111111, 97379, 101101101, 32911923, 10211201, 310131013, 101101101101, ... Once in a while, the palindrome produced in F are prime numbers as 97379 and 310131013. Q. can you extend both sequences, C & F and discover more primes in F?

---

Contributions came from Seiji Tomita & Emmanuel Vantieghem.

Note: I had to anticipate the edition of my pages one day because I have to attend a personal urgency out of the city. Sorry for these puzzlers that possible send their solutions during the rest of this day (friday) or saturday morning. I will add them next week.

***

Seiji wrote:

About Puzzle 706.
{P,Q}:Prime
P and Q are composed of {0, 1, 2}.
10^8<{P,Q}<10^14
C=P*Q
F=P&Q
Only one data is shown in each digit of P.

[C, P, Q, F]
[12323244744232321, 111010111, 111010111, 111010111111010111]
[1233101369631013321, 1100001211, 1121000011, 11000012111121000011]
[132121132494231121231, 11000011021, 12011000011, 1100001102112011000011]
[13212122213931222121231, 110100100021, 120001001011, 110100100021120001001011]
[1320013420049400243100231, 1100001100021, 1200011000011, 11000011000211200011000011]
[133100132001595100231001331, 11000010000121, 12100001000011, 1100001000012112100001000011]
It seems F is always divisible by 11.

***

Emmanuel wrote:

This is what I could find about puzzle 706 :

 

This is how I extended C (6 more than in  A046450, the underlined ones are new) :

4, 8, 9, 121, 343, 1331, 10001, 10201, 14641, 36763, 1030301, 1037301, 1226221, 9396939, 104060401, 12467976421, 14432823441, 93969696939, 119092290911, 1030507050301, 1120237320211, 1225559555221, 1234469644321, 1334459544331, 100330272033001, 101222252222101,103023070320301, 121363494363121, 134312696213431, 10022212521222001, 11111212521211111, 11333234943233311

The next term is <= 12115514941551121.

The corresponding  F  is :

22, 222, 33, 1111, 777, 111111, 73137, 101101, 11111111, 97379, 101101101, 32911923, 10211201, 310131013, 101101101101, 111211112111, 3328131318233, 3101310131013, 1190911190911, 10102011020101, 10002111120001, 11021111112011, 11012111121011, 11110211201111, 1001200110021001, 1001110110111001, 1010020110200101, 1101201111021011, 1110012112100111, 100111001100111001, 100100111111001001,102100111111001201.

To find this, I noticed that the biggest elements of C all were of the form  p*R(p) with  p  a prime with digits <= 2.  This let me find a lot of numbers of C.

It then took a few hours to check that there were no other elements between them.

It is much more difficult to find primes in F.  I tried several possibilities but none of them gave primes. The concatenations  p&R(p) are all divisible by 11.

One possibility is this one :

Let  a(n)  be the concatentation of  n  times 3101.  Thus, a(1) = 3101, a(2) = 31013101, ...

Put  q(n) = a(n)&3.  If  q(n)  is prime, then  3*101*q(n)  is in  C.  This is the case when  n = 1, 2, 295, 596  and maybe many others greater than 1000.

If  q(n)  and  q(n+1)  are both prime, then obviously  3101&q(n)  is prime since it equals  q(n+1).  But I think it is a titans job to find such an  n.

I proved the primality of  q(295)  and  q(596)  with PRIMO.  The last one took about 12 hours.

***

Giovanni Resta wrote on Sep. 20, 2013:

it is not difficult to find palindromes P whose
prime factors taken in order give another palindrome.

In particular it is easy to find primes p such that their reversal
r is greater than p and p*r is a palindrome. Since r is the reverse of
p, then the concatenation pr is palindrome as well.
For example, 1021*1201 = 1226221.
The first 80 primes with this property are

2,3,11,101,1021,111211,1000211,1010201,1101211,1102111,1111021,10011101,
10012001,10100201,11012011,11100121,100100111,100111001,102100111,110021011,
110111011,111010111,1000020001,1000110101,1001001011,1001002111,1001101021,
1001201101,1002000101,1010000021,1010001101,1010011111,1010100121,1010102101,
1010120011,1100001211,10000011121,10001102101, 10002011101,10002100111,
10010002001,10010100101,10010120011,10010201011,10100000011,10100000111,
10100201011,10100210011,10102100011,10111001011,11000011021,11100000211,
100000010101,100000011011,100000201111,100001210011,100001211001,100002011101,
100002110101,100010100121,100101110111,100101111001,100102100101,100110012001,
100110101011,100110101111,100111010101,100120000111,100120001011,100200010111,
101000000011,101000012011,101010100111,101010110011,101100011011,101101010111,
102000010111,102010000111,110100100021,110101000111,

and it is very easy to find larger examples, for example,
the prime p = 10^500+10^53+10^44+10^27+1, multiplied by its
prime reversal, gives a palindrome with 1001 digits.

The drawback of these easy to find solutions is that the palindrome
resulting from the concatenation of p and r has always an even number
of digits, and thus it is a multiple of 11 and cannot be prime.

There are however some more sporadic and more interesting solutions not
of the form above.
Up to prime factorizations involving 24 or less digits they are:

343 = 7*7*7
1331 = 11*11*11
10001 = 73*137
14641 = 11*11*11*11
36763 = 97*379
1030301 = 101*101*101
1037301 = 3*29*11923
9396939 = 3*101*31013
104060401 = 101*101*101*101
14432823441 = 3*3*281*313*18233
93969696939 = 3*101*310131013
119092290911 = 11*9091*1190911
34903953835930943 = 38821*899099812883
97195446964459179 = 3*3*7*1542784872451733
97729500500592779 = 7*13*14557*73775541317
9047954506054597409 = 911*9931892981399119
12222222222222222221 = 11*1111111111111111111
111010642191246010111 = 787*233406919*604332787
134444444444444444431 = 11*11*1111111111111111111
34282700724242700728243 = 7*313*2231079229*7013223137

the primes resulting from concatenating the palindromic factorizations
above are the two values already known 97379, 310131013, plus
7131455773775541317 and 11111111111111111111111.

It is also possible to find larger examples by generalizing the
9396939 = 3*101*31013 and 93969696939 = 3*101*310131013,
(with palindromes of the form 3*101*(3101)_k3, where (3101)_k denotes
k copies of 3101). For k up to 5000, (3101)_k3 is a (probable) prime for
k=1,2, 295, 596, 1250 and 1516, but the resulting concatenation is not prime.

I've used two approaches. The trivial one consists in generating odd palindromes, factorizing them using Mathematica and then testing if the concatenation of the prime factors is a palindrome.

At a certain point I abandoned this approach for another
one which does not requires the factorization in prime factors.

In practice I do the reverse: I generate odd palindromes (excluding those ending in '5') and then I recursively decompose (if possible) each palindrome into a concatenation of non decreasing primes.
Then I multiply the primes together and  I check if the result is a palindrome.

A final curiosity: the two smallest palindromes such that
the concatenation of their prime factorization is a square are
918656819 = 179*5132161, where 1795132161 = 42369^2,
and  90795731413759709 = 349*6530401*39838241 where
349653040139838241 = 591314671^2.

***