Talk:Zumkeller numbers

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)