Greatest prime dividing the n-th cubefree number
A cubefree number is a positive integer whose prime factorization does not contain any third (or higher) power factors. If follows that all primes are trivially cubefree and the first cubefree number is 1 because it has no prime factors.
- Definitions
Let a[n] be the greatest prime dividing the n-th cubefree number for n >= 2. By convention, let a[1] = 1 even though the first cubefree number, 1, has no prime factors.
- Examples
a[2] is clearly 2 because it is the second cubefree number and also prime. The fourth cubefree number is 4 and it's highest prime factor is 2, hence a[4] = 2.
- Task
Compute and show on this page the first 100 terms of a[n]. Also compute and show the 1,000th, 10,000th and 100,000th members of the sequence.
- Stretch
Compute and show the 1 millionth and 10 millionth terms of the sequence.
This may take a while for interpreted languages.
- Reference
Wren
This takes just under 4 minutes to run on my system (Core i7).
Although it looks odd that the 1 millionth and 10 millionth terms are the same (and I have no independent source to check against), it would appear that the 1 millionth cubefree number is 1,202,057 which is prime and the 10 millionth such number is coincidentally 10 times this.
import "./math" for Int
import "./fmt" for Fmt
var res = [1]
var count = 1
var i = 2
var lim1 = 100
var lim2 = 1000
var max = 1e7
while (count < max) {
var cubeFree = false
var factors = Int.primeFactors(i)
if (factors.count < 3) {
cubeFree = true
} else {
cubeFree = true
for (i in 2...factors.count) {
if (factors[i-2] == factors[i-1] && factors[i-1] == factors[i]) {
cubeFree = false
break
}
}
}
if (cubeFree) {
if (count < lim1) res.add(factors[-1])
count = count + 1
if (count == lim1) {
System.print("First %(lim1) terms of a[n]:")
Fmt.tprint("$3d", res, 10)
} else if (count == lim2) {
Fmt.print("\nThe $,r term of a[n] is $,d.", count, factors[-1])
lim2 = lim2 * 10
}
}
i = i + 1
}
- Output:
First 100 terms of a[n]: 1 2 3 2 5 3 7 3 5 11 3 13 7 5 17 3 19 5 7 11 23 5 13 7 29 5 31 11 17 7 3 37 19 13 41 7 43 11 5 23 47 7 5 17 13 53 11 19 29 59 5 61 31 7 13 11 67 17 23 7 71 73 37 5 19 11 13 79 41 83 7 17 43 29 89 5 13 23 31 47 19 97 7 11 5 101 17 103 7 53 107 109 11 37 113 19 23 29 13 59 The 1,000th term of a[n] is 109. The 10,000th term of a[n] is 101. The 100,000th term of a[n] is 1,693. The 1,000,000th term of a[n] is 1,202,057. The 10,000,000th term of a[n] is 1,202,057.