Skip to content

Problem 4: Largest palindrome product

Link to the problem: https://projecteuler.net/problem=4.

Problem 4

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.

A simple solution

Let our palindrom be \(P = a \cdot b\).

\(a\) and \(b\) being 3-digit long, they must lie between \(100\) and \(999\).

Then once we have calculated the product we just need to compute the reverse number (i.e. where all digits are reversed) and find that it is indeed the same number when a palindrome.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(defn reverse []
  (-> >= .n
      0 >= .reversed

      (Repeat
       (-> .n (Math.Mod 10) >= .mod
           .reversed (Math.Multiply 10) (Math.Add .mod) > .reversed
           .n (Math.Divide 10) > .n)
       :Forever true
       :Until (-> .n (Is 0)))
      .reversed))

(defn isPalindrome [n]
  (-> n (reverse) (Is n)))

(defwire main-wire
  0 >= .largest
  0 >= .a >= .b >= .ab

  (ForRange
   100 999
   (-> > .a
       (ForRange
        100 999
        (-> > .b
            .a (Math.Multiply .b) > .ab
            (When
             (-> (isPalindrome .ab) (And) .ab (IsMore .largest))
             (-> .ab > .largest))))))

  .largest (Assert.Is 906609 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:41.520] [T-876] [logging.cpp::62] [main-wire] Answer: 906609

A better solution

We can improve the previous implementation in two ways:

  • halving the calculations
  • counting downwards since we are looking for the largest palindrome

Halving the calculations comes from the fact that once we have checked for instance for \(a = 123\) and \(b = 456\), we don't need to check again for \(a = 456\) and \(b = 123\). In other words, we could assume \(a \leq b\).

Counting downwards means we start at \(999\) instead of \(100\) and we can stop once the product of \(a \cdot b\) is less than the largest palindrome we found so far.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(defn reverse []
  (-> >= .n
      0 >= .reversed

      (Repeat
       (-> .n (Math.Mod 10) >= .mod
           .reversed (Math.Multiply 10) (Math.Add .mod) > .reversed
           .n (Math.Divide 10) > .n)
       :Forever true
       :Until (-> .n (Is 0)))
      .reversed))

(defn isPalindrome [n]
  (-> n (reverse) (Is n)))

(defwire main-wire
  0 >= .largest
  0 >= .a >= .b >= .ab

  (ForRange
   999 100
   (-> > .a
       999 > .b
       999999 > .ab
       (Repeat
        (-> .a (Math.Multiply .b) > .ab
            (When
             (-> (isPalindrome .ab))
             (-> .ab > .largest))
            (Math.Dec .b))
        :Forever true
        :Until (-> .b (IsLess .a) (Or) .ab (IsLess .largest)))))

  .largest (Assert.Is 906609 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:41.611] [T-6232] [logging.cpp::62] [main-wire] Answer: 906609

A much better solution

This is all good but we can improve even further. Let the digits of \(P\) be \(x\), \(y\) and \(z\). Since \(P\) is a palindrome, we have:

\[ \begin{align} P & = 10^5x + 10^4y + 10^3z + 10^2z + 10y + x\\ & = 100001x + 10010y + 1100z \\ & = 11 (9091x + 910y + 100z) \end{align} \]

Since \(11\) is prime, at least one of the numbers \(a\) or \(b\) must have a factor of \(11\). In other words if \(a\) is not divisible by \(11\) then we know \(b\) necessarily must be.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
(defn reverse []
  (-> >= .n
      0 >= .reversed

      (Repeat
       (-> .n (Math.Mod 10) >= .mod
           .reversed (Math.Multiply 10) (Math.Add .mod) > .reversed
           .n (Math.Divide 10) > .n)
       :Forever true
       :Until (-> .n (Is 0)))
      .reversed))

(defn isPalindrome [n]
  (-> n (reverse) (Is n)))

(defwire main-wire
  0 >= .largest
  0 >= .a >= .b >= .db >= .ab

  (ForRange
   999 100
   (-> > .a
       (If (-> .a (Math.Mod 11) (Is 0))
           :Then (-> 999 > .b 1 > .db)
           :Else (-> 990 > .b 11 > .db))
       999999 > .ab
       (Repeat
        (-> .a (Math.Multiply .b) > .ab
            (When
             (-> (isPalindrome .ab))
             (-> .ab > .largest))
            .b (Math.Subtract .db) > .b)
        :Forever true
        :Until (-> .b (IsLess .a) (Or) .ab (IsLess .largest)))))

  .largest (Assert.Is 906609 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:41.696] [T-2896] [logging.cpp::62] [main-wire] Answer: 906609

More details on the Project Euler's website: https://projecteuler.net/overview=004.