Talk:Self numbers

Improvement to the clever sieving of purefox

It takes a lot of space for sieving all.
Thinking of a highest number to test has 12 digits then max digitcount is 12. One can use small blocks of 10,000 (or 100,000 ( 4..5 digits )) + an extension of (max digitcount)*9
So the upper limit is 10,000 +(max digitcount)*9 -1 here 10,107
For example:
After marking the first 10000 (n = 0--9999) not selfnumbers the last marked is 9999+4*9 = 10035 Now counting all selfnumbers 0..9999 than copy 10000- (max digitcount)*9 to Position 0..- (max digitcount)*9 and clear the rest to the upper limit. This can all be done lightning fast in Level I cache. Horst.h 18:20, 7 October 2020 (UTC)

I tought about one more time, because the CountOfSelfnumbers(n)/n ist nearly constant .

I mark once every follower of a number by adding its sum of digits in a range of 0..9999+(max digitcount)*9.

My window size is 0..9999.

For the first time I count the elements 0..9999

The next time I move the start of the window by one, the sum of digit in front of the four digits, for the range 10000..19999.

Than I move the start of the window by 2, the sum of digit in front of the four digits, for the range 20000..29999.

....

..by 72 ( 8*9) for 99999999_0000 to 99999999_9999

Now I think, i memorize the sum of self numbers (x..x+9999) at the Position 0..72, so only one time of counting is needed

Using the array SumOfDigits 0..9999 i can do it for that elemnents too

Is it that simple? Horsth Horsth (talk) 05:02, 8 October 2020 (UTC)

Go, tweaked

Rearranged some of the nested additions, seems to go around 25% faster, or so. (Original was taking over 12 seconds on tio.run) linky

Just saw Horst's idea, haven't incorporated it yet.--Enter your username (talk) 19:47, 7 October 2020 (UTC)

Actually, I wondered after I'd done the 'sieve based' version whether using partial sums for each loop would quicken it up but, when it came in so much faster than the 'low memory' version, I didn't bother investigating further.

Anyway I've now tested it and it does indeed improve performance by around 25% so I've incorporated it into the main page. Have done it slighly different to you (using an array of partial sums) to keep it more 'go fmt' friendly.

Incidentally, the timings are for my core i7 which is why they're much faster than tio.run's.

Might do a separate version incorporating Horst.h's ideas as I suspect it might come in a bit slower for the basic task of 100 million numbers while allowing us to stretch that to 1 billion. But we'll see. --PureFox (talk) 09:06, 8 October 2020 (UTC)

I was wrong. Horst.h's approach is not only quicker for 100 million numbers but I can't even extend the second version to do up to 1 billion numbers without running into memory issues. So I've added a third version. A little slower than Pascal but not too bad :) --PureFox (talk) 12:53, 8 October 2020 (UTC)