Re: Largest palindrome number for a 3 digit product of 2 numbers

The search space can be trimmed:

#!/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]

Comment on Re: Largest palindrome number for a 3 digit product of 2 numbers Download Code

Replies are listed 'Best First'.
Re^2: Largest palindrome number for a 3 digit product of 2 numbers by pr33 (Scribe) on Jul 06, 2017 at 07:14 UTC
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]	[reply] [d/l]
Re^3: Largest palindrome number for a 3 digit product of 2 numbers by salva (Canon) on Jul 06, 2017 at 07:52 UTC
Multiplication is a commutative operation (ab and ba 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 ac >= bc, 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.	[reply] [d/l] [select]