Talk:Untouchable numbers: Difference between revisions
→Nice recursive solution
Line 100:
: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)
| |||