Palindromic addition

This was sent to Math Fun by me a couple of days ago:

> Hello Math Fun,
> the addition a + b = c is palindromic if the digits
> involved in the addition are in the same order
> when read from left to right and from right to left.
> 12 + 9 = 21 is a good example.
> What is the « smallest » addition that shows at
> least once the ten digits 0, 1, 2, 3, … 9?
> I have a « c » with 16 digits in an addition that
> fulfills the requirements — but I am sure this can
> be beaten.
> Hope this is clear and not old hat.
> Best,
> É.

No reactions. I then posted this follow-up:

> Here is my a + b = c palindromic addition > with all digits from 0 to 9 visible at least once: > 234567898765432 + 1000000000000000 = 1234567898765432 > This « c » has 16 digits: is it possible to have > a smaller « c »? >
Maximilian was quick to send this to Math Fun:

Eric,           
You have
128904376 + 544505445 = 673409821
 Probably not the smallest, either... 
 -Maximilian

I was delighted. Then came Allan Wechsler:

The shortest possible would have 19 digits total, right? So it would have to be of the form [6-digit] + [6-digit] = [7-digit]. That means that the first digit of the sum would have to be 1. Its mirror-image would be the first digit of the second addend. I think that means that the first digit of the first addend has to be 8 or 9. I don't know how far this kind of analysis can get us. It's basically just a cryptarithm, right? But I never got into those.

And Maximilian again:

Allan,

I didn't do an exhaustive search but I convinced myself (maybe wrongly) that 6+6=7digits isn't possible:
In that case, the first digit on RHS must be 1 (can't be >1),
which by symmetry is also the leading digit of the 2nd term on the LHS.
Therefore the second digit of the RHS can't be > 1
But that digit is also the last digit of the first term, so if it's 0, 
then the last digits of the 2nd term and RHS (= 1st digit of 1st term) are equal and we can't have all 10 digits.
[Is that correct?]

I did a quick loop over permutations, i.e., first term (and RHS = reversal of first term) having all digits different,
so that's not an exhaustive search and may have missed solutions.
For 6+7=7 and 7+7=7 digits there was no candidate (:<=>  RHS - first term = palindrome),
only 8+8 = 8 gave what I posted, without the middle zero, which I added by hand. 
(There was no 8+8=8 "candidate" with a digit 0.)

-M.

Now enters Hans Havermann:

> AW: "The shortest possible would have 19 digits total, right?"

My brute force program found no sums in 19- and 20-digit pandigital palindromes. I've just started a 21-digit run that may take several days to finish. Luckily, I've already snagged a few solutions: 23087 + 16154945 = 16178032 23687 + 10154945 = 10178632 32078 + 16154945 = 16187023 32678 + 10154945 = 10187623

And Victor Miller:

I wrote a program using SAT solvers to find solutions. The sat solver cadical almost instantly shows that (6,6,7) is impossible. It also instantly found the second of Hans' (5,8,8) solutions.

Victor

... and a couple of minutes later, Victor sent this:

I've run my sat solver program to find all solutions. In all cases it does this in a fraction of a second on my desktop. Here are some of the results. The first column gives the number of digits in a,b,c, and the second the number of solutions. 5,8,8   | 24    | 6,9,9   | 60    | 7,8,8   | 324   | 6,8,9   | 0     | 4,8,8   | 0     | 7,7,7   | 0     | 7,9,9   | 324   | 9,9,9   | 330   | 8,9,9   | 378   | 9,10,10 | 15564 |

... and Victor again, a couple of hours later:

Here are the 24 solutions for 5,8,8: 23687 + 10154945 = 10178632 23087 + 16154945 = 16178032 23187 + 60654945 = 60678132 32178 + 60654945 = 60687123 31768 + 20254945 = 20286713 31268 + 70754945 = 70786213 32078 + 16154945 = 16187023 32078 + 61654945 = 61687023 31068 + 72754945 = 72786013 31068 + 27254945 = 27286013 32678 + 10154945 = 10187623 23087 + 61654945 = 61678032 21867 + 30354945 = 30376812 21067 + 38354945 = 38376012 21067 + 83854945 = 83876012 21367 + 80854945 = 80876312 12376 + 80854945 = 80867321 13086 + 27254945 = 27268031 12076 + 38354945 = 38367021 12076 + 83854945 = 83867021 13086 + 72754945 = 72768031 12876 + 30354945 = 30367821 13786 + 20254945 = 20268731 13286 + 70754945 = 70768231

Thank you and bravo Victor — and Allan, Maximilian + Hans! 

I guess Carole and me will turn a close idea into a sequence for the OEIS soon.


Commentaires

Enregistrer un commentaire

Posts les plus consultés de ce blog

Beautés ?

Image
Beau comme un clavier ? Un deuxième ? (celui de Modotti)   Beau comme le dos d ’ un timbre proposé par Delcampe ? Beau comme une série ukrainienne où les avions râpent le Kremlin ? Belle comme Chargois ? ... belle comme Germaine Richier ? Bel atelier ? Beau comme une pièce de 1 santim ? ... ou comme une pièce de 50  santeem ? ... Byrrh , beau comme un anus ? Beau comme la collection de Marin Karmitz à Beaubourg ? Belles Ménines ? Beau comme Marcel Duchamp ? Beau comme Jean-Luc Godard ? Beau comme la réouverture de l ’ Einsteinturm à Berlin ? Beau comme un anneau dudit ? Beau comme Eisenstein ? Beau comme les fleurs de Pascale hier matin ? Beau comme on dirait la planète Mars ? Beau comme des recherches personnelles ? Beau comme une marelle (vers le ciel) ? Beau comme un triple selfie (au Man Ray ) ? Beau comme le ciel de Sacha , mardi, en face du restaurant La Montagne ? (qui a rouvert) ... beau comme ce bleu-là de Lo ? Beau comme le froid ? Beau comme une Vespa ? Beau comme Cloon
Lire la suite

Underline, reproduce

Image
Dall.e creation If we underline the... « first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth, eleventh,… » letter of this sentence S 1 , we see that the successive underlined letters simply reproduce S 1 . No big deal. If we decide not to start S 1   with "first" but with "sixth", we can reproduce the new S 6  quite easily: S 6 = sixth , second, third, fourth, fifth, first , seventh, eighth, ninth, tenth, eleventh,… S 6  was reproduced in a slightly less mechanical manner than  S 1 :  just two words of  S 1   swapped here ("first" and "sixth", in red, above). If we start S 8  with "eighth" we just swap again a pair of words of S 1  ("first" and "eighth", in red, hereunder): S 8  = eighth , second, third, fourth, fifth, sixth, seventh, first , ninth, tenth, eleventh,… What about starting S 9  with "ninth"? How many swaps do we need to reproduce S 9 ?  This is more tricky! (Indeed, we
Lire la suite

Le tripalin se présente

Image
Un tripalin est constitué de trois images. Chaque image illustre un substantif. Accolés, ces trois substantifs forment une chaîne palindromique. Laquelle nous vous invitons à trouver.  Exemple ci-dessous. Le premier mot est COL-BLEU Le second DUEL Le troisième BLOC . Ces mots forment la chaîne COLBLEUDUELBLOC qui est bien palindromique. Je posterai chaque jeudi une nouvelle salve de tripalins . Rien que des noms illustrés – pas d’adjectifs, pas de verbes conjugués, pas d’adverbes (parfois un prénom ou un nom propre – mais seulement quand il faut). À la demande générale (de mon neveu), chaque tripalin sera surmonté de son numéro d ’ ordre ( octothorpe noir) et de trois nombres bleus. Ces nombres reprennent les trois longueurs (en lettres) des trois mots présents dans le tripalin. On a par exemple ci-dessous [ #0 ↓ 7+4+4 ] car COL-BLEU comporte  7  lettres, DUEL   4  et BLOC   4 . Le numéro d ’ ordre est zéro. #0 ↓ 7+4+4 Voilà – tous retours critiques, construits ou déconstruits, bien
Lire la suite