Achilles numbers: Difference between revisions
→{{header|Wren}}: Added a second much faster version.
Thundergnat (talk | contribs) m (→{{header|Raku}}: add some higher oom) |
(→{{header|Wren}}: Added a second much faster version.) |
||
Line 357:
{{libheader|Wren-seq}}
{{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!
<lang ecmascript>import "./math" for Int
Line 486 ⟶ 487:
7 digits: 2242
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>
| |||