Untouchable numbers: Difference between revisions
→{{header|Wren}}: Added a second, much faster version.
(Added C) |
(→{{header|Wren}}: Added a second, much faster version.) |
||
Line 1,822:
{{libheader|Wren-fmt}}
Not an easy task as, even allowing for the prime tests, it's difficult to know how far you need to sieve to get the right answers. The parameters here were found by trial and error.
===Version 1===
Run time about 70 seconds on my Core i7 machine.
<syntaxhighlight lang="ecmascript">import "/math" for Int, Nums
import "/seq" for Lst
Line 1,894 ⟶ 1,896:
1,212 untouchable numbers were found <= 10,000
13,863 untouchable numbers were found <= 100,000
</pre>
===Version 2===
{{trans|C}}
This version uses a much more efficient algorithm for calculating the sums of divisors in bulk.
Run time for untouchable numbers up to 100,000 (m = 14) is now only 1.4 seconds and 1,000,000 (m = 63) is reached in 132 seconds.
=={{header|Wren}}==
<syntaxhighlight lang="ecmascript">import "/math" for Int, Nums
import "/seq" for Lst
import "/fmt" for Fmt
var limit = 1e6
var m = 63
var c = Int.primeSieve(limit, false)
var n = m * limit + 1
var sumDivs = List.filled(n, 0)
for (i in 1...n) {
var j = i
while (j < n) {
sumDivs[j] = sumDivs[j] + i
j = j + i
}
}
var s = List.filled(n, false)
for (i in 1...n) {
var sum = sumDivs[i] - i // proper divs sum
if (sum <= n) s[sum] = true
}
var untouchable = [2, 5]
n = 6
while (n <= limit) {
if (!s[n] && c[n-1] && c[n-3]) untouchable.add(n)
n = n + 2
}
System.print("List of untouchable numbers <= 2,000:")
for (chunk in Lst.chunks(untouchable.where { |n| n <= 2000 }.toList, 10)) {
Fmt.print("$,6d", chunk)
}
System.print()
Fmt.print("$,7d untouchable numbers were found <= 2,000", untouchable.count { |n| n <= 2000 })
var p = 10
var count = 0
for (n in untouchable) {
count = count + 1
if (n > p) {
Fmt.print("$,7d untouchable numbers were found <= $,9d", count-1, p)
p = p * 10
if (p == limit) break
}
}
Fmt.print("$,7d untouchable numbers were found <= $,d", untouchable.count, limit)</syntaxhighlight>
{{out}}
As Version 1, plus:
<pre>
150,232 untouchable numbers were found <= 1,000,000
</pre>
| |||