A followup to WONplate 36
and a new ninedigital puzzle...
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 muchimproved 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
Multiplicand  Smallest Possible Multiplier  Palindrome 
81  12345679  (easy)  999999999 
8181  1173450678278939  [ March 10, 2001 ]  9599999998999999959 
8891  8546948927  75990922909957 
8991  111222333444555666777889
by Daniel Fischer [ June 19, 2008 ] 
999999999999999999999999999
or 10^271 
9801  2030405060708091  [ 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 ?
Ninedigital  Multiplier  Smallest (?) Palindrome 
?  ?  ? 
987654321  99  97777777779 
Ninedigital  Multiplier  Largest (?) Palindrome 
123456789  4340315  535841353148535 
123456798  343340038  42387661716678324 
123467895  405409019  50054998189945005 
918273645  5636442767  5175796844486975715 
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 :
http://forum.projecteuler.net/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^271.
Prelude FPalindromes> findSmallestMP 8991
Looking for 5digit palindromes
Looking for 6digit palindromes
Looking for 7digit palindromes
Looking for 8digit palindromes
Looking for 9digit palindromes
Looking for 10digit palindromes
Looking for 11digit palindromes
Looking for 12digit palindromes
Looking for 13digit palindromes
Looking for 14digit palindromes
Looking for 15digit palindromes
Looking for 16digit palindromes
Looking for 17digit palindromes
Looking for 18digit palindromes
Looking for 19digit palindromes
Looking for 20digit palindromes
Looking for 21digit palindromes
Looking for 22digit palindromes
Looking for 23digit palindromes
Looking for 24digit palindromes
Looking for 25digit palindromes
Looking for 26digit palindromes
Looking for 27digit 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 7digit palindromes
Looking for 8digit palindromes
Looking for 9digit palindromes
Looking for 10digit palindromes
Looking for 11digit palindromes
Looking for 12digit palindromes
Looking for 13digit palindromes
Looking for 14digit palindromes
Looking for 15digit palindromes
Looking for 16digit palindromes
Looking for 17digit palindromes
Looking for 18digit palindromes
Looking for 19digit palindromes
Looking for 20digit palindromes
Looking for 21digit palindromes
Looking for 22digit palindromes
Looking for 23digit palindromes
Looking for 24digit palindromes
Looking for 25digit palindromes
Looking for 26digit palindromes
Looking for 27digit palindromes
Looking for 28digit palindromes
Looking for 29digit 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.
Since it is possible that we will make a Project Euler problem about this
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
bruteforce), probably too harmless.
81081081 has a cute 20digit multiplier, 810081 has a 16digit multiplier, so
a determined bruteforcer 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
