Zumkeller numbers: Difference between revisions

Content added Content deleted
m (→‎{{header|AppleScript}}: Minor tweaks, comment and label changes, optional cheat to reduce the stretch goal time.)
m (→‎{{header|AppleScript}}: Incorporated "abundant number" optimisation for odd numbers.)
Line 550: Line 550:


=={{header|AppleScript}}==
=={{header|AppleScript}}==
On my machine, this takes about 0.35 seconds to perform the two main searches and a further 109 to do the stretch task. However, the latter time can be dramatically reduced to 1.87 seconds with the cheat of foreknowing that at least the first 200 odd Zumkellers not ending with 5 are divisible by 63.
On my machine, this takes about 0.28 seconds to perform the two main searches and a further 107 to do the stretch task. However, the latter time can be dramatically reduced to 1.7 seconds with the cheat of knowing beforehand that the first 200 or so odd Zumkellers not ending with 5 are divisible by 63. The "abundant number" optimisation's now used with odd numbers, but the cheat-free running time was only two to three seconds longer without it.


<lang applescript>-- Return n's proper divisors.
<lang applescript>-- Sum n's proper divisors.
on aliquotSum(n)
⚫
if (n < 2) then return 0
⚫
set sum to 1
⚫
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set sum to sum + limit
set limit to limit - 1
⚫
end if
⚫
repeat with i from 2 to limit
if (n mod i is 0) then set sum to sum + i + n div i
⚫
end repeat
⚫
return sum
end aliquotSum

-- Return n's proper divisors.
on properDivisors(n)
on properDivisors(n)
set output to {}
set output to {}
Line 599: Line 616:
-- Is n a Zumkeller number?
-- Is n a Zumkeller number?
on isZumkeller(n)
on isZumkeller(n)
-- Yes if its aliquot sum is greater than or equal to it, the difference between them is even, and
script o
-- Get n's proper divisors. n itself isn't needed or wanted in this list.
-- either n is odd or a subset of its proper divisors sums to the average of it and all its proper divisors.
-- The 'or equal' logic works because (below 2,000,000 at least) no odd numbers, and only the even
property divisors : properDivisors(n)
-- Zumkellers 6, 28, 496, and 8128, /are/ equal to their aliquot sums. The rest are all greater or smaller.
⚫
end script
-- Using the aliquotSum() handler not only saves creating and looping through a list of the proper divisors
⚫
-- when n is odd, but the result also eliminates enough evens that calling properDivisors() on top of that
-- Sum all the divisors (including n) and halve the result, rounding towards zero.
-- to handle what's left is still faster than using properDivisors() with all the even numbers.
⚫
set sum to n
tell aliquotSum(n) to ¬
⚫
repeat with thisDivisor in o's divisors
set sum to sum + thisDivisor
return ((it ≥ n) and ((it - n) mod 2 = 0) and ¬
((n mod 2 = 1) or (my subsetSumsTo(my properDivisors(n), (it + n) div 2))))
⚫
end repeat
⚫
set halfSum to sum div 2
-- If the result's large enough, accurate, and summable to from a subset of the divisors, n's a Zumkeller.
⚫
if ((halfSum < n) or (halfSum < sum / 2)) then return false
return ((halfSum = n) or (subsetSumsTo(o's divisors, halfSum)))
end isZumkeller
end isZumkeller


Line 681: Line 693:
end script
end script
if (cheating) then
if (cheating) then
-- Knowing that at least the first 200 odd Zumkellers not ending with 5
-- Knowing that the HCF of at least the first 200 odd Zumkellers which don't end with 5
-- are divisible by 63, only check each 126th number, starting with 63 itself.
-- is 63, only check 63 and each 126th number thereafter.
-- (Somewhere between 200 and 500, the HCF reduces to 21, so adjust accordingly.)
set zumkellers to zumkellerNumbers(40, 63, 126, no5Multiples)
set zumkellers to zumkellerNumbers(40, 63, 126, no5Multiples)
else
else
Retrieved from "https://rosettacode.org/wiki/Zumkeller_numbers"