What you have shown is twisted spaghetti code full of misguided micro-optimizations. Your algorithm is not at all obvious. This is it cleaned up, so that we can analyze it:
#!/usr/bin/env perl
use strict;
use warnings;
use feature 'say';
my $n = 3;
my $lo = 10**($n - 1);
my $hi = (10**$n) - 1;
my $smallest_product = 10**(2*$n - 2);
my $index = 0;
for (my $sum = 2*$hi; ; $sum--) {
my $a = int $sum/2;
my $b = $sum - $a;
last if $a*$b < $smallest_product;
while ($lo <= $a and $b <= $hi) {
$index++;
my $candidate = $a * $b;
if ($candidate eq reverse $candidate) {
say "$candidate = $a * $b (candidate $index)"
if $candidate > $smallest_product;
exit if $n > 2;
$a--;
$b++;
}
}
For this specific problem, your algorithm is actually quite fast, and the solution is found very early. But the search method is flawed, and in the grand scale of things very inefficient.
The below image illustrates how you walk through your search space.
Your primary search direction is through the sums of \$a + b\$. Then you vary \$a\$ and \$b\$ for each constant sum within the bounds \$a, b \in [lo, hi]\$. This means that you visit every pair \$(a, b)\$ in the shaded area. The problem is that most of these \$(hi - lo)^2 / 2 > 400000\$ visited points will not form palindromic products – there are only \$1800\$ palindromes with 5 or 6 digits.
Since you visit all possible products, you will encounter many palindromes more than once (in total, roughly half of your results are duplicates).
You will not see all palindromes in descending order. For each sum, when you only vary \$a\$ and \$b\$, the products will descend since their product is largest when they are closest. But between different sums, there is no ordering.
Let's look at this in an example with smaller numbers. In the following table, I have entered the products of their coordinates:
5| 25 hi = 5
| lo = 1
4| 16 20
|
3| 9 12 15
|
2| 4 6 8 10
|
1| 1 2 3 4 5
|
0|0__0__0__0__0__0_
0 1 2 3 4 5
And this table looks at the descending sums and the order in which these sums find products:
SUM : SEQUENCE
10 : 25
9 : 20
8 : 16, 15
7 : 12, 10
6 : 9, 8, 5
5 : 6, 4
4 : 4, 3
3 : 2
2 : 1
Oh look, we came across 4
twice! What a waste. Also, the total sequence of elements is 25, 20, 16, 15, 12, 10, 9, 8, 5, 6, 4, 4, 3, 2, 1
– note that 5
preceded 6
. So if both 5
and 6
were solutions and we'd stop at the first solution, we would not have found the largest solution.
Given that this diagonal search has a few very important flaws (the first solution isn't guaranteed to be the largest solution), we could have used a far simpler search that shares all its advantages and shortcomings, e.g. searching primarily by descending \$a\$ value and secondarily by descending \$b\$:
Yes, this is exactly brute-forcing via two nested loops, but that is exactly equivalent to what your current algorithm is doing. The search space is the same, only the order is simplified.
I mentioned earlier that there are less than 2000 possible palindromes in that search space. In general, it would be far more efficient to generate these palindromes, and then check whether two integer factors \$a\$ and \$b\$ exist which fall inside certain bounds. Generating the palindromes is trivial (for a fixed length with nested loops, otherwise by recursion), the difficult part is calculating the divisors. A palindrome-driven search will need less than half as many iterations for this search space, but might (in this specific case) lose the race to the first palindrome by a few iterations.