Talk:Zumkeller numbers

From Rosetta Code
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 checked
All 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.

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)