Edit: There are two solutions in C# below, a short one in the middle and a more-optimized one at the end.
I posted a solution in C a few years ago here that uses a few more optimizations than pgs’. (Now rewritten in C# below, in a more functional style.) You can read the source if you like, but here’s a description of the algorithm.
We’re looking for a six-digit number, because a product of two three-digit numbers must be less than 1,000×1,000 = 1,000,000. The basic approach is to generate the 900 six-digit palindromes, from 999,999 to 100,001, in descending order, and test whether each is a solution by attempting a factorization. Because we generate all palindromes in descending order, the first solution we find is the greatest. There is no need to search any further; that is our answer.
We can optimize the factorization by noticing that a six-digit palindrome abccba = 100001 a + 10010 b + 1100 c = 11 (9091 a + 910 b + 100 c). So if we have a six-digit palindrome p = xy, 11 is a prime factor of p, so 11 must be a factor of x or y. We can pick either to be the multiple of 11, so let’s choose x. The smallest three-digit multiple of 11 is 110 and the greatest is 990. The other factor y = p/x is between 100 and 999, so x = p/y is between p/999 and p/100. That gives us the following restrictions on x:
- 11|x
- 110 ≤ x ≤ 990
- p/999 ≤ x ≤ p/100
If an x meets all of these conditions, our p is the product of two three-digit numbers. I expressed this as a set of four nested loops: the three initial digits of the palindrome, plus the possible values of x. There are 900 possible palindromes and, for each one, fewer than 81 multiples of 11 in range to be candidates for x, making the search space tiny.
The Code
I’m new to C#, so I’d appreciate a code review myself.
using System; using System.Collections.Generic; using System.Linq; static class Euler4 { static public bool hasFactors(Int32 p) { // Find candidates for x such that p = 11*x*y, where x is an integer // between 10 and 90, and y is an integer between 100 and 999. Any // pair of three-digit factors will decompose into 11*x and y. // Use the greater lower bound that makes y <= 999 and 11*x >= 100. Int32 lower = Math.Max((p/11+998)/999, 10); // Use the lesser upper bound that makes y >= 100 and 11*x <= 999. Int32 upper = Math.Min(p/(100*11), 90); // Calculate the extent of the range: Int32 count = Math.Max(upper-lower+1, 0); return Enumerable.Range(lower, count).Any(x => p%x == 0); } static public IEnumerable<Int32> listPalindromes() // Generates a lazily-evaluated list of palindromes in descending order. { for (Int32 a = 9; a >= 1; --a ) for (Int32 b = 9; b >= 0; --b ) for (Int32 c = 9; c >= 0; --c ) yield return a*100001 + b*10010 + c*1100; } // The solution to Euler problem 4: static public readonly Int32 answer = listPalindromes().First(hasFactors); static public void Main() { Console.WriteLine(answer); } };
Generalizing the Problem
Peter Taylor mentioned he was benchmarking my algorithm for finding eight-digit and ten-digit palindromic numbers. It would therefore be polite for me to prove that it actually works: that is, that any palindromic number whose length is even is a multiple of 11. (It does not work for odd lengths: all palindromes 101, 10001, 1000001, ... are congruent to 2, mod 11.) I’m sure I’m not the first person to do this and that he already knew it was valid.
Theorem:Any palindrome whose length n is even is a multiple of 11.
Basis case: Any two-digit palindrome (00, 11, 22, ...) is a digit times 11.
Inductive step: Suppose any palindrome of length n-2 is a multiple of 11.
Any palindrome of length n consists of a palindrome of length n-2 enclosed by a pair of identical digits. (For example, 1221 is 22 surrounded by 1s.) This can be written as (1+10ⁿ⁻¹) a + 10 b, where a is a digit and b is a palindrome of length n-2. For example, 321123 = (1+10⁶⁻¹)·3 + 10·2112.
Because n is even, n-1 is odd. We know 10 ≡ -1 (mod 11), so 1+10ⁿ⁻¹ ≡ 1+(-1)ⁿ⁻¹ ≡ 1-1 ≡ 0 (mod 11). Our inductive hypothesis tells us that b is also a multiple of 11, and therefore so is 10·b. Our n-digit palindrome is the sum of two multiples of 11, so it is a multiple of 11 itself. ∎
Other Optimizations
There is some more low-hanging fruit that could be picked here.
The best one is that it’s easy to test whether our palindrome p is odd or even. Any product of an even number is even, so if p is odd, both of its factors must be odd too. Dividing by another prime like 11 keeps the parity, and therefore, when p is odd, we only need to check the odd candidates for x. That cuts the search space in half, half the time, for a savings of 25%.
This generalizes to other primes than 2: p = xy is divisible by some prime q if and only if x or y are divisible by q. We could use the Chinese Remainder Theorem to test several prime factors at once: a number is divisible by 2 if and only if it is congruent to 0, 2 or 4 mod 6, and divisible by 3 if and only if it is congruent to 0 or 3 mod 6, so we can take r = p mod 6. If r is 1 or 5, then x mod 6 must be 1 or 5 as well. If r is 2 or 4, then x mod 6 cannot be 0 or 3. If r is 3, x mod 6 cannot be 0, 2 or 4. That reduces the search space by two-thirds one-third of the time, one-third another third of the time and one-half another sixth of the time, pruning the search space by a total of 5/12, or 41.6%. We could extend this to 2, 3, and 5 by going modulo 30, with severely increasing complexity and diminishing returns.
Second Solution
This solution uses the optimization from the previous section. It might not actually be faster. For example, on some machines, the work to skip checking some values of x might take longer than just doing the trial divisions.
using System; using System.Collections.Generic; using System.Linq; static class Euler4 { static public bool hasFactors(int p) { return xCandidates(p).Any(x => p%x == 0); } static public IEnumerable<int> listPalindromes() // Generates a lazily-evaluated list of palindromes in descending order. { for (int a = 9; a >= 1; --a ) for (int b = 9; b >= 0; --b ) for (int c = 9; c >= 0; --c ) yield return a*100001 + b*10010 + c*1100; } static public IEnumerable<int> xCandidates(int p) // Generate a lazily-evaluated list of potential values of x such that // p == 11*x*y, and both 11*x and y are between 100 and 999. { int q = p/11; // All palindromes of even length are multiples of 11. // The greatest lower bound on x such that 11*x >= 100 and y <= 999. int lower = Math.Max(10, (q+(999-1))/999); // The least upper bound on x such that 11*x <= 999 and y >= 100. int upper = Math.Min(90, q/100); int k = q%6; if (k == 1 || k == 5) { // Neither 2 nor 3 is a factor of z. // The possible values of x%6 are 1 and 5. int r = lower%6; bool mod1 = r <= 1; int i = lower - r + (mod1 ? 1 : 5); while (i <= upper) { yield return i; i += mod1 ? 4 : 2; mod1 = !mod1; } // end while } else if (k == 2 || k == 4) { // 3 cannot be a factor of x. // The possible values of x%6 are 1, 2, 4 and 5. int r = lower%6; int m = (r == 3 || r == 0) ? r+1 : r; int i = lower - r + m; while (i <= upper) { yield return i; if (m == 5) { i += 2; m = 1; } else if ( m == 2) { i += 2; m = 4; } else { // m == 1 || m == 4 ++i; ++m; } // end if } // end while } else if (k == 3) { // 2 cannot be a factor of x. // The possible values of x%6 are 1, 3 and 5. int i = lower + 1 - lower%2; while (i <= upper) { yield return i; i += 2; } // end while } else { // k == 0. Because y%6 could be 0, x%6 can be anything. for ( int i = lower; i <= upper; ++i ) yield return i; } // end if } // The solution to Euler problem 4: static public readonly int answer = listPalindromes().First(hasFactors); static public void Main() { Console.WriteLine(answer); } };
