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.
Tested 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
Tested 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 occurrence 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!
- I was initially more concerned about my assumption in the isZumkeller() handler logic that odd numbers are always either less than or greater than their aliquot sums, never equal to them. But I've tested up to 9,999,999 this morning and it's held true so far. --Nig (talk) 11:25, 21 July 2021 (UTC)
- Look for Perfect_numbers there is a link odd perfect numbers ( > 10^2000 ;-) )
- The "Odd Perfect" link isn't working, but the Wikipedia entry says: "It is unknown whether there is any odd perfect number, though various results have been obtained." Numbers beyond 10^2000 are definitely beyond AppleScript's resolution — not to mention that getting to them would take more than the lifetime of the average AppleScript user. So that's a weight off my mind. ;) --Nig (talk) 13:25, 21 July 2021 (UTC)
- Look for Perfect_numbers there is a link odd perfect numbers ( > 10^2000 ;-) )