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)