Talk:Zumkeller numbers: Difference between revisions
m (→Where to find count of Zumkeller to verify solutions.Is there a constant ratio 0.228...?: new timings) |
|||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
__TOC__ |
|||
== Why this limitation in c++ == |
== Why this limitation in c++ == |
||
Line 4: | Line 6: | ||
if (n % 2 || d.size() >= 24) |
if (n % 2 || d.size() >= 24) |
||
return true;</pre> |
return true;</pre> |
||
99504 has 30 divisors and is not a |
99504 has 30 divisors and is not a Zumkeller number.<BR> |
||
Tested with GO version: |
|||
<lang go>func main() { |
<lang go>func main() { |
||
fmt.Println("The first 220 Zumkeller numbers are:") |
fmt.Println("The first 220 Zumkeller numbers are:") |
||
Line 13: | Line 15: | ||
<pre> |
<pre> |
||
99500 99510 99512 99516 99520 </pre> |
99500 99510 99512 99516 99520 </pre> |
||
Tested with cpp version: |
|||
<lang cpp> |
<lang cpp> |
||
int main() { |
int main() { |
||
Line 29: | Line 31: | ||
99500 99504 99510 99512 99516 </pre> |
99500 99504 99510 99512 99516 </pre> |
||
Checked the first 100,000 |
Checked the first 100,000 Zumkeller numbers.<BR> |
||
First |
First occurrence of Non-Zumkeller number with count of divisors |
||
<pre> |
<pre> |
||
Div |
Div |
||
Line 47: | Line 49: | ||
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?--[[User:Mckann|Mckann]] ([[User talk:Mckann|talk]]) 03:35, 12 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?--[[User:Mckann|Mckann]] ([[User talk:Mckann|talk]]) 03:35, 12 May 2021 (UTC) |
||
: I think the overflow will happen with 32 Bit aka uint.<br>If you change d.size to >30-Bit it will take a while and find 99504 to be a non- |
: I think the overflow will happen with 32 Bit aka uint.<br>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) |
if (n % 2 || d.size() > 30) |
||
return true;</lang> |
return true;</lang> |
||
Line 57: | Line 59: | ||
:: There is no.<BR>In '[[oeis:A083207|OEIS:A083207 - Zumkeller numbers]] someone stated and checked <pre>All 205283 odd abundant numbers less than 10^8 that have even abundance are Zumkeller numbers. - T. D. Noe, Nov 14 2010</pre> something one can use. |
:: There is no.<BR>In '[[oeis:A083207|OEIS:A083207 - Zumkeller numbers]] someone stated and checked <pre>All 205283 odd abundant numbers less than 10^8 that have even abundance are Zumkeller numbers. - T. D. Noe, Nov 14 2010</pre> something one can use. |
||
Oh I see. It works, empirically, for N >> max |
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. --[[User:Mckann|Mckann]] ([[User talk:Mckann|talk]]) 16:45, 15 May 2021 (UTC) |
||
== Where to find count of |
== 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.On AMD 2200G Linux 64-bit |
|||
<pre> |
|||
Start 1 at 1 |
|||
100000000 tested found 22879037 ratio 0.2287904 recursion 1.101 runtime 9.777 s |
|||
200000000 tested found 45744040 ratio 0.2287202 recursion 1.116 runtime 10.640 s |
|||
300000000 tested found 68603020 ratio 0.2286767 recursion 1.171 runtime 11.159 s |
|||
400000000 tested found 91458844 ratio 0.2286471 recursion 1.230 runtime 11.506 s |
|||
500000000 tested found 114316149 ratio 0.2286323 recursion 1.283 runtime 11.770 s |
|||
600000000 tested found 137176153 ratio 0.2286269 recursion 1.332 runtime 20.701 s |
|||
700000000 tested found 160037821 ratio 0.2286255 recursion 2.834 runtime 22.288 s |
|||
800000000 tested found 182899550 ratio 0.2286244 recursion 2.786 runtime 13.064 s |
|||
900000000 tested found 205760422 ratio 0.2286227 recursion 2.691 runtime 12.682 s |
|||
1000000000 tested found 228620760 ratio 0.2286208 recursion 2.620 runtime 12.842 s |
|||
total 136s = 2m16s ( 228620758 1000000000 time 2763.437 s (2 with high recursion >1e8 added as true ) ) |
|||
</pre> |
|||
[[user Horst.h|Horst.h]] 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 |
|||
<pre> |
|||
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</pre> |
|||
The first not divisible by 3*7 aka 21 is #908:28,683,369 |
|||
<pre> |
|||
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</pre> |
|||
It might be possible that those numbers aren't divisible by 3. |
|||
Replace 5 by 7. Therefor it must be a very large number. |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
: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 have modified the program to run up to 1E9 |
|||
<pre>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 |
|||
: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. --[[User:Nig|Nig]] ([[User talk:Nig|talk]]) 11:25, 21 July 2021 (UTC) |
|||
count of count of last with |
|||
::Look for [[Perfect_numbers]] there is a link odd perfect numbers ( > 10^2000 ;-) ) |
|||
divisors occurence this count |
|||
:::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. ;) --[[User:Nig|Nig]] ([[User talk:Nig|talk]]) 13:25, 21 July 2021 (UTC) |
|||
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</pre> |
|||
[[user Horsth|Horsth]] 06:28, 20 June 2021 (UTC) |
Latest revision as of 12:10, 31 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.
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.On AMD 2200G Linux 64-bit
Start 1 at 1 100000000 tested found 22879037 ratio 0.2287904 recursion 1.101 runtime 9.777 s 200000000 tested found 45744040 ratio 0.2287202 recursion 1.116 runtime 10.640 s 300000000 tested found 68603020 ratio 0.2286767 recursion 1.171 runtime 11.159 s 400000000 tested found 91458844 ratio 0.2286471 recursion 1.230 runtime 11.506 s 500000000 tested found 114316149 ratio 0.2286323 recursion 1.283 runtime 11.770 s 600000000 tested found 137176153 ratio 0.2286269 recursion 1.332 runtime 20.701 s 700000000 tested found 160037821 ratio 0.2286255 recursion 2.834 runtime 22.288 s 800000000 tested found 182899550 ratio 0.2286244 recursion 2.786 runtime 13.064 s 900000000 tested found 205760422 ratio 0.2286227 recursion 2.691 runtime 12.682 s 1000000000 tested found 228620760 ratio 0.2286208 recursion 2.620 runtime 12.842 s total 136s = 2m16s ( 228620758 1000000000 time 2763.437 s (2 with high recursion >1e8 added as true ) )
Horst.h 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 ;-) )