|
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
| 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^27–1 |
| 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 :
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.
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
|
Continued at WONplate 223
|
A000096 
TOP OF PAGE]
- Short Bio - Some Pictures