For those interested, info can be found at:
[A] http://arxiv.org/pdf/0912.0052
[B] OEIS: http://www.research.att.com/~njas/sequences/A083207
[C] http://www.luschny.de/math/seq/ZumkellerNumbers.html
Zumkeller numbers are numbers from which the divisor set can be divided
in two disjunct sets with equal sums. The first few are:
6 [6] [1, 2, 3]
12 [2, 12] [1, 3, 4, 6]
20 [1, 20] [2, 4, 5, 10]
24 [6, 24] [1, 2, 3, 4, 8, 12]
28 [28] [1, 2, 4, 7, 14]
Facts used to decide if a number is zumkeller can be found in ref. A,
summarized:
fact 2: The sum of the divisors of n must be even
fact 3: The sigma test. n is a Zumkeller number if and only if
(sigma(n)-2n)/2 is either zero or is a sum of distinct positive factors
of n excluding n itself.
fact 4: The sum of the divisors of n must be >= 2n
I start with the translation of a Haskell program:
We need the descending sorted divisors of N (from JEssays):
divs=: 13 :'\:~ , > */&>/(^ i.@>:)&.>/__ q: y'
The 'slowing things down' sigma-test:
[1] sigmat =: [ (((- {.) $: }...@]) +. ($: }.))`0:@.(0...@])`1:@.(0=[) >:#]
zumkeller =: 3 : 0
s=. +/ fs=. divs y
if. (2|s) +. s < +: y do. 0 else.
(s&-&.+:y) sigmat fs end.
)
(#~zumkeller) 1+i.100
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96
Improvement in speed for the sigma-test by building a tree instead of
the double recursion divide and conquer.
NB. expand & prune
expand=:[: (#~a:~:]) [:,({. ([ (((-{.),}...@])&.> <\.) >:#]) }.) &>
NB. termination predicate and test for Zumkeller(ness).
pred=: +./@:(0 =;)
not24=: (2&|@[ +. <)/@(2&{.)
sigmaTest=: pred @ (expand^:(-...@pred)^:_)
zumkellerT=: [: sigmaTest@<@(2&(-:@-/@{.,}.))`0:@.not24 (+/,}.,~+:@{.)@divs
ts '(#~zumkellerT"0) 6+i.495'
0.1196 406528
ts '(#~zumkeller"0) 6+i.495'
27.439572 43520
A drawback with the second and improved version is the time-consuming
iteration for numbers with a large number of divisors and a 'late'
finding of a true/false (i.e. building a fat tree).
Example of a problem:
zumkellerT 80010
|out of memory: expand
| zumkellerT 80010
The Haskell program finds a true for this one.
If you are still with me here, what further improvements do you think
are possible (incl. different approaches)?
TIA
[1] with this kind of code Haskell seems much faster. Excerpt
....
sigmaTest 0 _ = True
sigmaTest _ [] = False
sigmaTest n (f:fs)
| f > n = sigmaTest n fs
| otherwise = sigmaTest (n-f) fs || sigmaTest n fs
--
Met vriendelijke groet,
=@@i
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
