View source for Talk:Self numbers

== Improvement to the clever sieving of purefox ==

It takes a lot of space for sieving all.<BR>
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<BR>
So the upper limit is 10,000 +(max digitcount)*9 -1 here 10,107<BR>
For example:<BR>
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. [[user Horst.h|Horst.h]] 18:20, 7 October 2020 (UTC)
:New observation using Base*Base+1 = 101. Line 0 is modified 1,3,5 are deleted<BR>
:Many same lines, changes in constant distances only a rotation of line 1 with some.
:There shall be a build system for this pattern.
:mostly 10 out of 101 are selfnumbers, every 9*101 -2 , every 99*101 -3 , every 999*101 -4
:
<pre>
annotation number of self numbers up to 
         101        13
        1010       103
       10100       991
      101000      9880
     1010000     98761
    10100000    987562
   101000000   9875563
  1010000000  98755565
 10100000000 987555566

          n  Div 101
           0       0 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         101       1 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         202       2 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         303       3 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         404       4 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         505       5 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         606       6 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         707       7 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         808       8 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
         909       9 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
-- rotate             <<<<<<<<<
--                   v deleted
        1010      10 00000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010
--                   v inserted
        1111      11 10000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010
--
        1818      18 10000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010
--                                                                                                                      v
        1919      19 10000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000000000000
        2020      20 00100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010100000000
--
        2828      28 00100000000001000000000010000000000100000000001000000000010000000000100000000001000000000010100000000
--                                                                                                             vvv
        2929      29 00100000000001000000000010000000000100000000001000000000010000000000100000000001000000000000001000000
        3030      30 00001000000000010000000000100000000001000000000010000000000100000000001000000000010100000000001000000
--                                                                                                    vvv
        3939      39 00001000000000010000000000100000000001000000000010000000000100000000001000000000000001000000000010000
        4040      40 00000010000000000100000000001000000000010000000000100000000001000000000010100000000001000000000010000
--
        4848      48 00000010000000000100000000001000000000010000000000100000000001000000000010100000000001000000000010000
                                                                                             vvv
        4949      49 00000010000000000100000000001000000000010000000000100000000001000000000000001000000000010000000000100
        5050      50 00000000100000000001000000000010000000000100000000001000000000010100000000001000000000010000000000100
--                                                                                  vvv
        5959      59 00000000100000000001000000000010000000000100000000001000000000000001000000000010000000000100000000001
        6060      60 00000000001000000000010000000000100000000001000000000010100000000001000000000010000000000100000000001
--                                                                         vvv
        6969      69 00000000001000000000010000000000100000000001000000000000001000000000010000000000100000000001000000000
        7070      70 01000000000010000000000100000000001000000000010100000000001000000000010000000000100000000001000000000
--                                                                vvv
        7979      79 01000000000010000000000100000000001000000000000001000000000010000000000100000000001000000000010000000
        8080      80 00010000000000100000000001000000000010100000000001000000000010000000000100000000001000000000010000000
--                                                       vvv
        8989      89 00010000000000100000000001000000000000001000000000010000000000100000000001000000000010000000000100000
        9090      90 00000100000000001000000000010100000000001000000000010000000000100000000001000000000010000000000100000
--                                   V          VVV
        9999      99 00000100000000000000000000000000010000000000100000000001000000000010000000000100000000001000000000010
----
       99889     989 01000000000010000000000100000000001000000000010100000000001000000000010000000000100000000001000000000
--                                          v          v          vvv
       99990     990 01000000000010000000000000000000000000000000000000000100000000001000000000010000000000100000000001000
First line found:
..8810 matches found... last one
   100992930  999930 00000001010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001000
</pre>
[[user:Horsth|Horsth]] [[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 07:01, 9 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) [https://tio.run/##bZLdjpswEIXveYpTpEqwWCtYqVKzjl@hqtTe7eaCHxucgFmBk16s8uzpeEJXrlouOPKcz/YMnH6@3d7q9lT3GlNtXZLY6W1ePLLUTD6VqbeTTvMkMWfXYrX6orMcL4dmnke8J8B6EXB4VrT7pLO7IfD0UOldsXvYFVUuUBJn5gW1qMeAlqIqJWrsgSfJVVUXFUlR8ZmBbUTDbHAlGmJZqaoaYpuYbUXLbHAlWmJZqapaYtuY7UTHbHAlOmJZqao6YruY1UIzG1wJTSwrVZUmVsesEYbZ4EoYYlmpqgyxJmZ70TMbXImeWFaqqp7YPmYHMTAbXImBWFaqqoHYIWatsMwGV8ISy0pVZYm1MXsMoJWke1iijkWBd5AZfunLsXAHKPjlrCUcWdePh5BF@/PiiEuuWzBCdCgXHAgvOBTtfHY@XBIS9Pht/pVRErYAbZGY/OP3xTo/uiz9OWgYu6weX0qsejRw56nRy4p60c@UwG1Ezs99uFG7bL3ktAi9c@vW4BO1bw/bGvc2ikIG697SXoUr/vhRGyZLP3dIBWy@mddNP/YqhUp//d/mMMOre3VhjqosMdlxtLPzQzwM7BofDzSLrk9/XRbe138@zjyfaCN/yR/WtTpbfZ4n19vtNw linky]

Just saw Horst's idea, haven't incorporated it yet.--[[User:Enter your username|Enter your username]] ([[User talk: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. --[[User:PureFox|PureFox]] ([[User talk: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 :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 12:53, 8 October 2020 (UTC)