Talk:Untouchable numbers: Difference between revisions
Content added Content deleted
(→Number of untouchable numbers up to 1 million: Further remarks.) |
|||
Line 40: | 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) |
: 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== |
==Nice recursive solution== |