Talk:Untouchable numbers: Difference between revisions
→Number of untouchable numbers up to 1 million: Further remarks.
(→Number of untouchable numbers up to 1 million: Further remarks.) |
|||
Line 40:
: Doh, what a stupid and embarrassing mistake! I've reverted the Go entry back to a limit of 1e5 until I can find time to sort out the 1e6 figure. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 17:03, 13 February 2021 (UTC)
:Well, after spending some time re-examining this, I think I may have to retire hurt as I'm not going to be able to get anywhere near Julia's time for a million untouchables.
:Reverting to 100,000 untouchables where Julia was using a sieve limit of 32 million, it's time was only about 1.5 minutes on my machine. Rewriting the Go program to use a similar approach and, even after adding some optimizations, the time was about 11.5 minutes which is nearly 8 times slower! So, for a million untouchables and a sieve limit of 512 million, if Julia is taking just under an hour, the Go program will likely take north of 8 hours which is far more than I have the patience for.
:I think the difference must be due to Julia having access to a very fast factorization routine in its Primes package which is then being used to calculate the sum of a number's proper divisors and is taking most of the time here. My own fairly simple approach must be relatively pedestrian.
:FWIW here's the latest Go program if anyone has any ideas about quickening it up:
<lang go>package main
import "fmt"
func sumDivisors(n int) int {
sum := 1
k := 2
if n%2 == 0 {
k = 1
}
for i := 1 + k; i*i <= n; i += k {
if n%i == 0 {
sum += i
j := n / i
if j != i {
sum += j
}
}
}
return sum
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
func main() {
const maxTarget = 100_000 // 1_000_000
const sieveLimit = 32_000_000 // 512_000_000
untouchables := make([]bool, maxTarget+1) // all false by default
primes := make([]bool, maxTarget+1) // ditto
for i := 1; i <= maxTarget; i++ {
untouchables[i] = true
}
for i := 2; i <= maxTarget; i++ {
n := sumDivisors(i)
if n <= maxTarget {
untouchables[n] = false
if n == 1 {
primes[i] = true
}
}
}
for i := maxTarget + 1; i <= sieveLimit; i++ {
n := sumDivisors(i)
if n <= maxTarget {
untouchables[n] = false
}
}
for i := 6; i <= maxTarget; i += 2 {
if untouchables[i] && (primes[i-1] || primes[i-3]) {
untouchables[i] = false
}
}
fmt.Println("List of untouchable numbers <= 2,000:")
count := 0
for i := 0; i <= 2000; i++ {
if untouchables[i] {
fmt.Printf("%6s", commatize(i))
count++
if count > 0 && count%10 == 0 {
fmt.Println()
}
}
}
fmt.Printf("\n\n%7s untouchable numbers were found <= 2,000\n", commatize(count))
p := 10
count = 0
for i, u := range untouchables {
if u {
count++
}
if i == p {
cc := commatize(count)
cp := commatize(p)
fmt.Printf("%7s untouchable numbers were found <= %9s\n", cc, cp)
p = p * 10
}
}
}</lang>
--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 21:03, 13 February 2021 (UTC)
==Nice recursive solution==
| |||