Achilles numbers: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Raku}}: add some higher oom) |
(→{{header|Wren}}: Added a second much faster version.) |
||
Line 357: | Line 357: | ||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
===Version 1 (Brute force)=== |
|||
This finds the number of 6 digit Achilles numbers in 2.5 seconds, 7 digits in 51 seconds but 8 digits needs a whopping 21 minutes! |
This finds the number of 6 digit Achilles numbers in 2.5 seconds, 7 digits in 51 seconds but 8 digits needs a whopping 21 minutes! |
||
<lang ecmascript>import "./math" for Int |
<lang ecmascript>import "./math" for Int |
||
Line 486: | Line 487: | ||
7 digits: 2242 |
7 digits: 2242 |
||
8 digits: 7395 |
8 digits: 7395 |
||
</pre> |
|||
===Version 2 (Much faster)=== |
|||
{{libheader|Wren-set}} |
|||
Here we make use of the fact that powerful numbers are always of the form a²b³, where a and b > 0, to generate such numbers up to a given limit. We also use an improved method for checking whether a number is a perfect power. |
|||
Ridiculously fast compared to the previous method: 8 digits now reached in 0.57 seconds, 9 digits in 4.8 seconds and 10 digits in 34 seconds. However, 11 digits takes 300 seconds and I gave up after that. |
|||
<lang ecmascript>import "./set" for Set, Bag |
|||
import "./math" for Int |
|||
import "./seq" for Lst |
|||
import "./fmt" for Fmt |
|||
var totient = Fn.new { |n| |
|||
var tot = n |
|||
var i = 2 |
|||
while (i*i <= n) { |
|||
if (n%i == 0) { |
|||
while(n%i == 0) n = (n/i).floor |
|||
tot = tot - (tot/i).floor |
|||
} |
|||
if (i == 2) i = 1 |
|||
i = i + 2 |
|||
} |
|||
if (n > 1) tot = tot - (tot/n).floor |
|||
return tot |
|||
} |
|||
var isPerfectPower = Fn.new { |n| |
|||
if (n == 1) return true |
|||
var pf = Int.primeFactors(n) |
|||
var bag = Bag.new(pf) |
|||
var es = bag.map { |me| me.value } |
|||
if (es.count == 1) return true |
|||
return Int.gcd(es.toList) != 1 |
|||
} |
|||
var getAchilles = Fn.new { |digits, lower| |
|||
var upper = 10.pow(digits) |
|||
var achilles = Set.new() // avoids duplicates |
|||
var count = 0 |
|||
for (b in 1..upper.cbrt.floor) { |
|||
var b3 = b * b * b |
|||
for (a in 1..upper.sqrt.floor) { |
|||
var p = b3 * a * a |
|||
if (p >= upper) break |
|||
if (p >= lower) { |
|||
if (!isPerfectPower.call(p)) achilles.add(p) |
|||
} |
|||
} |
|||
} |
|||
return achilles |
|||
} |
|||
var achillesSet = getAchilles.call(5, 1) // enough for first 2 parts |
|||
var achilles = achillesSet.toList |
|||
achilles.sort() |
|||
System.print("First 50 Achilles numbers:") |
|||
for (chunk in Lst.chunks(achilles[0..49], 10)) Fmt.print("$4d", chunk) |
|||
System.print("\nFirst 30 strong Achilles numbers:") |
|||
var strongAchilles = [] |
|||
var count = 0 |
|||
var n = 0 |
|||
while (count < 30) { |
|||
var tot = totient.call(achilles[n]) |
|||
if (achillesSet.contains(tot)) { |
|||
strongAchilles.add(achilles[n]) |
|||
count = count + 1 |
|||
} |
|||
n = n + 1 |
|||
} |
|||
for (chunk in Lst.chunks(strongAchilles, 10)) Fmt.print("$5d", chunk) |
|||
var maxDigits = 10 |
|||
System.print("\nNumber of Achilles numbers with:") |
|||
for (d in 2..maxDigits) { |
|||
var ac = getAchilles.call(d, 10.pow(d-1)).count |
|||
Fmt.print("$2d digits: $d", d, ac) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 50 Achilles numbers: |
|||
72 108 200 288 392 432 500 648 675 800 |
|||
864 968 972 1125 1152 1323 1352 1372 1568 1800 |
|||
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 |
|||
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 |
|||
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 |
|||
First 30 strong Achilles numbers: |
|||
500 864 1944 2000 2592 3456 5000 10125 10368 12348 |
|||
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500 |
|||
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000 |
|||
Number of Achilles numbers with: |
|||
2 digits: 1 |
|||
3 digits: 12 |
|||
4 digits: 47 |
|||
5 digits: 192 |
|||
6 digits: 664 |
|||
7 digits: 2242 |
|||
8 digits: 7395 |
|||
9 digits: 24008 |
|||
10 digits: 77330 |
|||
11 digits: 247449 |
|||
</pre> |
</pre> |