Largest palindrome product

Largest palindrome product is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Task description is taken from Project Euler (https://projecteuler.net/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.

F#

<lang fsharp> // Largest palindrome product. Nigel Galloway: November 3rd., 2021 let fN g=let rec fN g=[yield g%10; if g>=10 then yield! fN(g/10)] in let n=fN g in n=List.rev n printfn "%d" ([for n in 100..999 do for g in n..999->n*g]|>List.filter fN|>List.max) </lang>

Output:

906609

Go

Translation of: Wren

18 digit integers are within the range of Go's uint64 type though finding the result for 9-digit number products takes a while - around 15 seconds on my machine. <lang go>package main

import "fmt"

func reverse(n uint64) uint64 {

   r := uint64(0)
   for n > 0 {
       r = n%10 + r*10
       n /= 10
   }
   return r

}

func main() {

   pow := uint64(10)

nextN:

   for n := 2; n < 10; n++ {
       low := pow * 9
       pow *= 10
       high := pow - 1
       fmt.Printf("Largest palindromic product of two %d-digit integers: ", n)
       for i := high; i >= low; i-- {
           j := reverse(i)
           p := i*pow + j
           // k can't be even nor end in 5 to produce a product ending in 9
           for k := high; k > low; k -= 2 {
               if k % 10 == 5 {
                   continue
               }
               l := p / k
               if l > high {
                   break
               }
               if p%k == 0 {
                   fmt.Printf("%d x %d = %d\n", k, l, p)
                   continue nextN
               }
           }
       }
   }

}</lang>

Output:

Largest palindromic product of two 2-digit integers: 99 x 91 = 9009
Largest palindromic product of two 3-digit integers: 993 x 913 = 906609
Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099
Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699
Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999
Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999
Largest palindromic product of two 8-digit integers: 99999999 x 99990001 = 9999000000009999
Largest palindromic product of two 9-digit integers: 999980347 x 999920317 = 999900665566009999

Julia

<lang julia>using Primes

function twoprodpal(factorlength)

   maxpal = Int128(10)^(2 * factorlength) - 1
   dig = digits(maxpal)
   halfnum = dig[1:length(dig)÷2]
   while any(halfnum .!= 0)
       prodnum = evalpoly(Int128(10), [reverse(halfnum); halfnum])
       facs = twofac(factorlength, prodnum)
       if !isempty(facs)
           println("For factor length $factorlength, $(facs[1]) * $(facs[2]) = $prodnum")
           break
       end
       halfnum = digits(evalpoly(Int128(10), halfnum) - 1)
   end

end

function twofac(faclength, prodnum)

   f = [one(prodnum)]
   for (p, e) in factor(prodnum)
       f = reduce(vcat, [f * p^j for j in 1:e], init=f)
   end
   possiblefacs = filter(x -> length(string(x)) == faclength, f)
   for i in possiblefacs
       j = prodnum ÷ i
       j ∈ possiblefacs && return sort([i, j])
   end
   return typeof(prodnum)[]

end

@Threads.threads for i in 2:12

   twoprodpal(i)

end

</lang>

Output:

For factor length 2, 91 * 99 = 9009
For factor length 3, 913 * 993 = 906609
For factor length 4, 9901 * 9999 = 99000099
For factor length 5, 99681 * 99979 = 9966006699
For factor length 6, 999001 * 999999 = 999000000999
For factor length 7, 9997647 * 9998017 = 99956644665999
For factor length 8, 99990001 * 99999999 = 9999000000009999
For factor length 9, 999920317 * 999980347 = 999900665566009999
For factor length 10, 9999986701 * 9999996699 = 99999834000043899999
For factor length 11, 99999943851 * 99999996349 = 9999994020000204999999
For factor length 12, 999999000001 * 999999999999 = 999999000000000000999999

Perl

Library: ntheory

<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'divisors';

for my $l (2..7) {

   LOOP:
   for my $p (reverse map { $_ . reverse $_ } 10**($l-1) .. 10**$l - 1)  {
       my @f = reverse grep { length == $l } divisors $p;
       next unless @f >= 2 and $p == $f[0] * $f[1];
       say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP;
   }

}</lang>

Output:

Largest palindromic product of two 2-digit integers: 91 × 99 = 9009
Largest palindromic product of two 3-digit integers: 913 × 993 = 906609
Largest palindromic product of two 4-digit integers: 9901 × 9999 = 99000099
Largest palindromic product of two 5-digit integers: 99681 × 99979 = 9966006699
Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999
Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999

Raku

<lang perl6>use Inline::Perl5; my $p5 = Inline::Perl5.new(); $p5.use: 'ntheory'; my &divisors = $p5.run('sub { ntheory::divisors $_[0] }');

.say for (2..12).map: {.&lpp};

multi lpp ($oom where {!($_ +& 1)}) { # even number of multiplicand digits

   my $f = +(9 x $oom);
   my $o = $oom / 2;
   my $pal = +(9 x $o ~ 0 x $oom ~ 9 x $o);
   sprintf "Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $f, $f, $pal

}

multi lpp ($oom where {$_ +& 1}) { # odd number of multiplicand digits

   my $p;
   (+(1 ~ (0 x ($oom - 1))) .. +(9 ~ (9 x ($oom - 1)))).reverse.map({ +($_ ~ .flip) }).map: -> $pal {
       for my @factors = divisors("$pal")».Int.grep({ .chars == $oom }).sort( -* ) {
           next unless $pal div $_ ∈ @factors;
           $p = sprintf("Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $_, $_, $pal);
           last;
       }
       last if $p;
   }
   $p

}</lang>

Largest palindromic product of two  2-digit integers: 91 × 99 = 9009
Largest palindromic product of two  3-digit integers: 913 × 993 = 906609
Largest palindromic product of two  4-digit integers: 9901 × 9999 = 99000099
Largest palindromic product of two  5-digit integers: 99681 × 99979 = 9966006699
Largest palindromic product of two  6-digit integers: 999001 × 999999 = 999000000999
Largest palindromic product of two  7-digit integers: 9997647 × 9998017 = 99956644665999
Largest palindromic product of two  8-digit integers: 99990001 × 99999999 = 9999000000009999
Largest palindromic product of two  9-digit integers: 999920317 × 999980347 = 999900665566009999
Largest palindromic product of two 10-digit integers: 9999900001 × 9999999999 = 99999000000000099999
Largest palindromic product of two 11-digit integers: 99999943851 × 99999996349 = 9999994020000204999999
Largest palindromic product of two 12-digit integers: 999999000001 × 999999999999 = 999999000000000000999999

Ring

<lang ring>? "working..."

prod = 1 bestProd = 0 // maximum 3 digit number max = 999 // both factors must be >100 for a 6 digit product limitStart = 101 // one factor must be divisible by 11 limitEnd = 11 * floor(max / 11) second = limitStart iters = 0

// loop from hi to low to find the best result in the fewest steps for n = limitEnd to limitStart step -11

   // with n falling, the lower limit of m can rise with
   // the best-found-so-far second number. Doing this
   // lowers the iteration count by a lot.
   for m = max to second step -2
       prod = n * m
       if isPal(prod)
           iters++
           // exit when the product stops increasing
           if bestProd > prod
               exit
           ok
           // maintain the best-found-so-far result
           first = n
           second = m
           bestProd = prod
       ok
   next

next

put "The largest palindrome is: " ? "" + bestProd + " = " + first + " * " + second ? "Found in " + iters + " iterations" put "done..."

func isPal n

   x = string(n)
   l = len(x) + 1
   i = 0
   while i < l
       if x[i++] != x[l--]
           return false
       ok
   end
   return true</lang>

Output:

working...
The largest palindrome is: 906609 = 913 * 993
Found in 6 iterations
done...

Wren

The approach here is to manufacture palindromic numbers of length 2n in decreasing order and then see if they're products of two n-digit numbers. <lang ecmascript>var reverse = Fn.new { |n|

   var r = 0 
   while (n > 0) {
       r = n%10 + r*10
       n = (n/10).floor
   }
   return r

}

var pow = 10 for (n in 2..7) {

   var low = pow * 9
   pow = pow * 10
   var high = pow - 1
   System.write("Largest palindromic product of two %(n)-digit integers: ")
   var nextN = false
   for (i in high..low) {
       var j = reverse.call(i)
       var p = i * pow + j
       // k can't be even nor end in 5 to produce a product ending in 9
       var k = high
       while (k > low) {
           if (k % 10 != 5) {
               var l = p / k
               if (l > high) break
               if (p % k == 0) {
                   System.print("%(k) x %(l) = %(p)")
                   nextN = true
                   break
               }
           }
           k = k - 2
       }
       if (nextN) break
   }

}</lang>

Output:

Largest palindromic product of two 2-digit integers: 99 x 91 = 9009
Largest palindromic product of two 3-digit integers: 993 x 913 = 906609
Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099
Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699
Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999
Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999

XPL0

<lang XPL0>func Rev(A); \Reverse digits int A, B; [B:= 0; repeat A:= A/10;

       B:= B*10 + rem(0);

until A = 0; return B; ];

int Max, M, N, Prod; [Max:= 0; for M:= 100 to 999 do

   for N:= M to 999 do
       [Prod:= M*N;
       if Prod/1000 = Rev(rem(0)) then
           if Prod > Max then Max:= Prod;
       ];

IntOut(0, Max); ]</lang>

Output:

906609