Talk:Untouchable numbers: Difference between revisions

← Older edit

Talk:Untouchable numbers (view source)

Revision as of 05:53, 6 September 2021

4,520 bytes added , 2 years ago

m

→‎reduction in the number of (counting) ranges: Thanks

Anonymous user

rosettacode>Horsth

Revision as of 16:36, 14 February 2021 (view source) PureFox (talk \| contribs) (→‎Number of untouchable numbers up to 1 million: Further results.) ← Older edit		Latest revision as of 05:53, 6 September 2021 (view source) rosettacode>Horsth m (→‎reduction in the number of (counting) ranges: Thanks)
(12 intermediate revisions by 4 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 //10010001000;//1010001000;//510001000;//10001000; factor //384( to small ) ;//152;//104;//64; // search area = factorLimit</pre> :How about using Goldbach conjectue ( tested true > 1e18 ).All numbers are a sum of max three primes<BR> proper div sum(pq) = 1+p+q / p<q and both prime and p+q < Limit proper div sum(pqr) = 1+p+q+r+pq+pr+qr/ p<q<r and all prime and proper div sum(pqr) <=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 53 ⟶ 75: :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) == Number of untouchable numbers up to <s>2</s> <s>3</s> 6 million == 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) 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) ::those who say this algorithm is too slow, somewhat against 4 s on TIO.RUN<br> ::it is but how to estimated a good Multiple of LIMIT to find all. --[[User:Horsth\|Horsth]] ([[User talk:Horsth\|talk]]) 14:06, 2 September 2021 (UTC) Running F# to 6 million seems to agree with uupaper3.pdf <pre> F:\>.\UntouchableP.exe 100000 -> 13863 200000 -> 28572 30000 -> 43515 400000 -> 58459 500000 -> 73565 600000 -> 88828 700000 -> 104062 800000 -> 119302 900000 -> 134758 1000000 -> 150232 2000000 -> 305290 3000000 -> 462110 4000000 -> 619638 5000000 -> 777672 6000000 -> 936244 </pre>--[[User:Nigel Galloway\|Nigel Galloway]] ([[User talk:Nigel Galloway\|talk]]) 15:31, 5 September 2021 (UTC) ==Nice recursive solution== Line 95 ⟶ 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 ge-Π. Rule 1 is applied when the prime doesn't change: Π<-Πi; e<-e+l; and l<-li.<br> Rule 2 is applied when the prime changes: i<-new prime; Π<-Πi; g<-eg; e<-1+i; and l<-ii. --[[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)