World!Of
Numbers

WON plate
96 |

A follow-up from WONplate 36 and a new ninedigital puzzle

A follow-up from WONplate 36

Every integer X can be multiplied with another
integer Y to produce a palindrome P.
Which one are the hardest cases ?

In WONplate 36 I solved Fred W. Helenius's (email) puzzle
"Find the smallest palindrome divisible by 8181"
which turned out to be 9599999998999999959

What I wanted to know is how he came about that 8181
would be a challenge in the first place ?

 Here is Fred's answer from [ March 12, 2001 ] On 27 April 1997, I sent you an email message in response to your post on sci.math in which I mentioned a C program that I used to verify that 999999999 was the smallest palindrome divisible by 81. A few days later, a much-improved version of that program was able to find the smallest palindrome divisible by each integer (other than multiples of 10) up to 10000, with three exceptions: 8181, 8991 and 9801. The program checked palindromes of up to 15 digits, and took only a few minutes to run. So the short answer is that I knew 8181 was hard because I knew it wasn't easy. Also, a special mention should be given to 8891, which is the only number up to 10000 other than the multiples of 81 which is at all difficult; its smallest palindromic multiple has 14 digits. And lastly, was the above solution for 8181 already known ? Probably not. Although I checked yesterday that my program could handle 8181 in about 20 minutes, I don't think I bothered to do so back in 1997. 9801 is of similar difficulty (20 digits); 8991 is worse (more than 20 digits; once again, I didn't take the time to look further).

Things are recapitulated in the following table.
Let us try now to (re)discover Fred Helenius results

MultiplicandSmallest Possible MultiplierPalindrome
8112345679 - (easy)999999999
81811173450678278939 - [ March 10, 2001 ]9599999998999999959
8891854694892775990922909957
8991
111222333444555666777889
by Daniel Fischer [ June 19, 2008 ]
999999999999999999999999999
or 10^27–1
98012030405060708091 - [ May 16, 2003 ]19899999999999999891

Some things for the margin
8991 can be expressed palindromically.
Is is namely equal to 9990 – 0999

I'd like to introduce now the next ninedigital variation to the puzzle.

Which ninedigital multiplicand needs the smallest/largest
multiplier to become palindromic ?

There are 9! or 362880 ninedigital numbers to search through.
I started by checking out a few limit values to get the puzzle going !
Can you come up with better results than these ?

NinedigitalMultiplierSmallest (?) Palindrome
???
9876543219997777777779

NinedigitalMultiplierLargest (?) Palindrome
1234567894340315535841353148535
12345679834334003842387661716678324
12346789540540901950054998189945005
91827364556364427675175796844486975715

An extra challenge !
Exist there other 'palindromic' multipliers for some ninedigital multiplicands ?
World!Of Ninedigitals

Contributions from Daniel Fischer (email)
[ June 19 & 20, 2008 ]

This topic was brought to my attention by a posting of one of the members of
the Project Euler forum :
https://projecteuler.chat/viewtopic.php?f=2&t=955

Here are Daniel Fischer's latest results
from a keen program he wrote in the Haskell computer language.

 The smallest number k which, multiplied by 8991 gives a palindrome is 111222333444555666777889, the palindrome is 10^27-1. Prelude FPalindromes> findSmallestMP 8991 Looking for 5-digit palindromes Looking for 6-digit palindromes Looking for 7-digit palindromes Looking for 8-digit palindromes Looking for 9-digit palindromes Looking for 10-digit palindromes Looking for 11-digit palindromes Looking for 12-digit palindromes Looking for 13-digit palindromes Looking for 14-digit palindromes Looking for 15-digit palindromes Looking for 16-digit palindromes Looking for 17-digit palindromes Looking for 18-digit palindromes Looking for 19-digit palindromes Looking for 20-digit palindromes Looking for 21-digit palindromes Looking for 22-digit palindromes Looking for 23-digit palindromes Looking for 24-digit palindromes Looking for 25-digit palindromes Looking for 26-digit palindromes Looking for 27-digit palindromes Found one! 999999999999999999999999999 is the smallest of [999999999999999999999999999] 999999999999999999999999999 (0.67 secs, 126891708 bytes) Prelude FPalindromes Control.Monad> it `divMod` 8991 (111222333444555666777889,0) (0.00 secs, 527340 bytes)

 That number, by the way, is also the smallest multiplier to make 818181 palindromic: Prelude FPalindromes Control.Monad> findSmallestMP 818181 Looking for 7-digit palindromes Looking for 8-digit palindromes Looking for 9-digit palindromes Looking for 10-digit palindromes Looking for 11-digit palindromes Looking for 12-digit palindromes Looking for 13-digit palindromes Looking for 14-digit palindromes Looking for 15-digit palindromes Looking for 16-digit palindromes Looking for 17-digit palindromes Looking for 18-digit palindromes Looking for 19-digit palindromes Looking for 20-digit palindromes Looking for 21-digit palindromes Looking for 22-digit palindromes Looking for 23-digit palindromes Looking for 24-digit palindromes Looking for 25-digit palindromes Looking for 26-digit palindromes Looking for 27-digit palindromes Looking for 28-digit palindromes Looking for 29-digit palindromes Found one! 90999999999999999999999999909 is the smallest of [90999999999999999999999999909 ,91989999999999999999999998919 ,91999998999999999999989999919 ,91999999989999999998999999919 ,91999999999998989999999999919 ,92979999999999999999999997929 ,92989998999999999999989998929 ,92989999989999999998999998929 ,92989999999998989999999998929 ,92999997999999999999979999929] 90999999999999999999999999909 (93.73 secs, 19421462360 bytes) Prelude FPalindromes Control.Monad> it `divMod` 818181 (111222333444555666777889,0) (0.01 secs, 531680 bytes)

I have since yesterday further improved my algorithm, so 8991 is settled
in 0.05s, and 818181 in 7.6s now.
However, 9801 still takes 12.6 minutes (about 90 minutes yesterday) and
81818181 takes almost 20 minutes (multiplier is
11117333444506667778277788893889), so there are some hard cases remaining.

topic, I will not yet explain my algorithm or send the code. But I tend to
believe we won't, in which case I'll be happy to explain and perhaps (after
cleaning it up) send you the code (can you read Haskell, by the way?).

Can you set a new challenge number for the topic ?

81818181 is pretty bad, I haven't yet gone for 8181818181.
810801081 is relatively harmless (that shouldn't take very long to
brute-force), probably too harmless.
81081081 has a cute 20-digit multiplier, 810081 has a 16-digit multiplier, so
a determined brute-forcer could perhaps do it.
The sequence 89...91 generates some large minimal multipliers, too.
See table at the end of   WONplate 36

 For the pandigitals, I found time ./palindromes 123467895 Found one! 50054998189945005 The multiplier is 405409019 real    1m18.726s user    1m4.080s sys      0m0.120s and later time ./palindromes 918273645 Found one! 5175796844486975715 The multiplier is 5636442767 real    0m2.338s user    0m2.090s sys     0m0.010s

Continued at WONplate 223

A000096 Prime Curios! Prime Puzzle
Wikipedia 96 Le Nombre 96 Numberland 96
```

```