I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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 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.

Stretch Goal

Find the largest palindrome made from the product of two n-digit numbers, where n ranges from 4 to 7.

Extended Stretch Goal

Find the largest palindrome made from the product of two n-digit numbers, where n ranges beyond 7,

## ALGOL 68

Translation of: Wren
`BEGIN # find the highest palindromic multiple of various sizes of numbers #    # returns n with the digits reversed #    PROC reverse = ( LONG INT v )LONG INT:         BEGIN            LONG INT r := 0 ;            LONG INT n := v;            WHILE n > 0 DO                r *:= 10; r +:= n MOD 10;                n OVERAB 10            OD;            r         END # reverse # ;     LONG INT pow := 10;    FOR n FROM 2 TO 7 DO        LONG INT low := pow * 9;        pow *:= 10;        LONG INT high := pow - 1;        print( ( "Largest palindromic product of two ", whole( n, 0 ), "-digit integers: " ) );        BOOL next n := FALSE;        LONG INT i := high + 1;        WHILE i -:= 1;              i >= low AND NOT next n        DO            LONG INT j = reverse( i );            LONG INT p = ( i * pow ) + j;            # k can't be even nor end in 5 to produce a product ending in 9 #            LONG INT k := high + 2;            WHILE k -:= 2;                  IF   k < low                  THEN FALSE                  ELIF k MOD 10 = 5                  THEN TRUE                  ELIF LONG INT l = p OVER k;                                l > high                  THEN FALSE                  ELIF p MOD k = 0 THEN                       print( ( whole( k, 0 ), " x ", whole( l, 0 ), " = ", whole( p, 0 ), newline ) );                       next n := TRUE;                       FALSE                  ELSE TRUE                  FI            DO SKIP OD        OD    ODEND`
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
```
Translation of: Ring

Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity.

`BEGIN # find the highest palindromic multiple of various sizes of numbers #    PROC is pal = ( LONG INT n )BOOL:         BEGIN             STRING x       = whole( n, 0 );             INT    l      := UPB x + 1;             BOOL   result := TRUE;             FOR i FROM LWB x WHILE i < l AND result DO                 l     -:= 1;                 result := x[ i ] = x[ l ]             OD;             result          END # is pal # ;     # maximum 2 digit number #    LONG INT max := 99;    # both factors must be >= 10for a 4 digit product #    LONG INT limit start := 10;    FOR w FROM 2 TO 7 DO        LONG INT best prod   := 0;        # one factor must be divisible by 11 #        LONG INT limit end = 11 * ( max OVER 11 );        LONG INT second   := limit start;        LONG INT first    := 1;        # loop from hi to low to find the best result in the fewest steps #        LONG INT n        := limit end + 11;        WHILE n -:= 11;              n >= limit start        DO            # 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. #            LONG INT m := max + 2;            WHILE m -:= 2;                  IF   m < second                  THEN FALSE                  ELIF LONG INT prod = n * m;                       best prod > prod                  THEN FALSE                  ELIF NOT is pal( prod )                  THEN TRUE                  ELSE # maintain the best-found-so-far result #                       first     := n;                       second    := m;                       best prod := prod;                       TRUE                  FI            DO SKIP OD        OD;         print( ( "Largest palindromic product of two ", whole( w, 0 )               , "-digit numbers: ", whole( first, 0 ), " * ", whole( second, 0 )               , " = ", whole( best prod, 0 )               , newline               )             );        max *:= 10;        max +:= 9;        limit start *:= 10    ODEND`
Output:
```Largest palindromic product of two 2-digit numbers: 99 * 91 = 9009
Largest palindromic product of two 3-digit numbers: 913 * 993 = 906609
Largest palindromic product of two 4-digit numbers: 9999 * 9901 = 99000099
Largest palindromic product of two 5-digit numbers: 99979 * 99681 = 9966006699
Largest palindromic product of two 6-digit numbers: 999999 * 999001 = 999000000999
Largest palindromic product of two 7-digit numbers: 9997647 * 9998017 = 99956644665999
```

## AWK

` # syntax: GAWK -f LARGEST_PALINDROME_PRODUCT.AWKBEGIN {    main(9)    main(99)    main(999)    main(9999)    exit(0)}function main(n,  i,j,max_i,max_j,max_product,product) {    for (i=1; i<=n; i++) {      for (j=1; j<=n; j++) {        product = i * j        if (product > max_product) {          if (product ~ /^9/ && product ~ /9\$/) {            if (product == reverse(product)) {              max_product = product              max_i = i              max_j = j            }          }        }      }    }    printf("%1d: %4s * %-4s = %d\n",length(n),max_i,max_j,max_product)}function reverse(str,  i,rts) {    for (i=length(str); i>=1; i--) {      rts = rts substr(str,i,1)    }    return(rts)} `
Output:
```1:    1 * 9    = 9
2:   91 * 99   = 9009
3:  913 * 993  = 906609
4: 9901 * 9999 = 99000099
```

## C#

Translation of: Paper & Pencil
`using System;class Program {   static bool isPal(int n) {    int rev = 0, lr = -1, rem;    while (n > rev) {      n = Math.DivRem(n, 10, out rem);      if (lr < 0 && rem == 0) return false;      lr = rev; rev = 10 * rev + rem;      if (n == rev || n == lr) return true;    } return false; }   static void Main(string[] args) {    var sw = System.Diagnostics.Stopwatch.StartNew();    int x = 900009, y = (int)Math.Sqrt(x), y10, max = 999, max9 = max - 9, z, p, bp = x, ld, c;    var a = new int[]{ 0,9,0,3,0,0,0,7,0,1 }; string bs = "";    y /= 11;    if ((y & 1) == 0) y--;    if (y % 5 == 0) y -= 2;    y *= 11;    while (y <= max) {      c = 0;      y10 = y * 10;      z = max9 + a[ld = y % 10];      p = y * z;      while (p >= bp) {        if (isPal(p)) {          if (p > bp) bp = p;          bs = string.Format("{0} x {1} = {2}", y, z - c, bp);        }        p -= y10; c += 10;      }      y += ld == 3 ? 44 : 22;    }    sw.Stop();    Console.Write("{0} {1} μs", bs, sw.Elapsed.TotalMilliseconds * 1000.0);  }}`
Output @ Tio.run:
`913 x 993 = 906609 245.2 μs`

### Stretch

`using System; class Program {     static bool isPal(long n) {        long rev = 0, lr = -1, rem;        while (n > rev) {            n = Math.DivRem(n, 10, out rem);            if (lr < 0 && rem == 0) return false;            lr = rev; rev = 10 * rev + rem;            if (n == rev || n == lr) return true;        } return false; }     static void doOne(int n) {        int ld, c; string bs = "";        string sx = "9" + new string('0', (n - 1) << 1) + "9", sm = new string('9', n);        long x = long.Parse(sx), y = (long)Math.Sqrt(x), oy, max = long.Parse(sm), max9 = max - 9, z, yy, p, bp = x;        var a = new long[] { 0, 9, 0, 3, 0, 0, 0, 7, 0, 1 };        y /= 11;        if ((y & 1) == 0) y--;        if (y % 5 == 0) y -= 2;        y *= 11; oy = y;        while (y <= max) y += 22; y -= 22;        while (y >= oy) {            c = 0;            yy = y * 10;            z = max9 + a[ld = (int)(y % 10)];            //Console.WriteLine("y,z: {0},{1}", y, z);            p = y * z;            while (p >= bp) {                if (isPal(p)) {                    if (p > bp) bp = p;                    bs = string.Format(" {0,2} {1,10} x {2,-10} = {3}{4}", n, y, z - c, new string(' ', 10 - n), bp); }                p -= yy; c += 10; }            y -= ld == 7 ? 44 : 22; }        Console.WriteLine(bs); }     static void Main(string[] args) {        Console.WriteLine("digs    factor   factor            palindrome");        var sw = System.Diagnostics.Stopwatch.StartNew();        for (int i = 2, h = 1; i <= 10; h = ++i >> 1) {            if ((i & 1) == 0) {                string b = new string('9', i),                       a = new string('9', h) + new string('0', (h) - 1) + "1",                       c = new string('9', h) + new string('0', i) + new string('9', h);                Console.WriteLine(" {0,2} {1,10} x {2,-10} = {3}{4}", i, a, b, new string(' ', 10 - i), c); }            else doOne(i);        }        sw.Stop();        Console.Write("{0} sec", sw.Elapsed.TotalSeconds);    }}`
Output @ Tio.run:

Showing results for 2 through 10 digit factors.

```digs    factor   factor            palindrome
2         91 x 99         =         9009
3        913 x 993        =        906609
4       9901 x 9999       =       99000099
5      99979 x 99681      =      9966006699
6     999001 x 999999     =     999000000999
7    9997647 x 9998017    =    99956644665999
8   99990001 x 99999999   =   9999000000009999
9  999920317 x 999980347  =  999900665566009999
10 9999900001 x 9999999999 = 99999000000000099999
2.1622142 sec```
Wow! how did that go so fast? The results for the even-number-of-digit factors were manufactured by string manipulation instead of calculation (since the pattern was obvious). This algorithm can easily be adapted to BigIntegers for higher n-digit factors, but the execution time is unspectacular.

## F#

` // Largest palindrome product. Nigel Galloway: November 3rd., 2021let 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 nprintfn "%d" ([for n in 100..999 do for g in n..999->n*g]|>List.filter fN|>List.max) `
Output:
```906609
```

## FreeBASIC

### Version 1

`function make_pal( n as ulongint ) as ulongint    'turn a number into a palindrom with twice as many digits    dim as string ns, ret    ns = str(n) : ret = ns    for i as uinteger = len(ns) to 1 step -1       ret += mid(ns, i, 1)    next i    return val(ret)end function function has_dig( n as ulongint, d as uinteger ) as boolean    'does the number n have d decimal digits?    if 10^(d-1)<=n and n<10^d then return true else return falseend function dim as integer np for d as uinteger = 2 to 7    for n as ulongint = 10^d - 1 to 10^(d-1) step -1 'count down from 999...                                                     'since the first good number we encounter                                                     'must be the highest        np = make_pal( n )                           'produce a 2d-digit palindrome from it        for f as ulongint = 10^d - 1 to 10^(d-1) step -1   'look for highest d-digit factor            if np mod f = 0 then                if has_dig( np/f, d ) then           'if np/f also has d digits we are done :)                    print f;" *";np/f;" =";np                    goto nextd                end if            end if        next f    next n    nextd:                                           'yes, I used a goto. sue me.next d`
Output:
```99 * 91 = 9009
993 * 913 = 906609
9999 * 9901 = 99000099
99979 * 99681 = 9966006699
999999 * 999001 = 999000000999
9998017 * 9997647 = 99956644665999```

### Version 2

This version is based on Version 1 with only a few changes and some extra code based on the fact that one divisor can be divided by 11, this speeds it even more up and a option for using goto, exit or continue. highest n is 9, (highest possible for unsigned 64bit integers).

`' version 07-10-2021' compile with: fbc -s console ' Now you can choice, no speed changes for all 3' 1: use goto' 2: use exit' 3: use continue#Define Option_ 1  ' set option_ to 1, 2 or 3. for all other value's uses 1 Function make_pal( n As UInteger ) As ULongInt    'turn a number into a palindrom with twice as many digits    Dim As String ns = Str(n), ret = ns    For i As UInteger = Len(ns) To 1 Step -1        ret += Mid(ns, i, 1)    Next i    Return ValULng(ret)End Function Dim As ULongInt np, tmpDim As Double t1 =TimerFor d As UInteger = 2 To 9    For n As UInteger = 10^d -2 To 10^(d -1) Step -1        np = make_pal( n )        tmp = Sqr(np)        tmp = tmp - (10^d - 1 - tmp)        tmp = tmp - tmp Mod 11        If (tmp And 1) = 0 Then tmp = tmp + 11        For f As UInteger = tmp To 10^d -1  Step 22            If np Mod f = 0 Then                If np \ f > (10^d) Then Continue For                Print f; " * "; np \ f; " = "; np                #If (option_ = 2)                    Exit For, For                #ElseIf (option_ = 3)                    Continue For, For, For                #Else                    GoTo nextd                #EndIf            End If        Next f    Next n    #If (option_ <> 2 Or option_ <> 3)        nextd:    #EndIfNext d Print Timer-t1' empty keyboard bufferWhile InKey <> "" : WendPrint : Print "hit any key to end program"SleepEnd`
Output:
```99 * 91 = 9009
993 * 913 = 906609
9999 * 9901 = 99000099
99979 * 99681 = 9966006699
999999 * 999001 = 999000000999
9998017 * 9997647 = 99956644665999
99999999 * 99990001 = 9999000000009999
999980347 * 999920317 = 999900665566009999```

## 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.

`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                }            }        }    }}`
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

`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) * \$(facs) = \$prodnum")            break        end        halfnum = digits(evalpoly(Int128(10), halfnum) - 1)    endend 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 `
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
```

### Faster version

Translation of: Python
`""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """ const T = [Set([(0, 0)])] function double(it)    arr = empty(it)    for p in it        push!(arr, p, reverse(p))    end    return arrend """ Construct a pair of n-digit numbers such that their product ends with 99...9 pattern """function tails(n)    if length(T) <= n        l = Set()        for i in 0:9, j in i:9            I = i * 10^(n-1)            J = j * 10^(n-1)            it = collect(tails(n - 1))            I != J && (it = double(it))            for (t1, t2) in it                if ((I + t1) * (J + t2) + 1) % 10^n == 0                    push!(l, (I + t1, J + t2))                end            end        end        push!(T, l)    end    return T[n + 1]end """ find the largest palindrome that is a product of n-digit numbers """function largestpalindrome(n)    m, tail = 0, n ÷ 2    head = n - tail    up = 10^head    for L in 1 : 9 * 10^(head-1)        # Consider small shell (up-L)^2 < (up-i)*(up-j) <= (up-L)^2, 1<=i<=L<=j        m, sol = 0, (0, 0)        for i in 1:L            lo = max(Int128(i), Int128(up - (up - L + 1)^2 ÷ (up - i)) + 1)            hi = Int128(up - (up - L)^2 ÷ (up - i))            for j in lo:hi                I = (up - i) * 10^tail                J = (up - j) * 10^tail                it = collect(tails(tail))                I != J && (it = double(it))                for (t1, t2) in it                    val = (I + t1) * (J + t2)                    s = string(val)                    if s == reverse(s) && val > m                        sol = (I + t1, J + t2)                        m = val                    end                end            end        end        if m > 0            println(lpad(n, 2), "    ", lpad(m % 1337, 4), " \$sol \$(sol * sol)")            return m % 1337        end    end    return 0end @time for k in 1:16    largestpalindrome(k)end `
Output:
``` 1       9 (9, 1) 9
2     987 (91, 99) 9009
3     123 (993, 913) 906609
4     597 (9901, 9999) 99000099
5     677 (99979, 99681) 9966006699
6    1218 (999001, 999999) 999000000999
7     877 (9998017, 9997647) 99956644665999
8     475 (99990001, 99999999) 9999000000009999
9    1226 (999980347, 999920317) 999900665566009999
10     875 (9999986701, 9999996699) 99999834000043899999
11     108 (99999943851, 99999996349) 9999994020000204999999
12     378 (999999000001, 999999999999) 999999000000000000999999
13    1097 (9999999993349, 9999996340851) 99999963342000024336999999
14     959 (99999990000001, 99999999999999) 9999999000000000000009999999
15     465 (999999998341069, 999999975838971) 999999974180040040081479999999
16      51 (9999999900000001, 9999999999999999) 99999999000000000000000099999999
62.575515 seconds (241.50 M allocations: 16.491 GiB, 25.20% gc time, 0.07% compilation time)
```

## Paper & Pencil

`find two 3-digit factors, that when multiplied together, yield the highest 6-digit palindrome. lowest possible 6 digit palindrome starting with 9 is 900009floor(sqrt(900009)) = 948one factor must be an odd multiple of 11floor(948 / 11) = 86it must not be even or a multiple of 5, so use 8383 * 11 = 913 <- this is the lowest possible first factorthe last digit of the second factor must multiply with the last digit of the first factor to get 9the highest suitable second factor (for 913) is 993913 x 993 = 906609, a palindrome, now check suitable higher first factors913 + 22 = 935, an unsuitable multiple of 5, so skip it and use 913 + 44 = 957957 x 997 = ‭954129‬, not a palindrome, so continue (just subtract 9570)957 x 987 = 944559‬‬, not a palindrome, so continue957 x 977 = ‭934989‬, not a palindrome, so continue957 x 967 = ‭925429‬, not a palindrome, so continue957 x 957 = ‭915849‬, not a palindrome, so continue957 x 947 = ‭906279‬, not a palindrome, and less than the best found so far, so stop andcontinue to the next suitible first number, 957 + 22 = 979979 x 991 = 970189‬‬, not a palindrome, so continue (just subtract 9790)979 x 981 = 960399‬, not a palindrome, so continue979 x 971 = 950609‬, not a palindrome, so continue979 x 961 = 940819‬, not a palindrome, so continue979 x 951 = 931029‬, not a palindrome, so continue979 x 941 = 921239‬, not a palindrome, so continue979 x 931 = 911449‬, not a palindrome, so continue979 x 921 = 901659‬, not a palindrome, and less than the best found so far, so stopdone because 979 + 22 = 1001`

## Perl

Library: ntheory
`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 * \$f;        say "Largest palindromic product of two @{[\$l]}-digit integers: \$f × \$f = \$p" and last LOOP;    }}`
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```

## Phix

Library: Phix/online

Translated from python by Lucy_Hedgehog as found on page 5 of the project euler discussion page (dated 25 Sep 2011), and further optimised as per the C# comments (on this very rosettacode page). You can run this online here.

```-- demo\rosetta\Largest_palindrome_product.exw
with javascript_semantics
requires("1.0.1") -- (mpz_fdiv_qr(), mpz_si_sub() added to mpfr.js, mpz_mod_ui(), mpz_fdiv_q_ui(), mpz_fdiv_r(), mpz_fdiv_ui() fixed)
include mpfr.e

function ispalindrome(mpz x)
string s = mpz_get_str(x)
return s == reverse(s)
end function

function inverse(mpz x, integer m)
-- Compute the modular inverse of x modulo power(10,m).
-- Return -1 if the inverse does not exist.
-- This function uses Hensel lifting.
integer a = {-1, 1, -1, 7, -1, -1, -1, 3, -1, 9}[mpz_fdiv_ui(x,10)+1]
if a!=-1 then
mpz ax = mpz_init()
while true do
mpz_mul_si(ax,x,a)
{} = mpz_mod_ui(ax,ax,m)
if mpz_cmp_si(ax,1)==0 then exit end if
mpz_si_sub(ax,2,ax)
mpz_mul_si(ax,ax,a)
a = mpz_fdiv_q_ui(ax,ax,m)
end while
end if
return a
end function

function pal2(integer n)
assert(n>1)

mpz {best,factor,y,r} = mpz_inits(4)
if even(n) then
// (as per the C# comments)
mpz_ui_pow_ui(factor,10,n/2)
mpz_sub_si(factor,factor,1)
mpz_ui_pow_ui(best,10,n/2*3)
mpz_mul(best,best,factor)
assert(ispalindrome(best))
mpz_ui_pow_ui(factor,10,n)
mpz_sub_si(factor,factor,1)
assert(ispalindrome(factor))
else
// Get a lower bound:
integer k = floor(n/2)
mpz {maxf,maxf11,minf,x,t,maxy,p} = mpz_inits(7)
while true do
mpz_ui_pow_ui(maxf,10,n)
mpz_sub_si(maxf,maxf,1)
mpz_sub_si(maxf11,maxf,11)
{} = mpz_fdiv_q_ui(maxf11,maxf11,22)
mpz_mul_si(maxf11,maxf11,22)
mpz_ui_pow_ui(minf,10,n-k)
mpz_sub(minf,maxf,minf)
mpz_mul(best,minf,minf)
mpz_set_si(factor,0)
// This palindrome starts with k 9's.
// Hence the largest palindrom must also start with k 9's and
// therefore end with k 9's.
// Thus, if p = x * y is the solution then
// x * y + 1 is divisible by m.
integer m = power(10,k) -- (should not exceed 1e8)
mpz_set(x,maxf11)
while mpz_cmp_si(x,1)>=0 do
mpz_mul(t,x,maxf)
if mpz_cmp(t,best)=-1 then exit end if
integer ry = inverse(x, m)
if ry!=-1 then
mpz_mul(p,maxy,x)
while mpz_cmp(p,best)>0 do
if ispalindrome(p) then
mpz_set(best,p)
mpz_set(factor,x)
end if
mpz_mul_si(t,x,m)
mpz_sub(p,p,t)
end while
end if
mpz_sub_si(x,x,22)
end while
if mpz_cmp_si(factor,0)!=0 then exit end if
k -= 1
end while
end if
mpz_fdiv_qr(y,r,best,factor)
assert(mpz_cmp_si(r,0)=0)
return {best, factor, y}
end function

constant fmt = "Largest palindromic product of two %d-digit integers: %s = %s x %s (%s)\n"
for n=2 to 12 do
atom t1 = time()
mpz {p,x,y} = pal2(n)
string sp = mpz_get_str(p),
sx = mpz_get_str(x),
sy = mpz_get_str(y),
e = elapsed(time()-t1)
printf(1,fmt,{n,sp,sx,sy,e})
end for
```
Output:
```Largest palindromic product of two 2-digit integers: 9009 = 99 x 91 (0s)
Largest palindromic product of two 3-digit integers: 906609 = 913 x 993 (0s)
Largest palindromic product of two 4-digit integers: 99000099 = 9999 x 9901 (0s)
Largest palindromic product of two 5-digit integers: 9966006699 = 99979 x 99681 (0s)
Largest palindromic product of two 6-digit integers: 999000000999 = 999999 x 999001 (0s)
Largest palindromic product of two 7-digit integers: 99956644665999 = 9997647 x 9998017 (0.0s)
Largest palindromic product of two 8-digit integers: 9999000000009999 = 99999999 x 99990001 (0s)
Largest palindromic product of two 9-digit integers: 999900665566009999 = 999920317 x 999980347 (0.8s)
Largest palindromic product of two 10-digit integers: 99999000000000099999 = 9999999999 x 9999900001 (0s)
Largest palindromic product of two 11-digit integers: 9999994020000204999999 = 99999996349 x 99999943851 (0.1s)
Largest palindromic product of two 12-digit integers: 999999000000000000999999 = 999999999999 x 999999000001 (0s)
```

After that it starts to struggle a bit:

```Largest palindromic product of two 13-digit integers: 99999963342000024336999999 = 9999996340851 x 9999999993349 (40.4s)
Largest palindromic product of two 14-digit integers: 9999999000000000000009999999 = 99999999999999 x 99999990000001 (0s)
Largest palindromic product of two 15-digit integers: 999999974180040040081479999999 = 999999998341069 x 999999975838971 (1 minute and 12s)
Largest palindromic product of two 16-digit integers: 99999999000000000000000099999999 = 9999999999999999 x 9999999900000001 (0s)
```

## Python

Original author credit to user peijunz at Leetcode.

`""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """ T=[set([(0, 0)])] def double(it):    for a, b in it:        yield a, b        yield b, a def tails(n):    '''Construct pair of n-digit numbers that their product ends with 99...9 pattern'''    if len(T)<=n:        l = set()        for i in range(10):            for j in range(i, 10):                I = i*10**(n-1)                J = j*10**(n-1)                it = tails(n-1)                if I!=J: it = double(it)                for t1, t2 in it:                    if ((I+t1)*(J+t2)+1)%10**n == 0:                        l.add((I+t1, J+t2))        T.append(l)    return T[n] def largestPalindrome(n):    """ find largest palindrome that is a product of two n-digit numbers """    m, tail = 0, n // 2    head = n - tail    up = 10**head    for L in range(1, 9*10**(head-1)+1):        # Consider small shell (up-L)^2 < (up-i)*(up-j) <= (up-L)^2, 1<=i<=L<=j        m = 0        sol = None        for i in range(1, L + 1):            lo = max(i, int(up - (up - L + 1)**2 / (up - i)) + 1)            hi = int(up - (up - L)**2 / (up - i))            for j in range(lo, hi + 1):                I = (up-i) * 10**tail                J = (up-j) * 10**tail                it = tails(tail)                if I!=J: it = double(it)                    for t1, t2 in it:                        val = (I + t1)*(J + t2)                        s = str(val)                        if s == s[::-1] and val>m:                            sol = (I + t1, J + t2)                            m = val         if m:            print("{:2d}\t{:4d}".format(n, m % 1337), sol, sol * sol)            return m % 1337    return 0 if __name__ == "__main__":    for k in range(1, 14):        largestPalindrome(k) `
Output:
``` 1	   9 (9, 1) 9
2	 987 (91, 99) 9009
3	 123 (993, 913) 906609
4	 597 (9901, 9999) 99000099
5	 677 (99979, 99681) 9966006699
6	1218 (999001, 999999) 999000000999
7	 877 (9998017, 9997647) 99956644665999
8	 475 (99990001, 99999999) 9999000000009999
9	1226 (999980347, 999920317) 999900665566009999
10	 875 (9999986701, 9999996699) 99999834000043899999
11	 108 (99999943851, 99999996349) 9999994020000204999999
12	 378 (999999000001, 999999999999) 999999000000000000999999
13	1097 (9999999993349, 9999996340851) 99999963342000024336999999
```

## Raku

`use Inline::Perl5;my \$p5 = Inline::Perl5.new();\$p5.use: 'ntheory';my &divisors = \$p5.run('sub { ntheory::divisors \$_ }'); .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}`
```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

`? "working..." prod = 1bestProd = 0// maximum 3 digit numbermax = 999// both factors must be >100 for a 6 digit product limitStart = 101// one factor must be divisible by 11limitEnd = 11 * floor(max / 11)second = limitStartiters = 0 // loop from hi to low to find the best result in the fewest stepsfor 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    nextnext 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`
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.

`var reverse = Fn.new { |n|    var r = 0     while (n > 0) {        r = n%10 + r*10        n = (n/10).floor    }    return r} var pow = 10for (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    }}`
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

`func Rev(A);    \Reverse digitsint 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);]`
Output:
```906609
```