Talk:Untouchable numbers: Difference between revisions
→Nice recursive solution
(→Number of untouchable numbers up to 1 million: Removed previous Go code as now have a much quicker version.) |
|||
Line 81:
Path=1;2;2;2 Path=1;2;2;3 Path=1;3;3;3
Π=8 Π=12 Π=27
Σ=7 Σ=
</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 94:
: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.
: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)
| |||