Largest palindrome product: Difference between revisions
m (→{{header|Sidef}}: slightly faster) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 17: | Line 17: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="11l">F reverse(=n) |
||
V r = Int64(0) |
V r = Int64(0) |
||
L n > 0 |
L n > 0 |
||
Line 45: | Line 45: | ||
k -= 2 |
k -= 2 |
||
I nextN |
I nextN |
||
L.break</ |
L.break</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 59: | Line 59: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{Trans|Wren}} |
{{Trans|Wren}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the highest palindromic multiple of various sizes of numbers # |
||
# returns n with the digits reversed # |
# returns n with the digits reversed # |
||
PROC reverse = ( LONG INT v )LONG INT: |
PROC reverse = ( LONG INT v )LONG INT: |
||
Line 104: | Line 104: | ||
OD |
OD |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 118: | Line 118: | ||
{{Trans|Ring}} |
{{Trans|Ring}} |
||
Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity. |
Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity. |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the highest palindromic multiple of various sizes of numbers # |
||
PROC is pal = ( LONG INT n )BOOL: |
PROC is pal = ( LONG INT n )BOOL: |
||
BEGIN |
BEGIN |
||
Line 176: | Line 176: | ||
limit start *:= 10 |
limit start *:= 10 |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 188: | Line 188: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f LARGEST_PALINDROME_PRODUCT.AWK |
# syntax: GAWK -f LARGEST_PALINDROME_PRODUCT.AWK |
||
BEGIN { |
BEGIN { |
||
Line 220: | Line 220: | ||
return(rts) |
return(rts) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 230: | Line 230: | ||
=={{header|Ksh}}== |
=={{header|Ksh}}== |
||
< |
<syntaxhighlight lang="ksh"> |
||
#!/bin/ksh |
#!/bin/ksh |
||
Line 279: | Line 279: | ||
print "Largest palindrome product of two 3-digit factors = ${MAXPPROD}" |
print "Largest palindrome product of two 3-digit factors = ${MAXPPROD}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
Largest palindrome product of two 3-digit factors = 906609</pre> |
Largest palindrome product of two 3-digit factors = 906609</pre> |
||
Line 286: | Line 286: | ||
===Main Task=== |
===Main Task=== |
||
{{trans|Paper & Pencil}} |
{{trans|Paper & Pencil}} |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
class Program { |
class Program { |
||
Line 323: | Line 323: | ||
Console.Write("{0} {1} μs", bs, sw.Elapsed.TotalMilliseconds * 1000.0); |
Console.Write("{0} {1} μs", bs, sw.Elapsed.TotalMilliseconds * 1000.0); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out|Output @ Tio.run}} |
{{out|Output @ Tio.run}} |
||
<pre>913 x 993 = 906609 245.2 μs</pre> |
<pre>913 x 993 = 906609 245.2 μs</pre> |
||
===Stretch=== |
===Stretch=== |
||
< |
<syntaxhighlight lang="csharp">using System; |
||
class Program { |
class Program { |
||
Line 379: | Line 379: | ||
Console.Write("{0} sec", sw.Elapsed.TotalSeconds); |
Console.Write("{0} sec", sw.Elapsed.TotalSeconds); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out|Output @ Tio.run}} |
{{out|Output @ Tio.run}} |
||
Showing results for 2 through 10 digit factors. |
Showing results for 2 through 10 digit factors. |
||
Line 395: | Line 395: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Largest palindrome product. Nigel Galloway: November 3rd., 2021 |
// 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 |
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) |
printfn "%d" ([for n in 100..999 do for g in n..999->n*g]|>List.filter fN|>List.max) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 407: | Line 407: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Version 1=== |
===Version 1=== |
||
< |
<syntaxhighlight lang="freebasic">function make_pal( n as ulongint ) as ulongint |
||
'turn a number into a palindrom with twice as many digits |
'turn a number into a palindrom with twice as many digits |
||
dim as string ns, ret |
dim as string ns, ret |
||
Line 439: | Line 439: | ||
next n |
next n |
||
nextd: 'yes, I used a goto. sue me. |
nextd: 'yes, I used a goto. sue me. |
||
next d</ |
next d</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>99 * 91 = 9009 |
<pre>99 * 91 = 9009 |
||
Line 449: | Line 449: | ||
===Version 2=== |
===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). |
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). |
||
< |
<syntaxhighlight lang="freebasic">' version 07-10-2021 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 500: | Line 500: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>99 * 91 = 9009 |
<pre>99 * 91 = 9009 |
||
Line 514: | Line 514: | ||
{{trans|Wren}} |
{{trans|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. |
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. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 554: | Line 554: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 572: | Line 572: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
< |
<syntaxhighlight lang="jq">def reverseNumber: |
||
tostring|explode|reverse|implode|tonumber; |
tostring|explode|reverse|implode|tonumber; |
||
Line 608: | Line 608: | ||
.emit ) ; |
.emit ) ; |
||
task</ |
task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 621: | Line 621: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
function twoprodpal(factorlength) |
function twoprodpal(factorlength) |
||
Line 654: | Line 654: | ||
twoprodpal(i) |
twoprodpal(i) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
For factor length 2, 91 * 99 = 9009 |
For factor length 2, 91 * 99 = 9009 |
||
Line 671: | Line 671: | ||
=== Faster version === |
=== Faster version === |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="julia">""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """ |
||
const T = [Set([(0, 0)])] |
const T = [Set([(0, 0)])] |
||
Line 740: | Line 740: | ||
largestpalindrome(k) |
largestpalindrome(k) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
1 9 (9, 1) 9 |
1 9 (9, 1) 9 |
||
Line 762: | Line 762: | ||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">palindromeQ[n_] := (* faster than built in test PalindromeQ *) |
||
Block[{digits = IntegerDigits@n}, digits == Reverse[digits]] |
Block[{digits = IntegerDigits@n}, digits == Reverse[digits]] |
||
Line 785: | Line 785: | ||
Grid[Join[{{"factors", "largest palindrome"}}, {#, Times @@ #} & /@ |
Grid[Join[{{"factors", "largest palindrome"}}, {#, Times @@ #} & /@ |
||
Table[search[n], {n, 2, 7}]], Alignment -> {Left, Baseline}]</ |
Table[search[n], {n, 2, 7}]], Alignment -> {Left, Baseline}]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 798: | Line 798: | ||
=={{header|Paper & Pencil}}== |
=={{header|Paper & Pencil}}== |
||
<lang>find two 3-digit factors, that when multiplied together, yield the highest 6-digit palindrome. |
<syntaxhighlight lang="text">find two 3-digit factors, that when multiplied together, yield the highest 6-digit palindrome. |
||
lowest possible 6 digit palindrome starting with 9 is 900009 |
lowest possible 6 digit palindrome starting with 9 is 900009 |
||
Line 825: | Line 825: | ||
979 x 931 = 911449, not a palindrome, so continue |
979 x 931 = 911449, not a palindrome, so continue |
||
979 x 921 = 901659, not a palindrome, and less than the best found so far, so stop |
979 x 921 = 901659, not a palindrome, and less than the best found so far, so stop |
||
done because 979 + 22 = 1001</ |
done because 979 + 22 = 1001</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 841: | Line 841: | ||
say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP; |
say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 |
<pre>Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 |
||
Line 855: | Line 855: | ||
and further optimised as per the C# comments (on this very rosettacode page). |
and further optimised as per the C# comments (on this very rosettacode page). |
||
You can run this online [http://phix.x10.mx/p2js/Largest_palindrome_product.htm here]. |
You can run this online [http://phix.x10.mx/p2js/Largest_palindrome_product.htm here]. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Largest_palindrome_product.exw</span> |
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Largest_palindrome_product.exw</span> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 960: | Line 960: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 985: | Line 985: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Original author credit to user peijunz at Leetcode. |
Original author credit to user peijunz at Leetcode. |
||
< |
<syntaxhighlight lang="python">""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """ |
||
T=[set([(0, 0)])] |
T=[set([(0, 0)])] |
||
Line 1,042: | Line 1,042: | ||
for k in range(1, 14): |
for k in range(1, 14): |
||
largestPalindrome(k) |
largestPalindrome(k) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
1 9 (9, 1) 9 |
1 9 (9, 1) 9 |
||
Line 1,061: | Line 1,061: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>use Inline::Perl5; |
||
my $p5 = Inline::Perl5.new(); |
my $p5 = Inline::Perl5.new(); |
||
$p5.use: 'ntheory'; |
$p5.use: 'ntheory'; |
||
Line 1,086: | Line 1,086: | ||
} |
} |
||
$p |
$p |
||
}</ |
}</syntaxhighlight> |
||
<pre>Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 |
<pre>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 3-digit integers: 913 × 993 = 906609 |
||
Line 1,100: | Line 1,100: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring">? "working..." |
||
prod = 1 |
prod = 1 |
||
Line 1,148: | Line 1,148: | ||
ok |
ok |
||
end |
end |
||
return true</ |
return true</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>working... |
<pre>working... |
||
Line 1,156: | Line 1,156: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func largest_palindrome_product (n) { |
||
for k in ((10**n - 1) `downto` 10**(n-1)) { |
for k in ((10**n - 1) `downto` 10**(n-1)) { |
||
Line 1,172: | Line 1,172: | ||
var (a,b) = largest_palindrome_product(n) |
var (a,b) = largest_palindrome_product(n) |
||
say "Largest palindromic product of two #{n}-digit integers: #{a} * #{b} = #{a*b}" |
say "Largest palindromic product of two #{n}-digit integers: #{a} * #{b} = #{a*b}" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,187: | Line 1,187: | ||
=={{header|Wren}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="ecmascript">var reverse = Fn.new { |n| |
||
var r = 0 |
var r = 0 |
||
while (n > 0) { |
while (n > 0) { |
||
Line 1,222: | Line 1,222: | ||
if (nextN) break |
if (nextN) break |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,235: | Line 1,235: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func Rev(A); \Reverse digits |
||
int A, B; |
int A, B; |
||
[B:= 0; |
[B:= 0; |
||
Line 1,253: | Line 1,253: | ||
]; |
]; |
||
IntOut(0, Max); |
IntOut(0, Max); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 17:31, 27 August 2022
- 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.
- 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,
11l
F reverse(=n)
V r = Int64(0)
L n > 0
r = n % 10 + r * 10
n I/= 10
R r
V po = Int64(10)
L(n) 2..7
V low = po * 9
po *= 10
V high = po - 1
V nextN = 0B
L(i) (high .. low).step(-1)
V j = reverse(i)
V p = i * po + j
V k = high
L k > low
I k % 10 != 5
V l = p I/ k
I l > high
L.break
I p % k == 0
print(‘Largest palindromic product of two ’n‘-digit integers: ’k‘ x ’l‘ = ’p)
nextN = 1B
L.break
k -= 2
I nextN
L.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
ALGOL 68
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
OD
END
- 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
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
OD
END
- 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.AWK
BEGIN {
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
Ksh
#!/bin/ksh
# Largest palindrome product of two 3-digit numbers
# # Variables:
#
typeset -si MINFACT=913 # From 'Paper & Pencil' solution
typeset -si MAXFACT=999
# # Functions:
#
# # Function _ispalindrome(n) - return 1 for palindromic number
#
function _ispalindrome {
typeset _n ; integer _n="$1"
(( _n != $(_flipit ${_n}) )) && return 0
return 1
}
# # Function _flipit(string) - return flipped string
#
function _flipit {
typeset _buf ; _buf="$1"
typeset _tmp ; unset _tmp
typeset _i ; typeset -si _i
for (( _i=$(( ${#_buf}-1 )); _i>=0; _i-- )); do
_tmp="${_tmp}${_buf:${_i}:1}"
done
echo "${_tmp}"
}
######
# main #
######
integer prod MAXPPROD=0
for (( i=MINFACT; i<=MAXFACT; i++)); do
for (( j=MINFACT; j<=MAXFACT; j++)); do
(( prod = i * j ))
_ispalindrome ${prod}
(( $? )) && (( prod > MAXPPROD )) && MAXPPROD=${prod}
done
done
print "Largest palindrome product of two 3-digit factors = ${MAXPPROD}"
- Output:
Largest palindrome product of two 3-digit factors = 906609
C#
Main Task
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., 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)
- 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 false
end 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, tmp
Dim As Double t1 =Timer
For 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:
#EndIf
Next d
Print Timer-t1
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
- 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
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
jq
Adapted from Wren
Works with gojq, the Go implementation of jq
def reverseNumber:
tostring|explode|reverse|implode|tonumber;
def task:
{ pow: 10}
| foreach range(2;8) as $n (.;
(.pow * 9) as $low
| .pow *= 10
| (.pow - 1) as $high
| .emit = null
| .nextN = false
| label $out
| foreach range($high; $low - 1; -1) as $i (.;
($i|reverseNumber) as $j
| ($i * .pow + $j) as $p
# k can't be even nor end in 5 to produce a product ending in 9
| .k = $high
| .done = false
| until(.k <= $low or .done;
if (.k % 10 != 5)
then ($p / .k) as $l
| if $l > $high
then .done = true
elif $p % .k == 0
then .emit = "Largest palindromic product of two \($n)-digit integers: \(.k) x \($l) = \($p)"
| .nextN = true
| .done = true
else .
end
else .
end
| .k += -2 )
| if .nextN then ., break $out else . end;
select(.emit) );
.emit ) ;
task
- 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
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
- 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
""" 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 arr
end
""" 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[1] * sol[2])")
return m % 1337
end
end
return 0
end
@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)
Mathematica / Wolfram Language
palindromeQ[n_] := (* faster than built in test PalindromeQ *)
Block[{digits = IntegerDigits@n}, digits == Reverse[digits]]
nextPair[n_] := (* outputs next pair of candidate divisors *)
Block[{next =
NestWhile[# - 11 &, n, ! MemberQ[{1, 3, 7, 9}, Mod[#, 10]] &],
len = Last@RealDigits@n},
{next, 10^len - Switch[Mod[next, 10], 1, 1, 3, 7, 7, 3, 9, 9]}]
search[n_] :=
Block[{resetLimit = 10^(n - Floor[n/2]) (10^Floor[n/2] - 1), cands},
cands =
Partition[
Flatten[
Reap[
NestWhile[(If[palindromeQ[Times @@ #], Sow[#]];
If[Last@# < resetLimit,
nextPair[First@# - 11], # - {0, 10}]) &,
nextPair@If[EvenQ@n, 10^n - 1, 10^n - 21],
First@# > resetLimit &]]], 2];
Flatten@cands[[Ordering[Times @@@ cands, -1]]]]
Grid[Join[{{"factors", "largest palindrome"}}, {#, Times @@ #} & /@
Table[search[n], {n, 2, 7}]], Alignment -> {Left, Baseline}]
- Output:
factors largest palindrome {99,91} 9009 {913,993} 906609 {9999,9901} 99000099 {99979,99681} 9966006699 {999999,999001} 999000000999 {9997647,9998017} 99956644665999
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 900009
floor(sqrt(900009)) = 948
one factor must be an odd multiple of 11
floor(948 / 11) = 86
it must not be even or a multiple of 5, so use 83
83 * 11 = 913 <- this is the lowest possible first factor
the last digit of the second factor must multiply with the last digit of the first factor to get 9
the highest suitable second factor (for 913) is 993
913 x 993 = 906609, a palindrome, now check suitable higher first factors
913 + 22 = 935, an unsuitable multiple of 5, so skip it and use 913 + 44 = 957
957 x 997 = 954129, not a palindrome, so continue (just subtract 9570)
957 x 987 = 944559, not a palindrome, so continue
957 x 977 = 934989, not a palindrome, so continue
957 x 967 = 925429, not a palindrome, so continue
957 x 957 = 915849, not a palindrome, so continue
957 x 947 = 906279, not a palindrome, and less than the best found so far, so stop and
continue to the next suitible first number, 957 + 22 = 979
979 x 991 = 970189, not a palindrome, so continue (just subtract 9790)
979 x 981 = 960399, not a palindrome, so continue
979 x 971 = 950609, not a palindrome, so continue
979 x 961 = 940819, not a palindrome, so continue
979 x 951 = 931029, not a palindrome, so continue
979 x 941 = 921239, not a palindrome, so continue
979 x 931 = 911449, not a palindrome, so continue
979 x 921 = 901659, not a palindrome, and less than the best found so far, so stop
done because 979 + 22 = 1001
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;
}
}
- 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
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) mpz_add(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_add_si(maxf11,maxf11,11) mpz_ui_pow_ui(minf,10,n-k) mpz_sub(minf,maxf,minf) mpz_add_si(minf,minf,2) 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_add_si(maxy,maxf,1-ry) 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[0] * sol[1])
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 $_[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
}
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 = 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
- Output:
working... The largest palindrome is: 906609 = 913 * 993 Found in 6 iterations done...
Sidef
func largest_palindrome_product (n) {
for k in ((10**n - 1) `downto` 10**(n-1)) {
var t = Num("#{k}#{Str(k).flip}")
t.divisors.each {|d|
if ((d.len == n) && ((t/d).len == n)) {
return (d, t/d)
}
}
}
}
for n in (2..9) {
var (a,b) = largest_palindrome_product(n)
say "Largest palindromic product of two #{n}-digit integers: #{a} * #{b} = #{a*b}"
}
- 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 Largest palindromic product of two 8-digit integers: 99990001 * 99999999 = 9999000000009999 Largest palindromic product of two 9-digit integers: 999920317 * 999980347 = 999900665566009999
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 = 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
}
}
- 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 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);
]
- Output:
906609