Talk:Zumkeller numbers: Difference between revisions
m (added a forced TOC (for now).) |
|||
Line 1:
__TOC__
== Why this limitation in c++ ==
|
Revision as of 11:31, 21 July 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 checkedAll 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.
- My real intention was to find a justification for
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)
Cheating odd no 5 zumkeller numbers
there are more restrictions for finding those zumkeller numbers quick: The first not divisible by 3^2*7 aka 63 is #204:6,789,783
203:6729723 : 80 : 3^4*7*11*13*83_chk_6729723<_SoD_13660416< 6830208 = 21+117+1079+11869+87399+6729723 = 6830208 204:6789783 : 96 : 3*7^2*11*13*17*19_chk_6789783<_SoD_13789440< 6894720 = 931+15827+88179+6789783 = 6894720 205:6837831 : 96 : 3^3*7*11^2*13*23_chk_6837831<_SoD_14300160< 7150080 = 3+33+759+14157+297297+6837831 = 7150080
The first not divisible by 3*7 aka 21 is #908:28,683,369
907:28639611 :108 : 3^2*7*11^2*13*17^2_chk_28639611<_SoD_59449936< 29724968 = 9+187+17017+200277+867867+28639611 = 29724968 908:28683369 :128 : 3^3*11*13*17*19*23_chk_28683369<_SoD_58060800< 29030400 = 19+57+1311+55913+289731+28683369 = 29030400 909:28765737 : 96 : 3^2*7*11*13*31*103_chk_28765737<_SoD_58146816< 29073408 = 1+9+63+143+2163+14729+290563+28765737 = 29073408
It might be possible that those numbers aren't divisible by 3. Replace 5 by 7. Therefor it must be a very large number.
first zumkeller not divible by 2 or 3 0: 5,391,411,025 :384 : 5^2*7*11*13*17*19*23*29_SoD_10799308800 this:46,797,447,697 :768 : 7^2*11*13*17*19*23*29*31 is to small
- Hi. Thanks for checking out the speed cheat in the AppleScript solution's stretch goal code. While the cheat's a handy way to pre-filter numbers for the particular stretch goal and thus to speed up running the task, it's clearly no use to anyone urgently needing more than the first 203 odd Zumkeller numbers not ending with 5 in real life!