Talk:Zumkeller numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 06:28, 20 June 2021

Why this limitation in c++

    // if we get here and n is odd or n has at least 24 divisors it's a zum!
    if (n % 2 || d.size() >= 24)
        return true;

99504 has 30 divisors and is not a zumkeller number.
Testet with GO version: <lang go>func main() {

   fmt.Println("The first 220 Zumkeller numbers are:")
   for i, count := 99500, 0; count < 5; i++ {
       if isZumkeller(i) {
           fmt.Printf("%3d ", i)</lang>

99500 99510 99512 99516 99520

Testet with cpp version: <lang cpp> int main() {

   cout << "First 220 Zumkeller numbers:" << endl;
   vector<uint> zumz;
   for (uint n = 99500; zumz.size() < 5; n++)
       if (isZum(n))
           zumz.push_back(n);
   cout << zumz << endl << endl;

...

   // if we get here and n is odd or n has at least 24 divisors it's a zum!
   if (n % 2 || d.size() >= 29)
       return true;</lang>

     99500      99504      99510      99512      99516

Checked the first 100,000 zumkeller numbers.
First occurence of Non-Zumkeller number with count of divisors

Div 
count    number
  12       738
  16      7544
  18      3492
  20     56816
  24     14184
  30     58896
  36    236448

Horsth 06:56, 9 May 2021 (UTC)

Good find! It's probably a bug. I'll look into it when I get a chance, thank you. --Mckann (talk) 16:47, 11 May 2021 (UTC)

I took a look and I'm not getting those numbers in the output. Can I see how you unit tested this? I'm not sure why that would matter though... my best guess is an OS dtype issue causing overflow but that seems unlikely. What IDE/OS did you run this on?--Mckann (talk) 03:35, 12 May 2021 (UTC)

I think the overflow will happen with 32 Bit aka uint.
If you change d.size to >30-Bit it will take a while and find 99504 to be a non-zumkeller number.<lang c++>// if we get here and n is odd it's a zum!

   if (n % 2 || d.size() > 30)
       return true;</lang>

Your program is limited to 31 divisors.
I'm testing mostly in the web on TIO.RUN like TIO.RUN/#cpp-gcc to be comparable. d.size >30 takes more than 60s limit :-(
Horsth (talk) 06:41, 12 May 2021 (UTC)

Alright, so I'm not seeing any overflow here. the variable d points to a vector of unsigned ints, stored in an array, so d.size() can become extremely large. I think the largest set I saw was 88 divisors, and the sum did not overflow. I also am still not seeing the bad outputs you did, so I'm not sure what's going on there, except for 99504. I use the condition odd|n divisors > 24 but I don't think that holds for large N if N is even. 99504 may be the first number that gets through. Given the problem description I didn't anticipate large even numbers to be evaluated; they get filtered before printing to console anyhow, so I think I wrote it that way for efficiency. I really don't remember. If you remove that condition the output looks fine through the first 100 000, but it will take a very long time. Probably, if you want to improve on this, there are a few handy properties of the sequence that could be used to bring time complexity down. But really, changing the data structure for d to make insertion faster and working with base 2 throughout instead of converting for no good reason would really speed up computation time. And there are lots of places to trade space for time, too. --Mckann (talk) 23:38, 12 May 2021 (UTC)

My real intention was to find a justification for

or n has at least 24 divisors it's a zum!

There is no.
In 'OEIS:A083207 - Zumkeller numbers someone stated and checked

All 205283 odd abundant numbers less than 10^8 that have even abundance are Zumkeller numbers. - T. D. Noe, Nov 14 2010

something one can use.

Oh I see. It works, empirically, for N >> max zumkeller number needed for the problem and reduces runtime appreciably. That's the justification. I should put a comment in there, thank you. --Mckann (talk) 16:45, 15 May 2021 (UTC)

Where to find count of zumkeller to verify solutions.Is there a constant ratio 0.228...?

I have modified the program to run up to 1E9

Count of zumkeller numbers up to 1,000,000,000
     count            n
       224         1000 time    0.004 s
      2294        10000 time    0.005 s
     23051       100000 time    0.016 s
    229026      1000000 time    0.241 s
   2287889     10000000 time    5.031 s
  22879037    100000000 time  114.117 s
 228620758   1000000000 time 2763.437 s

  count of  count of   last with
  divisors occurence   this count
         4         1            6
         6         3           28
         8   9327007    999999894
        10        10          496
        12  10043024    999999996
        14        30         8128
        16  29081897    999999978
        18      3061    999625548
        20   4470960    999999952
        22       308      2087936
        24  28328093    999999948
        26      1027     33550336
        28   1640168    999999680
        30     22909    999449264
        32  34193954    999999912
        34      1778    998834176
        36   5108860    999999740
        38       528    996933632
        40   8732428    999999984
        42     39946    999995456
        44    165649    999992320
        46        50    977272832
        48  30404269    999999980
        50      7343    999930064
        52     43316    999993344
        54    127846    999986004
        56   2231014    999999918
        58         1    805306368
        60   2285988    999999056
        64  17785246    999999966
        66     14418    999857152
        68      2944    999620608
        70     10065    999863488
        72   7612581    999999612
        76       751    999030784
        78      6291    999657472
        80   5097772    999999888
        84    550440    999998400
        88    125242    999994368
        90     99455    999990864
        92        45    994050048
        96  12888461    999999968
        98      2609    999978048
       100    137019   1000000000
       102       546    998703104
       104     29385    999985152
       108    672289    999999900
       110      1977    999392256
       112    983872    999999168
       114       163    993263616
       120   1793678    999999756
       126     30520    999949248
       128   4026453    999999750
       130       565    998977536
       132     32547    999982080
       136      1471    999882752
       138        10    868220928
       140     48252    999998784
       144   3107948    999999744
       150     13569    999970000
       152       301    999555072
       154       287    993912768
       156      7989    999788544
       160   1348234    999998480
       162     23768    999878400
       168    327063    999999936
       170        49    960823296
       176     41522    999945216
       180    191844    999997200
       182        77    988360704
       184         6    968884224
       190        14    997982208
       192   2404911    999999990
       196      3408    999884736
       198      2285    999756800
       200     74414    999987120
       204       434    997392384
       208      8206    999837696
       210      5189    999720000
       216    338514    999996900
       220      2270    999889920
       224    207061    999994560
       228        85    979107840
       234       622    998502400
       238         6    907739136
       240    503320    999999792
       242         4    786060288
       250       297    997110000
       252     34145    999993280
       256    420553    999999336
       260       506    999641088
       264     13404    999961600
       266         1    955514880
       270      7815    999967500
       272       236    999751680
       280     20719    999988416
       288    525917    999998880
       294       407    999604800
       300     13031    999990000
       304        26    994836480
       306        36    987955200
       308       213    999558144
       312      2573    998903808
       320    161781    999997680
       324     18434    999998208
       330       306    996480000
       336     70675    999972288
       340        18    992673792
       342         5    963379200
       350       137    998730000
       352      5606    999957504
       360     63310    999997488
       364        36    982388736
       378      1407    999132480
       380         1    743178240
       384    196619    999994842
       390        74    991678464
       392      1003    999000000
       396      1377    999429120
       400     13390    999979344
       408        49    997785600
       416       788    999198720
       420      3476    999625536
       432     53355    999980800
       440       538    998231040
       448     17624    999984960
       450       671    993322512
       456         1    908328960
       462        25    989107200
       468       242    998092800
       480     49670    999988080
       486       456    997210368
       490        11    903960000
       500       150    992631024
       504      7684    999979200
       510         1    928972800
       512     17626    999983880
       520        74    977080320
       528      1488    999060480
       540      3240    999791100
       544         3    984023040
       546         4    970444800
       550         6    995742720
       560      2348    999779760
       576     29682    999999840
       588       135    999044928
       594        49    942289920
       600      2171    999870480
       616        17    977163264
       624       142    999936000
       630       155    997012800
       640      6125    999989760
       648      2346    999532800
       660        65    997401600
       672      4038    999915840
       700        23    975240000
       702         5    858009600
       704       170    996602880
       720      4115    999702000
       750         8    958230000
       756       283    999835200
       768      4066    999814200
       780         4    987033600
       784        42    997738560
       792        84    999398400
       800       447    999217296
       810        45    968612400
       832         6    979292160
       840       236    996287040
       864      1338    999949860
       880        12    989936640
       882         4    987940800
       896       273    999311040
       900        63    998600400
       936         1    922521600
       960       635    999734400
       972        22    990662400
      1000         1    810810000
      1008       153    999028800
      1024        92    999999000
      1056         5    968647680
      1080        45    998917920
      1120        16    992431440
      1152        93    997682400
      1200         9    975466800
      1260         1    908107200
      1280         6    985944960
      1296         3    980179200
      1344         4    994593600

Horsth 06:28, 20 June 2021 (UTC)