#!/usr/bin/perl

use strict;
use warnings;

my $max = shift // 999;
my $min = shift // 100;

my $best = 0;

I: for (my $i = $max; $i >= $min; $i--) {
 J: for (my $j = $max; $j >= $i; $j--) {
        my $prod = $i * $j;
        if ($prod <= $best) {
            last I if $j == $max;
            last J;
        }
        if ($prod == reverse $prod) {
            $best = $prod;
            print "$i x $j -> $prod\n";
            last J;
        }
    }
}
print "best: $best\n";
[download]

Thanks . Have some confusion here . If none of the condition in the Inner Loop satisfies , Does the loop continue to execute the next iteration of the Outer loop or Is in't supposed to repeatedly execute the inner loop for each of the value of Inner loop ($i here)

I have added a print debugger statement in the Inner for loop and here is what I get for the first few iterations

So 999 x 999 doesn't satisfy the conditions in the Inner Loop and I was then expecting i to be 999 and j to be 998 , But I see the print giving I as 998 and j as 999 .. Can you please help walkover this algorithm if possible ?

  my $c = 0;
  I: for (my $i = $max; $i >= $min; $i--) {
 J: for (my $j = $max; $j >= $i; $j--) {
        my $prod = $i * $j;
        $c++;
        print "Iteration: $c, I: $i, J: $j Product: $prod\n";
..............
.............

Iteration: 1, I: 999, J: 999 Product: 998001
Iteration: 2, I: 998, J: 999 Product: 997002
Iteration: 3, I: 998, J: 998 Product: 996004
Iteration: 4, I: 997, J: 999 Product: 996003
Iteration: 5, I: 997, J: 998 Product: 995006
Iteration: 6, I: 997, J: 997 Product: 994009
Iteration: 7, I: 996, J: 999 Product: 995004
Iteration: 8, I: 996, J: 998 Product: 994008
Iteration: 9, I: 996, J: 997 Product: 993012
[download]

Multiplication is a commutative operation (a*b and b*a are the same quantity). That means that we can eliminate half of the operations making the inner J loop stop when $j becomes lesser than $i. You can see that explicit as the condition of the J loop.

Other trick used to trim the search space is taking into account that for natural numbers if a >= b then a*c >= b*c, so as soon as we found a $j that makes a palindrome we can stop the J loop.

Finally whatever becomes $prod <= $best we can also stop J; or even I if $j is still at 999.

# file pal.pl

my $d = shift;
my ($p, $n, @r);

my $r1 = - (9 x $d);
my $r2 = - ((9 x ($d-1)) +1);

IT: for my $f ($r1 .. $r2 ) { 
    for ($f .. $r2) {
        $p = $f * $_;
        last if $p < $r[2];
        if ($p eq reverse $p) {
            if ($n < $p) {
                $n = $p;
                @r = ($f,$_,$p);
                next IT;
            }
        }
    }
    last if -$f**2 < $r[2];
}
print -$r[0]," * ",-$r[1]," = $r[2]\n";
__END__
993 * 913 = 906609
[download]

qwurx [shmem] ~> time perl pal.pl 3
993 * 913 = 906609

real    0m0.004s
user    0m0.000s
sys    0m0.000s
[download]

Thanks . So you are checking the condition if the Square of the Number is less than the current product found in the second statement of the last

Yes. If the square of the greater operand is smaller than the highest palindrome found, further rundown of either factor can be stopped. There is no higher number to be found.

My algorithm differs from salvas solution, which probes the highest factors for a valid product, while mine runs down one factor to its lowest value. For some amount of digits it turns out to be faster than salva's, for others it is much, much slower (e.g. 9 digits).

update: Another approach would be:

• Starting from the square of the highest number, construct the next lower palindrome number
• factorize that number
• check for any cobination of factors whether their product has the amount of digits wanted
• check if the remaining factors product also has the amount of digits wanted
• If so, stop there. Highest palindrome found.

I guess that for a large amount of digits this might be the fastest way.

perl -le'print map{pack c,($-++?1:13)+ord}split//,ESEL'

    my $rev = reverse $n;
[download]

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]

Thanks . That has helped the code to improve the execution time was getting m0.1s now using this .

Also reversing numbers, from biggest to smallest, gives the answer sooner:

#!/usr/bin/perl
use warnings;
use strict;


foreach my $num (reverse (999 ... 999*999)) {  # I skipped the 'produc
+t of two 3 digit integers' part: see LanX below

    if ($num eq reverse $num){
        print "largest palindrome is: $num\n";
        exit;
    }
}

# or just:
perl -we "for(reverse 999 .. 999*999){($_ eq reverse $_ )?(print qq(la
+rgest palindrome $_)and exit 0 ): 1}"

largest palindrome 997799
[download]

L*

997799 is the product of two 3 digit integers?

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)
Je suis Charlie!}