Task
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Some thoughts about the task
Before jumping onto the task, let's stop for a moment and try to frame it. We basically have two choices:
We could try all factor combinations and check for each one if it's a palindrome.
We could generate all possible palindromes and test if we can express them as multiplication of two three-digit numbers.
If we went for choice #1, how many calculations would we have? Each factor can take any value between 100 and 999. Since multiplication is commutative (a*b=b*a), we need to test 899^2/2 = ~400.000 calculations if we use a naive brute-force algorithm.
Now let's evaluate option 2. How many palindromes can we expect to find? Our range goes from 100*100 to 999*999, i. e. between 10000 - 998001.
For five-digit numbers, we have 9 choices for the first digit plus 10 choices for the second and third digit: 900 numbers (the fourth and fifth digit are equal to the first and second). For six-digits, it's the same - another 900 numbers. So we only have 1800 palindrome numbers to test if they can be formed by two three-digit numbers. Seems not so much, right?
Unfortunately there is a big problem: factorization is a very resource-intensive task. As we have learned already in the last post, there is no efficient algorithm to determine the prime factors of a number. It can take up to sqrt(N) calculations, i. e. up to 100 and 999 calculations per number. After we got the prime numbers, we need to check if these numbers can be formed to two three-digit numbers.
In other words, it seems more promising to try all factor combinations and determine if they are palindromic than going the other way around. As we will see, with some minor modifications it will even require much less than 400.000 calculations.
Checking palindromes
A palindrome is a word that reads the same forward as backwards, such as "madam" or "racecar. Obviously numbers can be palindromes as well, like 12321.
Identifying palindromes in PicoLisp is easy, there is a number of built-in functions to help us with that. First of all, we can use chop to split a string into single characters which are returned as list.
: (chop "madam")
-> ("m" "a" "d" "a" "m")
: (chop 123)
-> ("1" "2" "3")
As you can see, it also works with numbers. Secondly, we can reverse a list with the reverse function.
: (reverse ("1" "2" "3"))
-> ("3" "2" "1")
Now we put it together to get our palindrome function. Since ? is not a reserved symbol, it is often used in PicoLisp to indicate a checking function (lik num?, pat?, circ?). So let's call it palindrome?:
(de palindrome? (S)
(= (setq S (chop S)) (reverse S)) )
palindrome? returns T for palindromes and NIL otherwise.
Getting the factor combinations
To return the complete factor combinations, we can use two nested for-loops. We have two factors A and B, where A >= B.
(for (A 999 (>= A 100) (dec A))
(for (B A (>= B 100) (dec B))
Now as a first step, let's get out all palindrome combinations and print them to the screen.
(let P (* A B)
(when (palindrome? P)
(prinl P " " A " " B)
Now we can test it and count the number of output lines with pil <filename.l> | wc -l. We get 1239 lines. So there are 1239 palindromes formed out of two 3-digit numbers, and now we need to find the largest one.
Filtering the results
Let's add another condition: P should only be returned if it is larger than the last previously found palindrome. Let's initialize a variable Palin to NIL and re-set it if P > Palin:
(let Palin NIL
(for (A 999 (>= A 100) (dec A))
(for (B A (>= B 100) (dec B))
(let P (* A B)
(when
(and
(> P Palin)
(palindrome? P) )
(setq Palin P)
(prinl Palin " " A " " B) ) ) ) ) )
Now this cuts our output down to only two lines:
$ pil palindrome.l
580085 995 583
906609 993 913
However, in the background, all 400.000 calculations are still running of course. This smells like there's an unefficiency hidden here. What can we do?
Improving the exit condition
Currently, the for loops are running until both A and B have reached 100. But actually this is not required:
We can see from the first output that we have a palindrome combination at A=995 and B=583. This means that for any palindrome P larger than 995*583, A must be minimum sqrt(P). Why? Because we know that A >= B, so if A < sqrt(P), then A * B < P.
So we can adjust our loop to that:
(let MinA 100
...
(for (A Max (>= A Min) (dec A))
(for (B A (>= B 100) (dec B))
...
(setq Min (sqrt Palin)) ) ) )
This cuts down our loop by 90% to 42073 calculations.
Now we can even take this one step further. There is also a minimum limit on B. From A * B >= P follows P / A =< B. In PicoLisp:
(let (AMin 100 BMin 100)
(for (A 999 (>= A AMin) (dec A))
(when Palin
(setq BMin (/ Palin A)) )
(for (B A (>= B BMin) (dec B))
...
This cuts down our number of calculation to less than 7000!
The final function
As last step, let's wrap a function around it for more reusability.
(de largest_palin_prod (Min Max)
(let (Palin NIL AMin Min BMin Min)
...
Palin) )
The final code can be found here.
Sources
- https://projecteuler.net/problem=4
- https://software-lab.de/doc/index.html
