Talk:Zumkeller numbers: Difference between revisions
m (→Why this limitation in c++: changing d.size gets the right solution) |
|||
Line 51: | Line 51: | ||
return true;</lang> |
return true;</lang> |
||
:Your program is limited to 31 divisors.<BR>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 :-(<br> [[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 06:41, 12 May 2021 (UTC) |
:Your program is limited to 31 divisors.<BR>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 :-(<br> [[User:Horsth|Horsth]] ([[User talk: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. |
|||
--[[User:Mckann|Mckann]] ([[User talk:Mckann|talk]]) 23:38, 12 May 2021 (UTC) |
Revision as of 23:38, 12 May 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)