Talk:Untouchable numbers: Difference between revisions
no edit summary
(→Number of untouchable numbers up to 1 million: More comments.) |
No edit summary |
||
Line 32:
:: Without something reliable to check against, I think that 1 million is probably as far as we can practically go. We could, of course, incrementally increase the sieve factor for higher limits until we ''appear'' to get a stable count but, judging by what it said in the Julia entry, there may still be the possibility of some outlier spoiling the party! --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 14:23, 11 February 2021 (UTC)
==Nice recursive solution==
In a manner similar to [[Talk:Numbers_with_prime_digits_whose_sum_is_13#Nice_recursive_solution]] I present a scheme which requires no guessed maximums and ends when the candidate list N is empty. First I identify the primes less than the maximum value I am interested in (10 for this example) then I combine them as follows.
Important: The minimum value of Σ at level n is greater than the minimum value of Σ at level n-1. The value of Σ increase with depth along any path.
;Level=root
Path=1
Π=na
Σ=na
;Level=1 N=1..10 Untouchables=None
<pre>
Path=1;2 Path=1;3 Path=1;5 Path=1;7
Π=2 Π=3 Π=5 Π=7
Σ=1 Σ=1 Σ=1 Σ=1
</pre>
;Level=2 N=2..10 Untouchables=None
<pre>
Path=1;2;2 Path=1;2;3 Path=1;2;5 Path=1;2;7 Path=1;3;3 Path=1;3;5 Path=1;3;7 Path=1;5;5 Path=1;5;7 Path=1;7;7
Π=4 Π=6 Π=10 Π=14 Π=9 Π=15 Π=21 Π=25 Π=35 Π=49
Σ=3 Σ=6 Σ=8 Σ=10 Σ=4 Σ=9 Σ=11 Σ=6 Σ=13 Σ=8
</pre>
I have not gained much yet. This elimates P+1s which I could have done by reading the task description. I have proven that 2 is untouchable. I remove 2 and the Σs found from N.
;Level=3 N=5;7 Untouchables=2 (because 2 is less than minimum Σ at level 2)
<pre>
Path=1;2;2;2 Path=1;2;2;3 Path=1;3;3;3
Π=8 Π=12 Π=27
Σ=7 Σ=14 Σ=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).
;Level=4 N=None Untouchables=5 (because 5 is less than minimum Σ at level 3)
N=None so I am done. 2 and 5 have been identified as untouchable. To find larger untouchables, probably time to turn to your poor long suffering computer. Where [[Talk:Numbers_with_prime_digits_whose_sum_is_13#Nice_recursive_solution]] may be considered 'Trees 101' This is more difficult to implement. It is described above as a breadth first search, but for for large values it may be better to use depth first. The main saving is in how well any implementation prunes the tree.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:55, 11 February 2021 (UTC)
| |||