Largest palindrome product: Difference between revisions
(Added Algol 68) |
(→{{header|ALGOL 68}}: Extended to 7 digit numbers, format output as per Wren sample and added translation of the Wren sample) |
||
Line 8: | Line 8: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{Trans|Wren}} |
|||
<lang algol68>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 n := v; |
|||
WHILE n > 0 DO |
|||
⚫ | |||
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</lang> |
|||
{{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> |
|||
{{Trans|Ring}} |
{{Trans|Ring}} |
||
Also showing the maximum for 2 and 4 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. |
||
<lang algol68>BEGIN # find the highest palindromic multiple of |
<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 24: | Line 82: | ||
# maximum 2 digit number # |
# maximum 2 digit number # |
||
INT max := 99; |
LONG INT max := 99; |
||
# both factors must be >= 10for a 4 digit product # |
# both factors must be >= 10for a 4 digit product # |
||
INT limit start := 10; |
LONG INT limit start := 10; |
||
FOR w FROM 2 TO |
FOR w FROM 2 TO 7 DO |
||
INT best prod := 0; |
LONG INT best prod := 0; |
||
# one factor must be divisible by 11 # |
# one factor must be divisible by 11 # |
||
INT limit end = 11 * ( max OVER 11 ); |
LONG INT limit end = 11 * ( max OVER 11 ); |
||
INT second := limit start; |
LONG INT second := limit start; |
||
INT first := 1; |
LONG INT first := 1; |
||
# loop from hi to low to find the best result in the fewest steps # |
# 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 # |
# with n falling, the lower limit of m can rise with # |
||
# the best-found-so-far second number. Doing this # |
# the best-found-so-far second number. Doing this # |
||
# lowers the iteration count by a lot. # |
# lowers the iteration count by a lot. # |
||
LONG INT m := max + 2; |
|||
WHILE |
WHILE m -:= 2; |
||
IF m < second |
|||
THEN FALSE |
|||
ELIF LONG INT prod = n * m; |
|||
best prod > prod |
|||
THEN FALSE |
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 |
FI |
||
DO SKIP OD |
DO SKIP OD |
||
OD; |
OD; |
||
print( ( " |
print( ( "Largest palindromic product of two ", whole( w, 0 ) |
||
, "-digit numbers |
, "-digit numbers: ", whole( first, 0 ), " * ", whole( second, 0 ) |
||
, " = ", whole( |
, " = ", whole( best prod, 0 ) |
||
, newline |
, newline |
||
) |
) |
||
Line 66: | Line 129: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
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 |
|||
</pre> |
</pre> |
||
Revision as of 20:19, 4 November 2021
- 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.
ALGOL 68
<lang algol68>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</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999
Also showing the maximum for 2 and 4 .. 7 digit numbers. Tests for a better product before testing for palindromicity. <lang algol68>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</lang>
- 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
F#
<lang fsharp> // Largest palindrome product. Nigel Galloway: November 3rd., 2021 let fN g=let rec fN g=[yield g%10; if g>=10 then yield! fN(g/10)] in let n=fN g in n=List.rev n printfn "%d" ([for n in 100..999 do for g in n..999->n*g]|>List.filter fN|>List.max) </lang>
- Output:
906609
Go
18 digit integers are within the range of Go's uint64 type though finding the result for 9-digit number products takes a while - around 15 seconds on my machine. <lang go>package main
import "fmt"
func reverse(n uint64) uint64 {
r := uint64(0) for n > 0 { r = n%10 + r*10 n /= 10 } return r
}
func main() {
pow := uint64(10)
nextN:
for n := 2; n < 10; n++ { low := pow * 9 pow *= 10 high := pow - 1 fmt.Printf("Largest palindromic product of two %d-digit integers: ", n) for i := high; i >= low; i-- { j := reverse(i) p := i*pow + j // k can't be even nor end in 5 to produce a product ending in 9 for k := high; k > low; k -= 2 { if k % 10 == 5 { continue } l := p / k if l > high { break } if p%k == 0 { fmt.Printf("%d x %d = %d\n", k, l, p) continue nextN } } } }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999 Largest palindromic product of two 8-digit integers: 99999999 x 99990001 = 9999000000009999 Largest palindromic product of two 9-digit integers: 999980347 x 999920317 = 999900665566009999
Julia
<lang julia>using Primes
function twoprodpal(factorlength)
maxpal = Int128(10)^(2 * factorlength) - 1 dig = digits(maxpal) halfnum = dig[1:length(dig)÷2] while any(halfnum .!= 0) prodnum = evalpoly(Int128(10), [reverse(halfnum); halfnum]) facs = twofac(factorlength, prodnum) if !isempty(facs) println("For factor length $factorlength, $(facs[1]) * $(facs[2]) = $prodnum") break end halfnum = digits(evalpoly(Int128(10), halfnum) - 1) end
end
function twofac(faclength, prodnum)
f = [one(prodnum)] for (p, e) in factor(prodnum) f = reduce(vcat, [f * p^j for j in 1:e], init=f) end possiblefacs = filter(x -> length(string(x)) == faclength, f) for i in possiblefacs j = prodnum ÷ i j ∈ possiblefacs && return sort([i, j]) end return typeof(prodnum)[]
end
@Threads.threads for i in 2:12
twoprodpal(i)
end
</lang>
- Output:
For factor length 2, 91 * 99 = 9009 For factor length 3, 913 * 993 = 906609 For factor length 4, 9901 * 9999 = 99000099 For factor length 5, 99681 * 99979 = 9966006699 For factor length 6, 999001 * 999999 = 999000000999 For factor length 7, 9997647 * 9998017 = 99956644665999 For factor length 8, 99990001 * 99999999 = 9999000000009999 For factor length 9, 999920317 * 999980347 = 999900665566009999 For factor length 10, 9999986701 * 9999996699 = 99999834000043899999 For factor length 11, 99999943851 * 99999996349 = 9999994020000204999999 For factor length 12, 999999000001 * 999999999999 = 999999000000000000999999
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'divisors';
for my $l (2..7) {
LOOP: for my $p (reverse map { $_ . reverse $_ } 10**($l-1) .. 10**$l - 1) { my @f = reverse grep { length == $l } divisors $p; next unless @f >= 2 and $p == $f[0] * $f[1]; say "Largest palindromic product of two @{[$l]}-digit integers: $f[1] × $f[0] = $p" and last LOOP; }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 Largest palindromic product of two 3-digit integers: 913 × 993 = 906609 Largest palindromic product of two 4-digit integers: 9901 × 9999 = 99000099 Largest palindromic product of two 5-digit integers: 99681 × 99979 = 9966006699 Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999 Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999
Raku
<lang perl6>use Inline::Perl5; my $p5 = Inline::Perl5.new(); $p5.use: 'ntheory'; my &divisors = $p5.run('sub { ntheory::divisors $_[0] }');
.say for (2..12).map: {.&lpp};
multi lpp ($oom where {!($_ +& 1)}) { # even number of multiplicand digits
my $f = +(9 x $oom); my $o = $oom / 2; my $pal = +(9 x $o ~ 0 x $oom ~ 9 x $o); sprintf "Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $f, $f, $pal
}
multi lpp ($oom where {$_ +& 1}) { # odd number of multiplicand digits
my $p; (+(1 ~ (0 x ($oom - 1))) .. +(9 ~ (9 x ($oom - 1)))).reverse.map({ +($_ ~ .flip) }).map: -> $pal { for my @factors = divisors("$pal")».Int.grep({ .chars == $oom }).sort( -* ) { next unless $pal div $_ ∈ @factors; $p = sprintf("Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom, $pal div $_, $_, $pal); last; } last if $p; } $p
}</lang>
Largest palindromic product of two 2-digit integers: 91 × 99 = 9009 Largest palindromic product of two 3-digit integers: 913 × 993 = 906609 Largest palindromic product of two 4-digit integers: 9901 × 9999 = 99000099 Largest palindromic product of two 5-digit integers: 99681 × 99979 = 9966006699 Largest palindromic product of two 6-digit integers: 999001 × 999999 = 999000000999 Largest palindromic product of two 7-digit integers: 9997647 × 9998017 = 99956644665999 Largest palindromic product of two 8-digit integers: 99990001 × 99999999 = 9999000000009999 Largest palindromic product of two 9-digit integers: 999920317 × 999980347 = 999900665566009999 Largest palindromic product of two 10-digit integers: 9999900001 × 9999999999 = 99999000000000099999 Largest palindromic product of two 11-digit integers: 99999943851 × 99999996349 = 9999994020000204999999 Largest palindromic product of two 12-digit integers: 999999000001 × 999999999999 = 999999000000000000999999
Ring
<lang ring>? "working..."
prod = 1 bestProd = 0 // maximum 3 digit number max = 999 // both factors must be >100 for a 6 digit product limitStart = 101 // one factor must be divisible by 11 limitEnd = 11 * floor(max / 11) second = limitStart iters = 0
// loop from hi to low to find the best result in the fewest steps for n = limitEnd to limitStart step -11
// with n falling, the lower limit of m can rise with // the best-found-so-far second number. Doing this // lowers the iteration count by a lot. for m = max to second step -2 prod = n * m if isPal(prod) iters++ // exit when the product stops increasing if bestProd > prod exit ok // maintain the best-found-so-far result first = n second = m bestProd = prod ok next
next
put "The largest palindrome is: " ? "" + bestProd + " = " + first + " * " + second ? "Found in " + iters + " iterations" put "done..."
func isPal n
x = string(n) l = len(x) + 1 i = 0 while i < l if x[i++] != x[l--] return false ok end return true</lang>
- Output:
working... The largest palindrome is: 906609 = 913 * 993 Found in 6 iterations done...
Wren
The approach here is to manufacture palindromic numbers of length 2n in decreasing order and then see if they're products of two n-digit numbers. <lang ecmascript>var reverse = Fn.new { |n|
var r = 0 while (n > 0) { r = n%10 + r*10 n = (n/10).floor } return r
}
var pow = 10 for (n in 2..7) {
var low = pow * 9 pow = pow * 10 var high = pow - 1 System.write("Largest palindromic product of two %(n)-digit integers: ") var nextN = false for (i in high..low) { var j = reverse.call(i) var p = i * pow + j // k can't be even nor end in 5 to produce a product ending in 9 var k = high while (k > low) { if (k % 10 != 5) { var l = p / k if (l > high) break if (p % k == 0) { System.print("%(k) x %(l) = %(p)") nextN = true break } } k = k - 2 } if (nextN) break }
}</lang>
- Output:
Largest palindromic product of two 2-digit integers: 99 x 91 = 9009 Largest palindromic product of two 3-digit integers: 993 x 913 = 906609 Largest palindromic product of two 4-digit integers: 9999 x 9901 = 99000099 Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 Largest palindromic product of two 6-digit integers: 999999 x 999001 = 999000000999 Largest palindromic product of two 7-digit integers: 9998017 x 9997647 = 99956644665999
XPL0
<lang XPL0>func Rev(A); \Reverse digits int A, B; [B:= 0; repeat A:= A/10;
B:= B*10 + rem(0);
until A = 0; return B; ];
int Max, M, N, Prod; [Max:= 0; for M:= 100 to 999 do
for N:= M to 999 do [Prod:= M*N; if Prod/1000 = Rev(rem(0)) then if Prod > Max then Max:= Prod; ];
IntOut(0, Max); ]</lang>
- Output:
906609