Greatest prime dividing the n-th cubefree number: Difference between revisions
Greatest prime dividing the n-th cubefree number (view source)
Revision as of 14:07, 6 March 2024
, 2 months ago→Version 2: Realigned (more or less) with Phix example and corrected previous prime sieve overkill.
m (→{{header|Phix}}: swapped n and nth for clarity) |
(→Version 2: Realigned (more or less) with Phix example and corrected previous prime sieve overkill.) |
||
Line 852:
{{trans|Phix}}
{{libheader|Wren-iterate}}
Astonishing speed-up, now taking only 0.04 seconds to reach 10 million and
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Conv, Fmt
import "./iterate" for Stepped
var start = System.clock▼
var primes = Int.primeSieve(15 * 1e6)▼
var countBits = Fn.new { |n| Conv.bin(n).count { |c| c == "1" } }
Line 865 ⟶ 867:
var xpm = true
var pm = []
for (i in 1..n.cbrt.floor) {
var p3 = primes[i-1].pow(3)
if (p3 > n) break
Line 872 ⟶ 874:
var m = mask
var mi = 0
var bc = countBits.call(mask)
var kpm = p3
while (m != 0) {
Line 879 ⟶ 882:
}
if (kpm > n) {
if (
xpm = false
pm = pm[0...mi-1]
Line 886 ⟶ 889:
} else {
var l = (n/kpm).floor
if (
k = k - l
} else {
Line 929 ⟶ 932:
var a370833 = Fn.new { |n|
if (n == 1) return [1, 1]
var nth = cubeFree.call(n)
return [Int.primeFactors(nth)[-1], nth]
}
▲var start = System.clock
System.print("First 100 terms of a[n]:")
Fmt.tprint("$3d", (1..100).map { |i| a370833.call(i)[0] }, 10)
System.print()
var n = 1000
while (n <= 1e10) {
Fmt.print("The $,r term of a[n] is $,d for cubefree number $,d.", n, res[0], res[1])
n = n * 10
}
System.print("\nTook %(System.clock - start) seconds.")
{{out}}
Line 959 ⟶ 962:
107 109 11 37 113 19 23 29 13 59
The 1,000th term of a[n] is 109 for cubefree number 1,199.
The 10,000th term of a[n] is 101 for cubefree number 12,019.
The 100,000th term of a[n] is 1,693 for cubefree number 120,203.
The 1,000,000th term of a[n] is 1,202,057 for cubefree number 1,202,057.
The 10,000,000th term of a[n] is 1,202,057 for cubefree number 12,020,570.
The 100,000,000th term of a[n] is 20,743 for cubefree number 120,205,685.
The 1,000,000,000th term of a[n] is 215,461 for cubefree number 1,202,056,919.
The 10,000,000,000th term of a[n] is 1,322,977 for cubefree number 12,020,569,022.
Took
</pre>
| |||