World!Of
Numbers

WON plate
96 |


A follow-up 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 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 :
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^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.

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
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




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














[ TOP OF PAGE]


( © All rights reserved )
Patrick De Geest - Belgium - Short Bio - Some Pictures
E-mail address : pdg@worldofnumbers.com