Rosetta Code

Talk:Untouchable numbers: Difference between revisions

Page Discussion

Talk:Untouchable numbers (view source)

Revision as of 05:53, 6 September 2021

4,367 bytes added ,  2 years ago
m
→‎reduction in the number of (counting) ranges: Thanks
 
(15 intermediate revisions by 5 users not shown)
Line 17:
 
I've reduced the number of ranges for counting untouchable numbers.     It seems the upper limit for searching for touchable numbers was far higher than I guesstimated.     -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 09:28, 9 February 2021 (UTC)
:I have checked counting ranges, but, as Nigel stated , that's not the way to get an reliable result, when changing the upper limit.
 
<pre>
Limit //100*1000*1000;//10*1000*1000;//5*1000*1000;//1000*1000;
factor //384( to small ) ;//152;//104;//64; // search area = factor*Limit</pre>
:How about using Goldbach conjectue ( tested true > 1e18 ).All numbers are a sum of max three primes<BR>
proper div sum(p*q) = 1+p+q / p<q and both prime and p+q < Limit
proper div sum(p*q*r) = 1+p+q+r+p*q+p*r+q*r/ p<q<r and all prime and proper div sum(p*q*r) <=Limit
: is limit for checks == limit^(1/3) or limit/3
:<b>EDIT found earlier failure at 300,000</b> used special glasses ;-)
<pre>
//url=https://math.dartmouth.edu/~carlp/uupaper3.pdf
100000 13863
200000 28572
300000 43515
but I get, testing fo 100,000,000 with limit 46,400,000,000 that is 154,666 x 300,000:
154,666 is bigger than 0.5 * 300,000
100,000 13,863
200,000 28,572
300,000 43,514 < less by one
</pre>
:Maybe Nigel can test 300,000 if the table in uupaper3.pdf is true? --[[User:Horst.h|Horst.h]] ([[User talk:Horst.h|talk]]) 12:29, 4 September 2021 (UTC)
:: The uupaper includes the final value, that is 300000 is an untouchable number--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:35, 5 September 2021 (UTC)
::::Thank you.I changed output to include limit.After other modifications the numbers fit to uupaper.<BR>
 
== Number of untouchable numbers up to 1 million ==
Line 46 ⟶ 68:
 
: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.
--[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 21:03, 13 February 2021 (UTC)
 
:Rather than giving up altogether, I've gone back to the earlier approach of guessing how far you need to sieve up to in order to arrive at the correct answer. A few trial runs on lower values suggested a sieve factor of over 60 would be needed so I've used 64 which is what Pete has used in his latest Phix version and also optimized the original code a bit. Sure enough this produced the correct figure of 150,232 untouchable numbers <= 1 million in just over 31 minutes on my machine. Not quick by Go's usual standards but acceptable.
:FWIW here's the latest Go program if anyone has any ideas about quickening it up:
<lang go>package main
 
:I'm going to play with it some more before posting on the main page. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 09:11, 14 February 2021 (UTC)
import "fmt"
 
:OK, i tried sieve factors of 62 and 63. The former was one off and the latter spot on so I'm going with that. The time was exactly the same as the factor 64 version because of another change I made to use less memory. I would, of course, have preferred to use a method which didn't involve any guessing such as Nigel's but the timing difference is just too great - the current Go program with a limit of 100,000 and a sieve factor of 14 takes only 6.2 seconds to run and is very easy to understand. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 16:36, 14 February 2021 (UTC)
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
}
 
== Number of untouchable numbers up to <s>2</s> <s>3</s> 6 million ==
func commatize(n int) string {
I've calculated 2 million as 305290. As Adrian Monk puts it "I could be wrong, but I never am."--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:11, 17 February 2021 (UTC)
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
}
 
I'll stick my neck out and say up to 3 million is 462110. As for those who say this algorithm is too slow: 3mins for 1 million 11½ mins for 2 million and 24mins for 3 million, how fast do they want an algorithm which works to be compared to a page full of algorithms which don't? Mark them as incorrect that's what I say!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 16:00, 25 February 2021 (UTC)
func main() {
::those who say this algorithm is too slow, somewhat against 4 s on TIO.RUN<br>
const maxTarget = 100_000 // 1_000_000
::it is but how to estimated a good Multiple of LIMIT to find all.
const sieveLimit = 32_000_000 // 512_000_000
--[[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 14:06, 2 September 2021 (UTC)
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
}
}
 
Running F# to 6 million seems to agree with uupaper3.pdf
fmt.Println("List of untouchable numbers <= 2,000:")
<pre>
count := 0
F:\>.\UntouchableP.exe
for i := 0; i <= 2000; i++ {
100000 -> 13863
if untouchables[i] {
200000 -> 28572
fmt.Printf("%6s", commatize(i))
30000 -> 43515
count++
400000 -> 58459
if count > 0 && count%10 == 0 {
500000 -> 73565
fmt.Println()
600000 -> 88828
}
700000 -> 104062
}
800000 -> 119302
}
900000 -> 134758
 
1000000 -> 150232
fmt.Printf("\n\n%7s untouchable numbers were found <= 2,000\n", commatize(count))
2000000 -> 305290
p := 10
3000000 -> 462110
count = 0
4000000 -> 619638
for i, u := range untouchables {
5000000 -> 777672
if u {
6000000 -> 936244
count++
</pre>--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:31, 5 September 2021 (UTC)
}
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==
Line 172 ⟶ 133:
Path=1;2;2;2 Path=1;2;2;3 Path=1;3;3;3
Π=8 Π=12 Π=27
Σ=7 Σ=1416 Σ=13
</pre>
Now I gain, there is no need to check i.e. Path=1;2;2;5 because this would add at least 5 to Σ[1;2;2] (3+5) which is greater than the max value in N (7).
Line 184 ⟶ 145:
:Obviously it would be very silly to use trial division when we already have all the prime factors.
:However, I am sure there is an easy/clever way to calculate Σ, from those primes [and/or prev Σ?], but I am ashamed to say I just can't see it.
::I've added a subsection, which I hope helps you see a way.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:21, 9 March 2021 (UTC)
:Is that Σ=14 for Π=12 a typo, should it be 16 ie sum({1,2,3,4,6})? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 08:03, 12 February 2021 (UTC)
::I should have turned my poor suffering computer on earlier, it can add up better than I.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:48, 14 February 2021 (UTC)
: I've only just realised there are 78,498 primes < 1 million, and if you're looking for any combination of those that sum to < 1 million, that's a pretty darn big search space... --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 20:57, 13 February 2021 (UTC)
::That would be sum of subsets and hard. Fortunately that is not what I am doing. I need to sum factors of 1..n which sum to less than n. Becoming an arborist rather than a computer programmer the tree can be pruned considerably. I have done to 100000 in 7 mins, without much optimization so far in F#. The timings to 100000 seem fairly linear so 1 million when I have 90mins? These are proven results, not just selecting a parameter to produce an arbitrary list which happens to be the same as somewhere else!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:48, 14 February 2021 (UTC)
 
===Calculating Π and Σ===
 
Considering lemma 13 and the general discussion of Sum Of Divisors on Wolfram[https://mathworld.wolfram.com/DivisorFunction.html] I construct the following example for part of 1 path through the above tree.
<pre>
Path Π i g e l
1 1 1 1 Initial Conditions.
1;2 2 2 1 3 4 Rule 2
1;2;3 6 3 3 4 9 Rule 2
1;2;3;3 18 3 3 13 27 Rule 1
1;2;3;3;5 90 5 39 6 25 Rule 2
.....
.....
</pre>
Where i is the current prime, e is 1+i+i<sup>2</sup>+i<sup>3</sup>....., and l is i<sup>2</sup>, i<sup>3</sup>....., at each level the sum of the proper divisors is g*e-Π.
 
Rule 1 is applied when the prime doesn't change: Π<-Π*i; e<-e+l; and l<-l*i.<br>
Rule 2 is applied when the prime changes: i<-new prime; Π<-Π*i; g<-e*g; e<-1+i; and l<-i*i.
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 13:21, 9 March 2021 (UTC)
 
==Faster Proper Divisor Sum calculation==
 
The Algol 68 solution uses a sieve rather than modulo operations to construct a table of proper divisor sums.
Using an experimental, home-grown transpiler to VB.NET and running under .Net Framework 3.5 on a Windows 7 machine, it calculated the number of untouchables up to 1 million in less than a minute (about 40 seconds) - as with the Go etc. samples a sieve factor of 64 is used.
I don't claim the generated VB.NET is anything special, BTW.
 
--[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk:Tigerofdarkness|talk]]) 18:58, 28 June 2021 (UTC)
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/307877...307893"