Zumkeller numbers: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Alextretyak (talk | contribs)
1,481 edits
Added 11l
Nig (talk | contribs)
557 edits
m →‎{{header|AppleScript}}: Revised subset sum handler. Some comment work..
Line 702: Line 702:


-- Does a subset of the given list of numbers add up to the target value?
-- Does a subset of the given list of numbers add up to the target value?
on subsetSumsTo(listOfNumbers, target)
on subsetOf:numberList sumsTo:target
script o
script o
property lst : listOfNumbers
property lst : numberList
property someNegatives : false
on recursion(target, i)
on ssp(target, i)
repeat while (i > 1)
repeat while (i > 1)
set n to item i of my lst
set n to item i of my lst
set i to i - 1
set i to i - 1
if (n < target) then
if ((n = target) or (((n < target) or (someNegatives)) and (ssp(target - n, i)))) then return true
if (recursion(target - n, i)) then return true
⚫
else if (n = target) then
return true
⚫
end if
end repeat
end repeat
return (target = beginning of my lst)
return (target = beginning of my lst)
end recursion
end ssp
end script
end script
-- The search can be more efficient if it's known the list contains no negatives.
repeat with n in o's lst
⚫
if (n < 0) then
set o's someNegatives to true
exit repeat
⚫
end if
end repeat
return o's recursion(target, count o's lst)
return o's ssp(target, count o's lst)
end subsetOf:sumsTo:
end subsetSumsTo


-- 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
-- Yes if its aliquot sum is greater than or equal to it, the difference between them is even, and
-- either n is odd or a subset of its proper divisors sums to the average of it and all its proper divisors.
-- either n is odd or a subset of its proper divisors sums to half the sum of the divisors and it.
-- Using aliquotSum() to get the divisor sum and then calling properDivisors() too if a list's actually
-- The 'or equal' logic works because (below 2,000,000 at least) no odd numbers, and only the even
-- needed is generally faster than using properDivisors() in the first place and summing the result.
-- Zumkellers 6, 28, 496, and 8128, /are/ equal to their aliquot sums. The rest are all greater or smaller.
⚫
set sum to aliquotSum(n)
-- Using the aliquotSum() handler not only saves creating and looping through a list of the proper divisors
⚫
return ((sum ≥ n) and ((sum - n) mod 2 = 0) and ¬
-- when n is odd, but the result also eliminates enough evens that calling properDivisors() on top of that
-- to handle what's left is still faster than using properDivisors() with all the even numbers.
((n mod 2 = 1) or (my subsetOf:(properDivisors(n)) sumsTo:((sum + n) div 2))))
⚫
tell aliquotSum(n) to ¬
⚫
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 isZumkeller
end isZumkeller


Line 802: Line 803:
end script
end script
if (cheating) then
if (cheating) then
-- Knowing that the HCF of at least the first 200 odd Zumkellers which don't end with 5
-- Knowing that the HCF of the first 203 odd Zumkellers not ending with 5
-- is 63, only check 63 and each 126th number thereafter.
-- is 63, just check 63 and each 126th number thereafter.
-- (Somewhere between 200 and 500, the HCF reduces to 21, so adjust accordingly.)
-- For the 204th - 907th such numbers, the HCF reduces to 21, so adjust accordingly.
-- (See Horsth's comments on the Talk page.)
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"