Largest palindrome product: Difference between revisions
(→{{header|Wren}}: Much better approach.) |
(→{{header|Go}}: Updated in line with Wren example.) |
||
Line 9: | Line 9: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{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 30 seconds on my machine. |
|||
Note also that it's a lot quicker in Go to reverse a number arithmetically than to reverse its string equivalent but finding the result for 6-digit numbers is still very slow. |
|||
<lang go>package main |
<lang go>package main |
||
Line 26: | Line 26: | ||
pow := uint64(10) |
pow := uint64(10) |
||
nextN: |
nextN: |
||
for n := 2; n < |
for n := 2; n < 10; n++ { |
||
low := pow* |
low := pow * 9 |
||
pow *= 10 |
pow *= 10 |
||
high := pow - 1 |
high := pow - 1 |
||
fmt.Printf("Largest palindromic product of two %d-digit integers: ", n) |
fmt.Printf("Largest palindromic product of two %d-digit integers: ", n) |
||
for |
for i := high; i >= low; i-- { |
||
j := reverse(i) |
|||
⚫ | |||
// all palindromic numbers are divisible by 11 and we assume here will end in 9 |
|||
if p%11 != 0 || p%10 != 9 { |
|||
continue |
continue |
||
} |
} |
||
for |
for k := high; k >= low+1; k-- { |
||
l := p / k |
|||
if |
if l > high { |
||
break |
break |
||
} |
} |
||
if p% |
if p%k == 0 { |
||
fmt.Printf("%d x %d = %d\n", k, l, p) |
|||
continue nextN |
|||
continue nextN |
|||
⚫ | |||
} |
} |
||
} |
} |
||
Line 58: | Line 59: | ||
Largest palindromic product of two 5-digit integers: 99979 x 99681 = 9966006699 |
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 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 |
|||
</pre> |
</pre> |
||
Revision as of 15:51, 3 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.
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 30 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 // all palindromic numbers are divisible by 11 and we assume here will end in 9 if p%11 != 0 || p%10 != 9 { continue } for k := high; k >= low+1; k-- { 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
Raku
<lang perl6>use Prime::Factor;
.say for (1..11).hyper(:1batch).map: {.&lpp};
multi lpp ($oom where {$_ +& 1}) { # even number of multiplicand digits
my $f = +(9 x ($oom + 1)); my $o = (1 + $oom) / 2; my $pal = +(9 x $o ~ 0 x $o * 2 ~ 9 x $o); sprintf "Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom + 1, $pal div $f, $f, $pal
}
multi lpp ($oom where {$_ +^ 1}) { # odd number of multiplicand digits
my $p; (+(1 ~ (0 x $oom)) .. +(9 ~ (9 x $oom))).reverse.map({ +($_ ~ .flip) }).map: -> $pal { for my @factors = $pal.&divisors.grep({.chars == ($oom + 1)}).sort(-*) { next unless $pal div $_ ∈ @factors; $p = sprintf("Largest palindromic product of two %2d-digit integers: %d × %d = %d", $oom + 1, $pal div $_, $_, $pal) and 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> load "stdlib.ring" see "working..." + nl
prodOld = 0 limitStart = 100 limitEnd = 999
for n = limitStart to limitEnd
for m = limitStart to limitEnd prodNew = n*m if prodNew > prodOld and palindrome(string(prodNew)) prodOld = prodNew first = n second = m ok next
next
see "The largest palindrome is:" + nl see "" + first + " * " + second + " = " + prodOld + nl see "done..." + nl </lang>
- Output:
working... The largest palindrome is: 913 * 993 = 906609 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 // all palindromic numbers are divisible by 11 and we assume here will end in 9 if (p % 11 != 0 || p % 10 != 9) continue for (k in high..low+1) { var l = p / k if (l > high) break if (p % k == 0) { System.print("%(k) x %(l) = %(p)") nextN = true break } } 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