Talk:Untouchable numbers

1464

Unfortunately, the factors of 14641 are {1,11,121,1331} which sum to 1464.
According to https://oeis.org/A005114/b005114.txt
There are 1212 not 1,216 untouchable numbers <= 10,000
There are 13,863 not 13,886 untouchable numbers <= 100,000 --Pete Lomax (talk) 08:50, 9 February 2021 (UTC)

Yes, I see that I need to extend the search for each range of untouchable numbers.   A fix (hopefully) will be forthcoming.   Thanks for finding those errors in the REXX's output.     -- Gerard Schildberger (talk) 09:00, 9 February 2021 (UTC)

That certainly slowed up the search when I extended the search field.     -- Gerard Schildberger (talk) 09:14, 9 February 2021 (UTC)

To match up to 1e5 I increased the limit to 18*n, a tactic I would deem rather unsound. Note added to the Phix entry. --Pete Lomax (talk) 09:17, 9 February 2021 (UTC)

reduction in the number of (counting) ranges

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.     -- 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.

Limit //100*1000*1000;//10*1000*1000;//5*1000*1000;//1000*1000;
factor //384( to small ) ;//152;//104;//64; // search area = factor*Limit

How about using Goldbach conjectue ( tested true > 1e18 ).All numbers are a sum of max three primes

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

EDIT found earlier failure at 300,000 used special glasses ;-)

//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

Maybe Nigel can test 300,000 if the table in uupaper3.pdf is true? --Horst.h (talk) 12:29, 4 September 2021 (UTC)

The uupaper includes the final value, that is 300000 is an untouchable number--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.

Number of untouchable numbers up to 1 million

According to one of the OEIS links there are 150,232 untouchable numbers up to 1e6 so it looks like the REXX result (150,233) is off by one here.

I've corrected the REXX output,   the incorrect count was computed with an overreach of   18,   not   20.     -- Gerard Schildberger (talk) 21:28, 11 February 2021 (UTC)

By running the Go program with a limit of 1e6 and a sieve factor of 20 (up from 14 for 1e5), I was in fact able to verify the figure of 150,232. Factors of 18 and 19 both gave 150,233 so there must be an 'awkward' number within this range which takes some eliminating. --PureFox (talk) 09:36, 11 February 2021 (UTC)

I've managed to isolate the 'awkward' number which is 816,422. The (first) number whose proper divisors sum to this is 19,175,641 its divisors being [1, 29, 151, 841, 4379, 22801, 126991, 661229]. This explains why we need a sieve factor between 19 and 20 to catch it since neither 816,421 or 816,419 is prime. --PureFox (talk) 11:33, 11 February 2021 (UTC)

That's mighty good detective work   ...   and a true dedicated ethic.     -- Gerard Schildberger (talk) 11:45, 11 February 2021 (UTC)

Yup, found that too, and wrote this before I saw your post: The factors of 19175641 aka 29*29*151*151 are {1,29,151,841,4379,22801,126991,661229}, aka {1,29,151,29*29,29*151,151*151,29*29*151,29*151*151}, which sum to 816422, in case that helps. Interestingly the "naughty boy" is a product of so few primes, and the original above, 14641 is 11*11*11*11. --Pete Lomax (talk) 11:50, 11 February 2021 (UTC)

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! --PureFox (talk) 14:23, 11 February 2021 (UTC)

Sorry! Both the REXX and Go entries report 150,252 not 150,232 untouchable numbers up to 1 million (ouch!).
I will quickly add that it just took the Julia entry 58mins to get the correct result, on this box. --Pete Lomax (talk) 14:45, 13 February 2021 (UTC)

Doh, what a stupid and embarrassing mistake! I've reverted the Go entry back to a limit of 1e5 until I can find time to sort out the 1e6 figure. --PureFox (talk) 17:03, 13 February 2021 (UTC)

Well, after spending some time re-examining this, I think I may have to retire hurt as I'm not going to be able to get anywhere near Julia's time for a million untouchables.

Reverting to 100,000 untouchables where Julia was using a sieve limit of 32 million, it's time was only about 1.5 minutes on my machine. Rewriting the Go program to use a similar approach and, even after adding some optimizations, the time was about 11.5 minutes which is nearly 8 times slower! So, for a million untouchables and a sieve limit of 512 million, if Julia is taking just under an hour, the Go program will likely take north of 8 hours which is far more than I have the patience for.

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.

--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.

I'm going to play with it some more before posting on the main page. --PureFox (talk) 09:11, 14 February 2021 (UTC)

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. --PureFox (talk) 16:36, 14 February 2021 (UTC)

Number of untouchable numbers up to 2 3 6 million

I've calculated 2 million as 305290. As Adrian Monk puts it "I could be wrong, but I never am."--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!--Nigel Galloway (talk) 16:00, 25 February 2021 (UTC)

those who say this algorithm is too slow, somewhat against 4 s on TIO.RUN

it is but how to estimated a good Multiple of LIMIT to find all.

--Horsth (talk) 14:06, 2 September 2021 (UTC)

Running F# to 6 million seems to agree with uupaper3.pdf

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

--Nigel Galloway (talk) 15:31, 5 September 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

Path=1;2    Path=1;3    Path=1;5    Path=1;7
   Π=2         Π=3         Π=5         Π=7
   Σ=1         Σ=1         Σ=1         Σ=1

Level=2 N=2..10 Untouchables=None

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

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)

Path=1;2;2;2  Path=1;2;2;3  Path=1;3;3;3
   Π=8           Π=12          Π=27
   Σ=7           Σ=16          Σ=13

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.--Nigel Galloway (talk) 14:55, 11 February 2021 (UTC)

I was thinking along (vaguely) similar lines, seeing it spelt out like that clarified a couple of points:

It is guaranteed to iterate through all composite numbers (as long as we carry on until Σ too big), and we have no interest in (large) primes.

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.--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})? --Pete Lomax (talk) 08:03, 12 February 2021 (UTC)

I should have turned my poor suffering computer on earlier, it can add up better than I.--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... --Pete Lomax (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!--Nigel Galloway (talk) 14:48, 14 February 2021 (UTC)

Calculating Π and Σ

Considering lemma 13 and the general discussion of Sum Of Divisors on Wolfram[1] I construct the following example for part of 1 path through the above tree.

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
.....
.....

Where i is the current prime, e is 1+i+i²+i³....., and l is i², i³....., 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.
Rule 2 is applied when the prime changes: i<-new prime; Π<-Π*i; g<-e*g; e<-1+i; and l<-i*i. --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.

--Tigerofdarkness (talk) 18:58, 28 June 2021 (UTC)