Largest palindrome product: Difference between revisions
Added Easylang
(Added Easylang) |
|||
| (10 intermediate revisions by 8 users not shown) | |||
Line 17:
{{trans|Wren}}
<
V r = Int64(0)
L n > 0
Line 45:
k -= 2
I nextN
L.break</
{{out}}
Line 59:
=={{header|ALGOL 68}}==
{{Trans|Wren}}
<
# returns n with the digits reversed #
PROC reverse = ( LONG INT v )LONG INT:
Line 104:
OD
OD
END</
{{out}}
Line 118:
{{Trans|Ring}}
Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity.
<
PROC is pal = ( LONG INT n )BOOL:
BEGIN
Line 176:
limit start *:= 10
OD
END</
{{out}}
<pre>
Line 186:
Largest palindromic product of two 7-digit numbers: 9997647 * 9998017 = 99956644665999
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">
palindrome?: function [n]->
(to :string n) = reverse to :string n
getAllMuls: function [n][
result: []
limFrom: 10^ n-1
limTo: dec 10^n
loop limFrom..limTo 'a [
loop limFrom..limTo 'b [
m: a*b
if palindrome? m ->
'result ++ @[@[a, b, a*b]]
]
]
return result
]
largestPal: maximum getAllMuls 3 'x -> last x
print ["Largest palindromic product of two 3-digit integers:" largestPal\0 "x" largestPal\1 "=" largestPal\2]</syntaxhighlight>
{{out}}
<pre>Largest palindromic product of two 3-digit integers: 913 x 993 = 906609</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f LARGEST_PALINDROME_PRODUCT.AWK
BEGIN {
Line 220 ⟶ 247:
return(rts)
}
</syntaxhighlight>
{{out}}
<pre>
Line 230 ⟶ 257:
=={{header|Ksh}}==
<
#!/bin/ksh
Line 279 ⟶ 306:
print "Largest palindrome product of two 3-digit factors = ${MAXPPROD}"
</syntaxhighlight>
{{out}}<pre>
Largest palindrome product of two 3-digit factors = 906609</pre>
Line 286 ⟶ 313:
===Main Task===
{{trans|Paper & Pencil}}
<
class Program {
Line 323 ⟶ 350:
Console.Write("{0} {1} μs", bs, sw.Elapsed.TotalMilliseconds * 1000.0);
}
}</
{{out|Output @ Tio.run}}
<pre>913 x 993 = 906609 245.2 μs</pre>
===Stretch===
<
class Program {
Line 379 ⟶ 406:
Console.Write("{0} sec", sw.Elapsed.TotalSeconds);
}
}</
{{out|Output @ Tio.run}}
Showing results for 2 through 10 digit factors.
Line 393 ⟶ 420:
10 9999900001 x 9999999999 = 99999000000000099999
2.1622142 sec</pre>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.
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|uses Windows,SysUtils,StdCtrls,Math}}
<syntaxhighlight lang="Delphi">
type TProgress = procedure(Percent: integer);
function ReverseNum(N: int64): int64;
{Reverse the digit order of a number}
begin
Result:=0;
while N>0 do
begin
Result:=(Result*10)+(N mod 10);
N:=N div 10;
end;
end;
function IsPalindrome(N: int64): boolean;
{If the number is the same in }
{reverse order it is a palindrome}
var N1: int64;
begin
N1:=ReverseNum(N);
Result:=N = N1;
end;
procedure ShowPalindrome(Memo: TMemo; D,N1,N2: int64);
begin
Memo.Lines.Add(Format('%5D %5D %5D %10D',[D,N1,N2,N1 * N2]));
end;
procedure FindPalindromes(Digits: integer; var C1,C2: int64; Prog: TProgress);
{Find the largest palindrome derrived from two}
{ terms with the specified number of digits}
var I,J: cardinal;
var Prd,MinNum,MaxNum,Best: int64;
begin
Best:=0;
{Find the minimum and maximum values}
{ with the specified number of digits}
MinNum:=Trunc(Power(10,Digits-1));
MaxNum:=Trunc(Power(10,Digits))-1;
for I:=MinNum to MaxNum do
begin
{We can eliminate even factors and number ending in 5}
if ((I and 1)=0) or ((I mod 10)=5) then continue;
for J:=I+1 to MaxNum do
begin
{We can eliminate even factors and number ending in 5}
if ((J and 1)=0) or ((J mod 10)=5) then continue;
Prd:=I * J;
if not IsPalindrome(Prd) then continue;
if Assigned(Prog) then Prog(MulDiv(100,I-MinNum,MaxNum-MinNum));
{Save the largest palindromes}
if Prd>Best then
begin
Best:=Prd;
C1:=I; C2:=J;
end;
end;
end;
end;
procedure FindPalindromeMax(Memo: TMemo; Prog: TProgress);
var N1,N2: Int64;
var I: integer;
begin
Memo.Lines.Add('Digits F1 F2 Palindrome');
Memo.Lines.Add('-------------------------------');
for I:=2 to 4 do
begin
FindPalindromes(I,N1,N2,Prog);
ShowPalindrome(Memo,I,N1,N2);
end;
end;
</syntaxhighlight>
{{out}}
<pre>
Digits F1 F2 Palindrome
-------------------------------
2 91 99 9009
3 913 993 906609
4 9901 9999 99000099
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc rev n .
while n > 0
r = r * 10 + n mod 10
n = n div 10
.
return r
.
for i = 100 to 999
for j = i to 999
p = i * j
if p > max and p = rev p
max = p
.
.
.
</syntaxhighlight>
{{out}}
<pre>
906609
</pre>
=={{header|F_Sharp|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)
</syntaxhighlight>
{{out}}
<pre>
Line 407 ⟶ 551:
=={{header|FreeBASIC}}==
===Version 1===
<
'turn a number into a palindrom with twice as many digits
dim as string ns, ret
Line 439 ⟶ 583:
next n
nextd: 'yes, I used a goto. sue me.
next d</
{{out}}
<pre>99 * 91 = 9009
Line 449 ⟶ 593:
===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).
<
' compile with: fbc -s console
Line 500 ⟶ 644:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>99 * 91 = 9009
Line 514 ⟶ 658:
{{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.
<
import "fmt"
Line 554 ⟶ 698:
}
}
}</
{{out}}
Line 567 ⟶ 711:
Largest palindromic product of two 9-digit integers: 999980347 x 999920317 = 999900665566009999
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
<
function twoprodpal(factorlength)
Line 602 ⟶ 798:
twoprodpal(i)
end
</
<pre>
For factor length 2, 91 * 99 = 9009
Line 619 ⟶ 815:
=== Faster version ===
{{trans|Python}}
<
const T = [Set([(0, 0)])]
Line 688 ⟶ 884:
largestpalindrome(k)
end
</
<pre>
1 9 (9, 1) 9
Line 708 ⟶ 904:
62.575515 seconds (241.50 M allocations: 16.491 GiB, 25.20% gc time, 0.07% compilation time)
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
Block[{digits = IntegerDigits@n}, digits == Reverse[digits]]
Line 732 ⟶ 929:
Grid[Join[{{"factors", "largest palindrome"}}, {#, Times @@ #} & /@
Table[search[n], {n, 2, 7}]], Alignment -> {Left, Baseline}]</
{{out}}<pre>
Line 745 ⟶ 942:
=={{header|Paper & Pencil}}==
<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
Line 772 ⟶ 969:
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</
=={{header|Perl}}==
{{libheader|ntheory}}
<
use warnings;
use feature 'say';
Line 788 ⟶ 985:
say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP;
}
}</
{{out}}
<pre>Largest palindromic product of two 2-digit integers: 91 × 99 = 9009
Line 802 ⟶ 999:
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].
<!--<
<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>
Line 907 ⟶ 1,104:
<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>
<!--</
{{out}}
<pre>
Line 932 ⟶ 1,129:
=={{header|Python}}==
Original author credit to user peijunz at Leetcode.
<
T=[set([(0, 0)])]
Line 989 ⟶ 1,186:
for k in range(1, 14):
largestPalindrome(k)
</
<pre>
1 9 (9, 1) 9
Line 1,004 ⟶ 1,201:
12 378 (999999000001, 999999999999) 999999000000000000999999
13 1097 (9999999993349, 9999996340851) 99999963342000024336999999
</pre>
=={{header|Quackery}}==
The largest product of two 3 digit numbers is 999*999 = 998001.
The smallest product of two 3 digit numbers is 100*100 = 10000.
Therefore we need only consider 6 and 5 digit palindromic numbers.
Considering 6 digit palindromic numbers:
The largest is 999999.
The smallest is 100001.
These can be costructed from the numbers 100 to 999.
Therefore there are 899 6 digit palindromic numbers.
The same applies to 5 digit palindromic numbers:
The largest is 99999.
The smallest is 10001.
These can be costructed from the numbers 100 to 999.
Therefore there are 899 5 digit palindromic numbers.
'''Method:'''
* Construct the 6 digit palindromic numbers in reverse numerical order.
* Test each one to see if it is divisible by a 3 digit number with a 3 digit result, starting with 999.
* If it is, the solution has been found.
* If no solution found, consider 5 digit palindromes.
A six digit solution was found, and as it was found virtually instantaneously I did not feel that any optimisations were necessary.
I went on to find the largest five digit soultion, even though the task did not call for it, as it was a trivial exercise.
<syntaxhighlight lang="Quackery"> [ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is ->digits ( n --> [ )
[ behead swap
witheach
[ swap 10 * + ] ] is ->number ( [ --> n )
[ ->digits
dup reverse join
->number ] is evenpal ( n --> n )
[ ->digits
dup reverse
behead drop join
->number ] is oddpal ( n --> n )
[ 2dup mod 0 != iff
[ 2drop false ]
done
/ 100 1000 within ] is solution ( n n --> b )
false
899 times
[ i 100 + evenpal
899 times
[ dup i 100 +
solution if
[ dip not
conclude ] ]
over iff
[ nip conclude ]
else drop ]
dup iff
[ say "Six digit solution found: " echo ]
else
[ drop say "No six digit solution found." ]
cr
false
899 times
[ i 100 + oddpal
899 times
[ dup i 100 +
solution if
[ dip not
conclude ] ]
over iff
[ nip conclude ]
else drop ]
dup iff
[ say "Five digit solution found: " echo ]
else
[ drop say "No five digit solution found." ]
</syntaxhighlight>
{{out}}
<pre>Six digit solution found: 906609
Five digit solution found: 99899
</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
my $p5 = Inline::Perl5.new();
$p5.use: 'ntheory';
Line 1,033 ⟶ 1,323:
}
$p
}</
<pre>Largest palindromic product of two 2-digit integers: 91 × 99 = 9009
Largest palindromic product of two 3-digit integers: 913 × 993 = 906609
Line 1,047 ⟶ 1,337:
=={{header|Ring}}==
<
prod = 1
Line 1,095 ⟶ 1,385:
ok
end
return true</
{{out}}
<pre>working...
Line 1,101 ⟶ 1,391:
Found in 6 iterations
done...</pre>
=={{header|RPL}}==
≪ "" OVER SIZE 1 '''FOR''' j
OVER j DUP SUB +
-1 '''STEP''' NIP
≫ '<span style="color:blue">REVSTR</span>' STO
≪ 1 CF
'''DO'''
1 -
DUP →STR DUP <span style="color:blue">REVSTR</span> + STR→
DUP DIVIS SORT
1 OVER SIZE '''FOR''' j
DUP j GET
DUP XPON 2
'''CASE'''
DUP2 < '''THEN''' 3 DROPN '''END'''
> '''THEN''' DROP DUP SIZE 'j' STO '''END'''
PICK3 SWAP /
'''IF''' XPON 2 == '''THEN''' 1 SF '''END'''
'''END'''
'''NEXT''' DROP2
'''UNTIL''' 1 FS? '''END'''
→STR DUP <span style="color:blue">REVSTR</span> + STR→
≫ '<span style="color:blue">P004</span>' STO
1000 <span style="color:blue">P004</span>
{{out}}
<pre>
1: 906609
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">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}"
}</syntaxhighlight>
{{out}}
<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 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
</pre>
=={{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.
<
var r = 0
while (n > 0) {
Line 1,139 ⟶ 1,490:
if (nextN) break
}
}</
{{out}}
Line 1,152 ⟶ 1,503:
=={{header|XPL0}}==
<
int A, B;
[B:= 0;
Line 1,170 ⟶ 1,521:
];
IntOut(0, Max);
]</
{{out}}
| |||