Zumkeller numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Zumkeller numbers are the set of numbers whose divisors can be partitioned into two disjoint sets that sum to the same value. Each sum must contain divisor values that are not in the other sum, and all of the divisors must be in one or the other. There are no restrictions on how the divisors are partitioned, only that the two partition sums are equal.
- E.G.
- 6 is a Zumkeller number; The divisors {1 2 3 6} can be partitioned into two groups {1 2 3} and {6} that both sum to 6.
- 10 is not a Zumkeller number; The divisors {1 2 5 10} can not be partitioned into two groups in any way that will both sum to the same value.
- 12 is a Zumkeller number; The divisors {1 2 3 4 6 12} can be partitioned into two groups {1 3 4 6} and {2 12} that both sum to 14.
Even Zumkeller numbers are common; odd Zumkeller numbers are much less so. For values below 10^6, there is at least one Zumkeller number in every 12 consecutive integers, and the vast majority of them are even. The odd Zumkeller numbers are very similar to the list from the task Abundant odd numbers; they are nearly the same except for the further restriction that the abundance (A(n) = sigma(n) - 2n), must be even: A(n) mod 2 == 0
- Task
-
- Write a routine (function, procedure, whatever) to find Zumkeller numbers.
- Use the routine to find and display here, on this page, the first 220 Zumkeller numbers.
- Use the routine to find and display here, on this page, the first 40 odd Zumkeller numbers.
- Optional, stretch goal: Use the routine to find and display here, on this page, the first 40 odd Zumkeller numbers that don't end with 5.
- See Also
- OEIS:A083207 - Zumkeller numbers to get an impression of different partitions OEIS:A083206 Zumkeller partitions
- OEIS:A174865 - Odd Zumkeller numbers
- Related Tasks
AArch64 Assembly
<lang AArch64 Assembly> /* ARM assembly AARCH64 Raspberry PI 3B */ /* program zumkellex641.s */
/* REMARK 1 : this program use routines in a include file
see task Include a file language arm assembly for the routine affichageMess conversion10 see at end of this program the instruction include */
/* REMARK 2 : this program is not optimized.
Not search First 40 odd Zumkeller numbers not divisible by 5 */
/*******************************************/ /* Constantes file */ /*******************************************/ /* for this file see task include a file in language AArch64 assembly*/ .include "../includeConstantesARM64.inc"
.equ NBDIVISORS, 100
/*******************************************/
/* Structures */
/********************************************/
/* structurea area divisors */
.struct 0
div_ident: // ident
.struct div_ident + 8
div_flag: // value 0, 1 or 2
.struct div_flag + 8
div_fin: /*******************************************/ /* Initialized data */ /*******************************************/ .data szMessStartPgm: .asciz "Program start \n" szMessEndPgm: .asciz "Program normal end.\n" szMessErrorArea: .asciz "\033[31mError : area divisors too small.\n" szMessError: .asciz "\033[31mError !!!\n"
szCarriageReturn: .asciz "\n"
/* datas message display */ szMessEntete: .asciz "The first 220 Zumkeller numbers are:\n" sNumber: .space 4*20,' '
.space 12,' ' // for end of conversion
szMessListDivi: .asciz "Divisors list : \n" szMessListDiviHeap: .asciz "Heap 1 Divisors list : \n" szMessResult: .ascii " " sValue: .space 12,' '
.asciz ""
szMessEntete1: .asciz "The first 40 odd Zumkeller numbers are:\n" /*******************************************/ /* UnInitialized data */ /*******************************************/ .bss .align 4 tbDivisors: .skip div_fin * NBDIVISORS // area divisors sZoneConv: .skip 30 /*******************************************/ /* code section */ /*******************************************/ .text .global main main: // program start
ldr x0,qAdrszMessStartPgm // display start message bl affichageMess
ldr x0,qAdrszMessEntete // display message bl affichageMess mov x2,#1 // counter number mov x3,#0 // counter zumkeller number mov x4,#0 // counter for line display
1:
mov x0,x2 // number mov x1,#0 // display flag bl testZumkeller cmp x0,#1 // zumkeller ? bne 3f // no mov x0,x2 ldr x1,qAdrsZoneConv // and convert ascii string bl conversion10 ldr x0,qAdrsZoneConv // copy result in display line ldr x1,qAdrsNumber lsl x5,x4,#2 add x1,x1,x5
11:
ldrb w5,[x0],1 cbz w5,12f strb w5,[x1],1 b 11b
12:
add x4,x4,#1 cmp x4,#20 blt 2f //add x1,x1,#3 // carriage return at end of display line mov x0,#'\n' strb w0,[x1] mov x0,#0 strb w0,[x1,#1] // end of display line ldr x0,qAdrsNumber // display result message bl affichageMess mov x4,#0
2:
add x3,x3,#1 // increment counter
3:
add x2,x2,#1 // increment number cmp x3,#220 // end ? blt 1b
/* raz display line */ ldr x0,qAdrsNumber mov x1,' ' mov x2,0
31:
strb w1,[x0,x2] add x2,x2,1 cmp x2,4*20 blt 31b
/* odd zumkeller numbers */ ldr x0,qAdrszMessEntete1 bl affichageMess mov x2,#1 mov x3,#0 mov x4,#0
4:
mov x0,x2 // number mov x1,#0 // display flag bl testZumkeller cmp x0,#1 bne 6f mov x0,x2 ldr x1,qAdrsZoneConv // and convert ascii string bl conversion10 ldr x0,qAdrsZoneConv // copy result in display line ldr x1,qAdrsNumber lsl x5,x4,#3 add x1,x1,x5
41:
ldrb w5,[x0],1 cbz w5,42f strb w5,[x1],1 b 41b
42:
add x4,x4,#1 cmp x4,#8 blt 5f mov x0,#'\n' strb w0,[x1] strb wzr,[x1,#1] ldr x0,qAdrsNumber // display result message bl affichageMess mov x4,#0
5:
add x3,x3,#1
6:
add x2,x2,#2 cmp x3,#40 blt 4b
ldr x0,qAdrszMessEndPgm // display end message bl affichageMess b 100f
99: // display error message
ldr x0,qAdrszMessError bl affichageMess
100: // standard end of the program
mov x0, #0 // return code mov x8, #EXIT // request to exit program svc 0 // perform system call
qAdrszMessStartPgm: .quad szMessStartPgm qAdrszMessEndPgm: .quad szMessEndPgm qAdrszMessError: .quad szMessError qAdrszCarriageReturn: .quad szCarriageReturn qAdrszMessResult: .quad szMessResult qAdrsValue: .quad sValue qAdrszMessEntete: .quad szMessEntete qAdrszMessEntete1: .quad szMessEntete1 qAdrsNumber: .quad sNumber qAdrsZoneConv: .quad sZoneConv /******************************************************************/ /* test if number is Zumkeller number */ /******************************************************************/ /* x0 contains the number */ /* x1 contains display flag (<>0: display, 0: no display ) */ /* x0 return 1 if Zumkeller number else return 0 */ testZumkeller:
stp x1,lr,[sp,-16]! // save registers stp x2,x3,[sp,-16]! // save registers stp x4,x5,[sp,-16]! // save registers stp x6,x7,[sp,-16]! // save registers mov x7,x1 // save flag ldr x1,qAdrtbDivisors bl divisors // create area of divisors cmp x0,#0 // 0 divisors or error ? ble 98f mov x5,x0 // number of dividers mov x6,x1 // number of odd dividers cmp x7,#1 // display divisors ? bne 1f ldr x0,qAdrszMessListDivi // yes bl affichageMess mov x0,x5 mov x1,#0 ldr x2,qAdrtbDivisors bl printHeap
1:
tst x6,#1 // number of odd divisors is odd ? bne 99f mov x0,x5 mov x1,#0 ldr x2,qAdrtbDivisors bl sumDivisors // compute divisors sum tst x0,#1 // sum is odd ? bne 99f // yes -> end lsr x6,x0,#1 // compute sum /2 mov x0,x6 // x0 contains sum / 2 mov x1,#1 // first heap mov x3,x5 // number divisors mov x4,#0 // N° element to start bl searchHeap cmp x0,#-2 beq 100f // end cmp x0,#-1 beq 100f // end
cmp x7,#1 // print flag ? bne 2f ldr x0,qAdrszMessListDiviHeap bl affichageMess mov x0,x5 // yes print divisors of first heap ldr x2,qAdrtbDivisors mov x1,#1 bl printHeap
2:
mov x0,#1 // ok b 100f
98:
mov x0,-1 b 100f
99:
mov x0,#0 b 100f
100:
ldp x6,x7,[sp],16 // restaur 2 registers ldp x4,x5,[sp],16 // restaur 2 registers ldp x2,x3,[sp],16 // restaur 2 registers ldp x1,lr,[sp],16 // restaur 2 registers ret // return to address lr x30
qAdrtbDivisors: .quad tbDivisors qAdrszMessListDiviHeap: .quad szMessListDiviHeap /******************************************************************/ /* search sum divisors = sum / 2 */ /******************************************************************/ /* x0 contains sum to search */ /* x1 contains flag (1 or 2) */ /* x2 contains address of divisors area */ /* x3 contains elements number */ /* x4 contains N° element to start */ /* x0 return -2 end search */ /* x0 return -1 no heap */ /* x0 return 0 Ok */ /* recursive routine */ searchHeap:
stp x3,lr,[sp,-16]! // save registers stp x4,x5,[sp,-16]! // save registers stp x6,x8,[sp,-16]! // save registers
1:
cmp x4,x3 // indice = elements number
beq 99f
lsl x6,x4,#4 // compute element address
add x6,x6,x2
ldr x7,[x6,#div_flag] // flag equal ?
cmp x7,#0
bne 6f
ldr x5,[x6,#div_ident]
cmp x5,x0 // element value = remaining amount
beq 7f // yes
bgt 6f // too large
// too less
mov x8,x0 // save sum
sub x0,x0,x5 // new sum to find
add x4,x4,#1 // next divisors
bl searchHeap // other search
cmp x0,#0 // find -> ok
beq 5f
mov x0,x8 // sum begin
sub x4,x4,#1 // prev divisors
bl razFlags // zero in all flags > current element
4:
add x4,x4,#1 // last divisors b 1b
5:
str x1,[x6,#div_flag] // flag -> area element flag b 100f
6:
add x4,x4,#1 // last divisors b 1b
7:
str x1,[x6,#div_flag] // flag -> area element flag mov x0,#0 // search ok b 100f
8:
mov x0,#-1 // end search b 100f
99:
mov x0,#-2 b 100f
100:
ldp x6,x8,[sp],16 // restaur 2 registers ldp x4,x5,[sp],16 // restaur 2 registers ldp x3,lr,[sp],16 // restaur 2 registers ret // return to address lr x30
/******************************************************************/ /* raz flags */ /******************************************************************/ /* x0 contains sum to search */ /* x1 contains flag (1 or 2) */ /* x2 contains address of divisors area */ /* x3 contains elements number */ /* x4 contains N° element to start */ /* x5 contains current sum */ /* REMARK : NO SAVE REGISTERS x14 x15 x16 AND LR */ razFlags:
mov x14,x4
1:
cmp x14,x3 // indice > nb elements ? bge 100f // yes -> end lsl x15,x14,#4 add x15,x15,x2 // compute address element ldr x16,[x15,#div_flag] // load flag cmp x1,x16 // equal ? bne 2f str xzr,[x15,#div_flag] // yes -> store 0
2:
add x14,x14,#1 // increment indice b 1b // and loop
100:
ret // return to address lr x30
/******************************************************************/ /* compute sum of divisors */ /******************************************************************/ /* x0 contains elements number */ /* x1 contains flag (0 1 or 2) /* x2 contains address of divisors area /* x0 return divisors sum */ /* REMARK : NO SAVE REGISTERS x13 x14 x15 x16 AND LR */ sumDivisors:
mov x13,#0 // indice mov x16,#0 // sum
1:
lsl x14,x13,#4 // N° element * 16 add x14,x14,x2 ldr x15,[x14,#div_flag] // compare flag cmp x15,x1 bne 2f ldr x15,[x14,#div_ident] // load value add x16,x16,x15 // and add
2:
add x13,x13,#1 cmp x13,x0 blt 1b mov x0,x16 // return sum
100:
ret // return to address lr x30
/******************************************************************/ /* print heap */ /******************************************************************/ /* x0 contains elements number */ /* x1 contains flag (0 1 or 2) */ /* x2 contains address of divisors area */ printHeap:
stp x2,lr,[sp,-16]! // save registers stp x3,x4,[sp,-16]! // save registers stp x5,x6,[sp,-16]! // save registers stp x1,x7,[sp,-16]! // save registers mov x6,x0 mov x5,x1 mov x3,#0 // indice
1:
lsl x1,x3,#4 // N° element * 16 add x1,x1,x2 ldr x4,[x1,#div_flag] cmp x4,x5 bne 2f ldr x0,[x1,#div_ident] ldr x1,qAdrsValue // and convert ascii string bl conversion10 ldr x0,qAdrszMessResult // display result message bl affichageMess
2:
add x3,x3,#1 cmp x3,x6 blt 1b ldr x0,qAdrszCarriageReturn bl affichageMess
100:
ldp x1,x8,[sp],16 // restaur 2 registers ldp x5,x6,[sp],16 // restaur 2 registers ldp x3,x4,[sp],16 // restaur 2 registers ldp x2,lr,[sp],16 // restaur 2 registers ret // return to address lr x30
/******************************************************************/ /* divisors function */ /******************************************************************/ /* x0 contains the number */ /* x1 contains address of divisors area /* x0 return divisors number */ /* x1 return counter odd divisors */ /* REMARK : NO SAVE REGISTERS x10 x11 x12 x13 x14 x15 x16 x17 x18 */ divisors:
str lr,[sp,-16]! // save register LR cmp x0,#1 // = 1 ? ble 98f mov x17,x0 mov x18,x1 mov x11,#1 // counter odd divisors mov x0,#1 // first divisor = 1 str x0,[x18,#div_ident] mov x0,#0 str x0,[x18,#div_flag] tst x17,#1 // number is odd ? cinc x11,x11,ne // count odd divisors mov x0,x17 // last divisor = N add x10,x18,#16 // store at next element str x0,[x10,#div_ident] mov x0,#0 str x0,[x10,#div_flag]
mov x16,#2 // first divisor mov x15,#2 // Counter divisors
2: // begin loop
udiv x12,x17,x16 msub x13,x12,x16,x17 cmp x13,#0 // remainder = 0 ? bne 3f cmp x12,x16 blt 4f // quot<divisor end lsl x10,x15,#4 // N° element * 16 add x10,x10,x18 // and add at area begin address str x12,[x10,#div_ident] str xzr,[x10,#div_flag] add x15,x15,#1 // increment counter cmp x15,#NBDIVISORS // area maxi ? bge 99f tst x12,#1 cinc x11,x11,ne // count odd divisors cmp x12,x16 // quotient = divisor ? ble 4f lsl x10,x15,#4 // N° element * 16 add x10,x10,x18 // and add at area begin address str x16,[x10,#div_ident] str xzr,[x10,#div_flag] add x15,x15,#1 // increment counter cmp x15,#NBDIVISORS // area maxi ? bge 99f tst x16,#1 cinc x11,x11,ne // count odd divisors
3:
cmp x12,x16 ble 4f add x16,x16,#1 // increment divisor b 2b // and loop
4:
mov x0,x15 // return divisors number mov x1,x11 // return count odd divisors b 100f
98:
mov x0,0 b 100f
99: // error
ldr x0,qAdrszMessErrorArea bl affichageMess mov x0,-1
100:
ldr lr,[sp],16 // restaur 1 registers ret // return to address lr x30
qAdrszMessListDivi: .quad szMessListDivi qAdrszMessErrorArea: .quad szMessErrorArea /********************************************************/ /* File Include fonctions */ /********************************************************/ /* for this file see task include a file in language AArch64 assembly */ .include "../includeARM64.inc" </lang> Template:Output:
Program start The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 Program normal end.
AppleScript
This takes about 0.38 seconds to execute the two main searches — then a further 109 for the stretch goal!
<lang applescript>on properDivisors(n)
set output to {}
if (n > 1) then
set sqrt to n ^ 0.5
set limit to sqrt div 1
if (limit = sqrt) then
set end of output to limit
set limit to limit - 1
end if
repeat with i from limit to 2 by -1
if (n mod i is 0) then
set beginning of output to i
set end of output to n div i
end if
end repeat
set beginning of output to 1
end if
return output
end properDivisors
on canSumTo(lst, target)
script o
property l : lst
on cst(target, i)
repeat
set n to item i of my l
if (n = target) then return true
if (i = 1) then return false
set i to i - 1
if ((n < target) and (cst(target - n, i))) then return true
end repeat
end cs
end script
return o's cst(target, count o's l)
end canSumTo
on isZumkeller(n)
script o
property divisors : properDivisors(n)
end script
set sum to n
repeat with thisDivisor in o's divisors
set sum to sum + thisDivisor
end repeat
set halfSum to sum / 2
return ((halfSum ≥ n) and (halfSum as integer = halfSum) and (canSumTo(o's divisors, halfSum)))
end isZumkeller
-- Task code: on zumkellerNumbers(target, n, interval, filter)
-- Params: how many required, first number to test, interval between numbers tested,
-- script object imposing any further restrictions on the numbers.
script o
property zumkellers : {}
end script
set counter to 0
repeat until (counter = target)
if ((filter's OK(n)) and (isZumkeller(n))) then
set end of o's zumkellers to n
set counter to counter + 1
end if
set n to n + interval
end repeat
return o's zumkellers
end zumkellerNumbers
on format(resultList, heading, resultsPerLine, separator)
script o
property input : resultList
property output : {heading}
end script
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to separator
set len to (count o's input)
repeat with i from 1 to len by resultsPerLine
set j to i + resultsPerLine - 1
if (j > len) then set j to len
set end of o's output to (items i thru j of o's input) as text
end repeat
set AppleScript's text item delimiters to linefeed
set output to o's output as text
set AppleScript's text item delimiters to astid
return output
end format
on doTask()
set output to {}
script default
on OK(n)
return true
end OK
end script
set header to "1st 220 Zumkeller numbers:"
set end of output to format(zumkellerNumbers(220, 1, 1, default), header, 20, " ")
set header to "1st 40 odd Zumkeller numbers:"
set end of output to format(zumkellerNumbers(40, 1, 2, default), header, 10, " ")
set header to "1st 40 odd Zumkeller numbers not ending with 5:"
script notDivisibleBy5
on OK(n)
return (n mod 5 > 0)
end OK
end script
set end of output to format(zumkellerNumbers(40, 1, 2, notDivisibleBy5), header, 10, " ")
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to linefeed & linefeed
set output to output as text
set AppleScript's text item delimiters to astid
return output
end doTask
doTask()</lang>
- Output:
<lang applescript>"1st 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984
1st 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
1st 40 odd Zumkeller numbers not ending with 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377"</lang>
ARM Assembly
<lang ARM Assembly> /* ARM assembly Raspberry PI */ /* program zumkeller4.s */ /* new version 10/2020 */
/* REMARK 1 : this program use routines in a include file see task Include a file language arm assembly for the routine affichageMess conversion10 see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */ /************************************/ /* Constantes */ /************************************/ .include "../constantes.inc"
.equ NBDIVISORS, 1000
/*******************************************/ /* Initialized data */ /*******************************************/ .data szMessStartPgm: .asciz "Program start \n" szMessEndPgm: .asciz "Program normal end.\n" szMessErrorArea: .asciz "\033[31mError : area divisors too small.\n" szMessError: .asciz "\033[31mError !!!\n" szMessErrGen: .asciz "Error end program.\n" szMessNbPrem: .asciz "This number is prime !!!.\n" szMessResultFact: .asciz "@ "
szCarriageReturn: .asciz "\n"
/* datas message display */ szMessEntete: .asciz "The first 220 Zumkeller numbers are:\n" sNumber: .space 4*20,' '
.space 12,' ' @ for end of conversion
szMessListDivi: .asciz "Divisors list : \n" szMessListDiviHeap: .asciz "Heap 1 Divisors list : \n" szMessResult: .ascii " " sValue: .space 12,' '
.asciz ""
szMessEntete1: .asciz "The first 40 odd Zumkeller numbers are:\n" szMessEntete2: .asciz "First 40 odd Zumkeller numbers not divisible by 5:\n" /*******************************************/ /* UnInitialized data */ /*******************************************/ .bss .align 4 sZoneConv: .skip 24 tbZoneDecom: .skip 8 * NBDIVISORS // facteur 4 octets, nombre 4 /*******************************************/ /* code section */ /*******************************************/ .text .global main main: @ program start
ldr r0,iAdrszMessStartPgm @ display start message bl affichageMess
ldr r0,iAdrszMessEntete @ display result message bl affichageMess mov r2,#1 mov r3,#0 mov r4,#0
1:
mov r0,r2 @ number bl testZumkeller cmp r0,#1 bne 3f mov r0,r2 ldr r1,iAdrsNumber @ and convert ascii string lsl r5,r4,#2 add r1,r5 bl conversion10 add r4,r4,#1 cmp r4,#20 blt 2f add r1,r1,#3 mov r0,#'\n' strb r0,[r1] mov r0,#0 strb r0,[r1,#1] ldr r0,iAdrsNumber @ display result message bl affichageMess mov r4,#0
2:
add r3,r3,#1
3:
add r2,r2,#1 cmp r3,#220 blt 1b
/* odd zumkeller numbers */ ldr r0,iAdrszMessEntete1 bl affichageMess mov r2,#1 mov r3,#0 mov r4,#0
4:
mov r0,r2 @ number bl testZumkeller cmp r0,#1 bne 6f mov r0,r2 ldr r1,iAdrsNumber @ and convert ascii string lsl r5,r4,#3 add r1,r5 bl conversion10 add r4,r4,#1 cmp r4,#8 blt 5f add r1,r1,#8 mov r0,#'\n' strb r0,[r1] mov r0,#0 strb r0,[r1,#1] ldr r0,iAdrsNumber @ display result message bl affichageMess mov r4,#0
5:
add r3,r3,#1
6:
add r2,r2,#2 cmp r3,#40 blt 4b /* odd zumkeller numbers not multiple5 */
61:
ldr r0,iAdrszMessEntete2 bl affichageMess mov r3,#0 mov r4,#0
7:
lsr r8,r2,#3 @ divide counter by 5 add r8,r8,r2,lsr #4 add r8,r8,r8,lsr #4 add r8,r8,r8,lsr #8 add r8,r8,r8,lsr #16 add r9,r8,r8,lsl #2 @ multiply result by 5 sub r9,r2,r9 mov r6,#13 mul r9,r6,r9 lsr r9,#6 add r9,r8 @ it is a quotient add r9,r9,r9,lsl #2 @ multiply by 5 sub r9,r2,r9 @ compute remainder cmp r9,#0 @ remainder = zero ? beq 9f mov r0,r2 @ number bl testZumkeller cmp r0,#1 bne 9f mov r0,r2 ldr r1,iAdrsNumber @ and convert ascii string lsl r5,r4,#3 add r1,r5 bl conversion10 add r4,r4,#1 cmp r4,#8 blt 8f add r1,r1,#8 mov r0,#'\n' strb r0,[r1] mov r0,#0 strb r0,[r1,#1] ldr r0,iAdrsNumber @ display result message bl affichageMess mov r4,#0
8:
add r3,r3,#1
9:
add r2,r2,#2 cmp r3,#40 blt 7b
ldr r0,iAdrszMessEndPgm @ display end message bl affichageMess b 100f
99: @ display error message
ldr r0,iAdrszMessError bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code mov r7, #EXIT @ request to exit program svc 0 @ perform system call
iAdrszMessStartPgm: .int szMessStartPgm iAdrszMessEndPgm: .int szMessEndPgm iAdrszMessError: .int szMessError iAdrszCarriageReturn: .int szCarriageReturn iAdrszMessResult: .int szMessResult iAdrsValue: .int sValue iAdrtbZoneDecom: .int tbZoneDecom iAdrszMessEntete: .int szMessEntete iAdrszMessEntete1: .int szMessEntete1 iAdrszMessEntete2: .int szMessEntete2 iAdrsNumber: .int sNumber
/******************************************************************/ /* test if number is Zumkeller number */ /******************************************************************/ /* r0 contains the number */ /* r0 return 1 if Zumkeller number else return 0 */ testZumkeller:
push {r1-r6,lr} @ save registers
mov r6,r0 @ save number
ldr r1,iAdrtbZoneDecom
bl decompFact @ create area of divisors
cmp r0,#1 @ no divisors
movle r0,#0
ble 100f
tst r2,#1 @ odd sum ?
movne r0,#0
bne 100f @ yes -> end
tst r1,#1 @ number of odd divisors is odd ?
movne r0,#0
bne 100f @ yes -> end
lsl r5,r6,#1 @ abondant number
cmp r5,r2
movgt r0,#0
bgt 100f @ no -> end
mov r3,r0
mov r4,r2 @ save sum
ldr r0,iAdrtbZoneDecom
mov r1,#0
mov r2,r3
bl shellSort @ sort table
mov r1,r3 @ factors number
ldr r0,iAdrtbZoneDecom
lsr r2,r4,#1 @ sum / 2
bl computePartIter @
100:
pop {r1-r6,lr} @ restaur registers
bx lr @ return
/******************************************************************/ /* search factors to sum = entry value */ /******************************************************************/ /* r0 contains address of divisors area */ /* r1 contains elements number */ /* r2 contains divisors sum / 2 */ /* r0 return 1 if ok 0 else */ computePartIter:
push {r1-r7,fp,lr} @ save registers
lsl r7,r1,#3 @ compute size of temp table
sub sp,r7 @ and reserve on stack
mov fp,sp @ frame pointer = stack address = begin table
mov r5,#0 @ stack indice
sub r3,r1,#1
1:
ldr r4,[r0,r3,lsl #2] @ load factor cmp r4,r2 @ compare value bgt 2f beq 90f @ equal -> end ok cmp r3,#0 @ first item ? beq 3f sub r3,#1 @ push indice item in temp table add r6,fp,r5,lsl #3 str r3,[r6] str r2,[r6,#4] @ push sum in temp table add r5,#1 sub r2,r4 @ substract divisors from sum b 1b
2:
sub r3,#1 @ other divisors cmp r3,#0 @ first item ? bge 1b
3: @ first item
cmp r5,#0 @ stack empty ? moveq r0,#0 @ no sum factors equal to value beq 100f @ end sub r5,#1 @ else pop stack add r6,fp,r5,lsl #3 @ and restaur ldr r3,[r6] @ indice ldr r2,[r6,#4] @ and value b 1b @ and loop
90:
mov r0,#1 @ it is ok
100:
add sp,r7 @ stack alignement
pop {r1-r7,fp,lr} @ restaur registers
bx lr @ return
/******************************************************************/ /* factor decomposition */ /******************************************************************/ /* r0 contains number */ /* r1 contains address of divisors area */ /* r0 return divisors items in table */ /* r1 return the number of odd divisors */ /* r2 return the sum of divisors */ decompFact:
push {r3-r8,lr} @ save registers
mov r5,r1
mov r8,r0 @ save number
bl isPrime @ prime ?
cmp r0,#1
beq 98f @ yes is prime
mov r1,#1
str r1,[r5] @ first factor
mov r12,#1 @ divisors sum
mov r11,#1 @ number odd divisors
mov r4,#1 @ indice divisors table
mov r1,#2 @ first divisor
mov r6,#0 @ previous divisor
mov r7,#0 @ number of same divisors
2:
mov r0,r8 @ dividende bl division @ r1 divisor r2 quotient r3 remainder cmp r3,#0 bne 5f @ if remainder <> zero -> no divisor mov r8,r2 @ else quotient -> new dividende cmp r1,r6 @ same divisor ? beq 4f @ yes mov r7,r4 @ number factors in table mov r9,#0 @ indice
21:
ldr r10,[r5,r9,lsl #2 ] @ load one factor mul r10,r1,r10 @ multiply str r10,[r5,r7,lsl #2] @ and store in the table tst r10,#1 @ divisor odd ? addne r11,#1 add r12,r10 add r7,r7,#1 @ and increment counter add r9,r9,#1 cmp r9,r4 blt 21b mov r4,r7 mov r6,r1 @ new divisor b 7f
4: @ same divisor
sub r9,r4,#1 mov r7,r4
41:
ldr r10,[r5,r9,lsl #2 ] cmp r10,r1 subne r9,#1 bne 41b sub r9,r4,r9
42:
ldr r10,[r5,r9,lsl #2 ] mul r10,r1,r10 str r10,[r5,r7,lsl #2] @ and store in the table tst r10,#1 @ divsor odd ? addne r11,#1 add r12,r10 add r7,r7,#1 @ and increment counter add r9,r9,#1 cmp r9,r4 blt 42b mov r4,r7 b 7f @ and loop /* not divisor -> increment next divisor */
5:
cmp r1,#2 @ if divisor = 2 -> add 1 addeq r1,#1 addne r1,#2 @ else add 2 b 2b /* divisor -> test if new dividende is prime */
7:
mov r3,r1 @ save divisor cmp r8,#1 @ dividende = 1 ? -> end beq 10f mov r0,r8 @ new dividende is prime ? mov r1,#0 bl isPrime @ the new dividende is prime ? cmp r0,#1 bne 10f @ the new dividende is not prime
cmp r8,r6 @ else dividende is same divisor ? beq 9f @ yes mov r7,r4 @ number factors in table mov r9,#0 @ indice
71:
ldr r10,[r5,r9,lsl #2 ] @ load one factor mul r10,r8,r10 @ multiply str r10,[r5,r7,lsl #2] @ and store in the table tst r10,#1 @ divsor odd ? addne r11,#1 add r12,r10 add r7,r7,#1 @ and increment counter add r9,r9,#1 cmp r9,r4 blt 71b mov r4,r7 mov r7,#0 b 11f
9:
sub r9,r4,#1 mov r7,r4
91:
ldr r10,[r5,r9,lsl #2 ] cmp r10,r8 subne r9,#1 bne 91b sub r9,r4,r9
92:
ldr r10,[r5,r9,lsl #2 ] mul r10,r8,r10 str r10,[r5,r7,lsl #2] @ and store in the table tst r10,#1 @ divisor odd ? addne r11,#1 add r12,r10 add r7,r7,#1 @ and increment counter add r9,r9,#1 cmp r9,r4 blt 92b mov r4,r7 b 11f
10:
mov r1,r3 @ current divisor = new divisor cmp r1,r8 @ current divisor > new dividende ? ble 2b @ no -> loop /* end decomposition */
11:
mov r0,r4 @ return number of table items mov r2,r12 @ return sum mov r1,r11 @ return number of odd divisor mov r3,#0 str r3,[r5,r4,lsl #2] @ store zéro in last table item b 100f
98:
//ldr r0,iAdrszMessNbPrem //bl affichageMess mov r0,#1 @ return code b 100f
99:
ldr r0,iAdrszMessError bl affichageMess mov r0,#-1 @ error code b 100f
100:
pop {r3-r8,lr} @ restaur registers
bx lr
iAdrszMessNbPrem: .int szMessNbPrem /***************************************************/ /* check if a number is prime */ /***************************************************/ /* r0 contains the number */ /* r0 return 1 if prime 0 else */ @2147483647 @4294967297 @131071 isPrime:
push {r1-r6,lr} @ save registers
cmp r0,#0
beq 90f
cmp r0,#17
bhi 1f
cmp r0,#3
bls 80f @ for 1,2,3 return prime
cmp r0,#5
beq 80f @ for 5 return prime
cmp r0,#7
beq 80f @ for 7 return prime
cmp r0,#11
beq 80f @ for 11 return prime
cmp r0,#13
beq 80f @ for 13 return prime
cmp r0,#17
beq 80f @ for 17 return prime
1:
tst r0,#1 @ even ? beq 90f @ yes -> not prime mov r2,r0 @ save number sub r1,r0,#1 @ exposant n - 1 mov r0,#3 @ base bl moduloPuR32 @ compute base power n - 1 modulo n cmp r0,#1 bne 90f @ if <> 1 -> not prime mov r0,#5 bl moduloPuR32 cmp r0,#1 bne 90f mov r0,#7 bl moduloPuR32 cmp r0,#1 bne 90f mov r0,#11 bl moduloPuR32 cmp r0,#1 bne 90f mov r0,#13 bl moduloPuR32 cmp r0,#1 bne 90f mov r0,#17 bl moduloPuR32 cmp r0,#1 bne 90f
80:
mov r0,#1 @ is prime b 100f
90:
mov r0,#0 @ no prime
100: @ fin standard de la fonction
pop {r1-r6,lr} @ restaur des registres
bx lr @ retour de la fonction en utilisant lr
/********************************************************/ /* Calcul modulo de b puissance e modulo m */ /* Exemple 4 puissance 13 modulo 497 = 445 */ /* */ /********************************************************/ /* r0 nombre */ /* r1 exposant */ /* r2 modulo */ /* r0 return result */ moduloPuR32:
push {r1-r7,lr} @ save registers
cmp r0,#0 @ verif <> zero
beq 100f
cmp r2,#0 @ verif <> zero
beq 100f @ TODO: vérifier les cas d erreur
1:
mov r4,r2 @ save modulo mov r5,r1 @ save exposant mov r6,r0 @ save base mov r3,#1 @ start result
mov r1,#0 @ division de r0,r1 par r2 bl division32R mov r6,r2 @ base <- remainder
2:
tst r5,#1 @ exposant even or odd beq 3f umull r0,r1,r6,r3 mov r2,r4 bl division32R mov r3,r2 @ result <- remainder
3:
umull r0,r1,r6,r6 mov r2,r4 bl division32R mov r6,r2 @ base <- remainder
lsr r5,#1 @ left shift 1 bit cmp r5,#0 @ end ? bne 2b mov r0,r3
100: @ fin standard de la fonction
pop {r1-r7,lr} @ restaur des registres
bx lr @ retour de la fonction en utilisant lr
/***************************************************/ /* division number 64 bits in 2 registers by number 32 bits */ /***************************************************/ /* r0 contains lower part dividende */ /* r1 contains upper part dividende */ /* r2 contains divisor */ /* r0 return lower part quotient */ /* r1 return upper part quotient */ /* r2 return remainder */ division32R:
push {r3-r9,lr} @ save registers
mov r6,#0 @ init upper upper part remainder !!
mov r7,r1 @ init upper part remainder with upper part dividende
mov r8,r0 @ init lower part remainder with lower part dividende
mov r9,#0 @ upper part quotient
mov r4,#0 @ lower part quotient
mov r5,#32 @ bits number
1: @ begin loop
lsl r6,#1 @ shift upper upper part remainder
lsls r7,#1 @ shift upper part remainder
orrcs r6,#1
lsls r8,#1 @ shift lower part remainder
orrcs r7,#1
lsls r4,#1 @ shift lower part quotient
lsl r9,#1 @ shift upper part quotient
orrcs r9,#1
@ divisor sustract upper part remainder
subs r7,r2
sbcs r6,#0 @ and substract carry
bmi 2f @ négative ?
@ positive or equal
orr r4,#1 @ 1 -> right bit quotient
b 3f
2: @ negative
orr r4,#0 @ 0 -> right bit quotient adds r7,r2 @ and restaur remainder adc r6,#0
3:
subs r5,#1 @ decrement bit size bgt 1b @ end ? mov r0,r4 @ lower part quotient mov r1,r9 @ upper part quotient mov r2,r7 @ remainder
100: @ function end
pop {r3-r9,lr} @ restaur registers
bx lr
/***************************************************/ /* shell Sort */ /***************************************************/
/* r0 contains the address of table */ /* r1 contains the first element but not use !! */ /* this routine use first element at index zero !!! */ /* r2 contains the number of element */ shellSort:
push {r0-r7,lr} @save registers
sub r2,#1 @ index last item
mov r1,r2 @ init gap = last item
1: @ start loop 1
lsrs r1,#1 @ gap = gap / 2 beq 100f @ if gap = 0 -> end mov r3,r1 @ init loop indice 1
2: @ start loop 2
ldr r4,[r0,r3,lsl #2] @ load first value mov r5,r3 @ init loop indice 2
3: @ start loop 3
cmp r5,r1 @ indice < gap blt 4f @ yes -> end loop 2 sub r6,r5,r1 @ index = indice - gap ldr r7,[r0,r6,lsl #2] @ load second value cmp r4,r7 @ compare values strlt r7,[r0,r5,lsl #2] @ store if < sublt r5,r1 @ indice = indice - gap blt 3b @ and loop
4: @ end loop 3
str r4,[r0,r5,lsl #2] @ store value 1 at indice 2 add r3,#1 @ increment indice 1 cmp r3,r2 @ end ? ble 2b @ no -> loop 2 b 1b @ yes loop for new gap
100: @ end function
pop {r0-r7,lr} @ restaur registers
bx lr @ return
/******************************************************************/ /* display divisors function */ /******************************************************************/ /* r0 contains address of divisors area */ /* r1 contains the number of area items */ displayDivisors:
push {r2-r8,lr} @ save registers
cmp r1,#0
beq 100f
mov r2,r1
mov r3,#0 @ indice
mov r4,r0
1:
add r5,r4,r3,lsl #2 ldr r0,[r5] @ load factor
ldr r1,iAdrsZoneConv bl conversion10 @ call décimal conversion ldr r0,iAdrszMessResultFact ldr r1,iAdrsZoneConv @ insert conversion in message bl strInsertAtCharInc bl affichageMess @ display message add r3,#1 @ other ithem cmp r3,r2 @ items maxi ? blt 1b ldr r0,iAdrszCarriageReturn bl affichageMess b 100f
100:
pop {r2-r8,lr} @ restaur registers
bx lr @ return
iAdrszMessResultFact: .int szMessResultFact iAdrsZoneConv: .int sZoneConv /***************************************************/ /* ROUTINES INCLUDE */ /***************************************************/ .include "../affichage.inc" </lang>
Program start The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers not divisible by 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377 Program normal end.
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
namespace ZumkellerNumbers {
class Program {
static List<int> GetDivisors(int n) {
List<int> divs = new List<int> {
1, n
};
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
int j = n / i;
divs.Add(i);
if (i != j) {
divs.Add(j);
}
}
}
return divs;
}
static bool IsPartSum(List<int> divs, int sum) {
if (sum == 0) {
return true;
}
var le = divs.Count;
if (le == 0) {
return false;
}
var last = divs[le - 1];
List<int> newDivs = new List<int>();
for (int i = 0; i < le - 1; i++) {
newDivs.Add(divs[i]);
}
if (last > sum) {
return IsPartSum(newDivs, sum);
}
return IsPartSum(newDivs, sum) || IsPartSum(newDivs, sum - last);
}
static bool IsZumkeller(int n) {
var divs = GetDivisors(n);
var sum = divs.Sum();
// if sum is odd can't be split into two partitions with equal sums
if (sum % 2 == 1) {
return false;
}
// if n is odd use 'abundant odd number' optimization
if (n % 2 == 1) {
var abundance = sum - 2 * n;
return abundance > 0 && abundance % 2 == 0;
}
// if n and sum are both even check if there's a partition which totals sum / 2
return IsPartSum(divs, sum / 2);
}
static void Main() {
Console.WriteLine("The first 220 Zumkeller numbers are:");
int i = 2;
for (int count = 0; count < 220; i++) {
if (IsZumkeller(i)) {
Console.Write("{0,3} ", i);
count++;
if (count % 20 == 0) {
Console.WriteLine();
}
}
}
Console.WriteLine("\nThe first 40 odd Zumkeller numbers are:");
i = 3;
for (int count = 0; count < 40; i += 2) {
if (IsZumkeller(i)) {
Console.Write("{0,5} ", i);
count++;
if (count % 10 == 0) {
Console.WriteLine();
}
}
}
Console.WriteLine("\nThe first 40 odd Zumkeller numbers which don't end in 5 are:");
i = 3;
for (int count = 0; count < 40; i += 2) {
if (i % 10 != 5 && IsZumkeller(i)) {
Console.Write("{0,7} ", i);
count++;
if (count % 8 == 0) {
Console.WriteLine();
}
}
}
}
}
}</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
C++
<lang cpp>#include <iostream>
- include <cmath>
- include <vector>
- include <algorithm>
- include <iomanip>
- include <numeric>
using namespace std;
// Returns n in binary right justified with length passed and padded with zeroes const uint* binary(uint n, uint length);
// Returns the sum of the binary ordered subset of rank r. // Adapted from Sympy implementation. uint sum_subset_unrank_bin(const vector<uint>& d, uint r);
vector<uint> factors(uint x);
bool isPrime(uint number);
bool isZum(uint n);
ostream& operator<<(ostream& os, const vector<uint>& zumz) {
for (uint i = 0; i < zumz.size(); i++) {
if (i % 10 == 0)
os << endl;
os << setw(10) << zumz[i] << ' ';
}
return os;
}
int main() {
cout << "First 220 Zumkeller numbers:" << endl;
vector<uint> zumz;
for (uint n = 2; zumz.size() < 220; n++)
if (isZum(n))
zumz.push_back(n);
cout << zumz << endl << endl;
cout << "First 40 odd Zumkeller numbers:" << endl;
vector<uint> zumz2;
for (uint n = 2; zumz2.size() < 40; n++)
if (n % 2 && isZum(n))
zumz2.push_back(n);
cout << zumz2 << endl << endl;
cout << "First 40 odd Zumkeller numbers not ending in 5:" << endl;
vector<uint> zumz3;
for (uint n = 2; zumz3.size() < 40; n++)
if (n % 2 && (n % 10) != 5 && isZum(n))
zumz3.push_back(n);
cout << zumz3 << endl << endl;
return 0;
}
// Returns n in binary right justified with length passed and padded with zeroes const uint* binary(uint n, uint length) {
uint* bin = new uint[length]; // array to hold result
fill(bin, bin + length, 0); // fill with zeroes
// convert n to binary and store right justified in bin
for (uint i = 0; n > 0; i++) {
uint rem = n % 2;
n /= 2;
if (rem)
bin[length - 1 - i] = 1;
}
return bin;
}
// Returns the sum of the binary ordered subset of rank r. // Adapted from Sympy implementation. uint sum_subset_unrank_bin(const vector<uint>& d, uint r) {
vector<uint> subset; // convert r to binary array of same size as d const uint* bits = binary(r, d.size() - 1);
// get binary ordered subset
for (uint i = 0; i < d.size() - 1; i++)
if (bits[i])
subset.push_back(d[i]);
delete[] bits;
return accumulate(subset.begin(), subset.end(), 0u);
}
vector<uint> factors(uint x) {
vector<uint> result;
// this will loop from 1 to int(sqrt(x))
for (uint i = 1; i * i <= x; i++) {
// Check if i divides x without leaving a remainder
if (x % i == 0) {
result.push_back(i);
if (x / i != i)
result.push_back(x / i);
}
}
// return the sorted factors of x sort(result.begin(), result.end()); return result;
}
bool isPrime(uint number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (uint i = 3; i * i <= number; i += 2)
if (number % i == 0) return false;
return true;
}
bool isZum(uint n) {
// if prime it ain't no zum
if (isPrime(n))
return false;
// get sum of divisors const auto d = factors(n); uint s = accumulate(d.begin(), d.end(), 0u);
// if sum is odd or sum < 2*n it ain't no zum
if (s % 2 || s < 2 * n)
return false;
// if we get here and n is odd or n has at least 24 divisors it's a zum!
// Valid for even n < 99504. To test n beyond this bound, comment out this condition.
// And wait all day. Thanks to User:Horsth for taking the time to find this bound!
if (n % 2 || d.size() >= 24)
return true;
if (!(s % 2) && d[d.size() - 1] <= s / 2)
for (uint x = 2; (uint) log2(x) < (d.size() - 1); x++) // using log2 prevents overflow
if (sum_subset_unrank_bin(d, x) == s / 2)
return true; // congratulations it's a zum num!!
// if we get here it ain't no zum return false;
}</lang>
- Output:
First 220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54
56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140
150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240
246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336
340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416
420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498
500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580
582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666
672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756
760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852
858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940
942 945 948 952 960 966 972 978 980 984
First 40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
First 40 odd Zumkeller numbers not ending in 5:
81081 153153 171171 189189 207207 223839 243243 261261 279279 297297
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
D
<lang d>import std.algorithm; import std.stdio;
int[] getDivisors(int n) {
auto divs = [1, n];
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
divs ~= i;
int j = n / i;
if (i != j) {
divs ~= j;
}
}
}
return divs;
}
bool isPartSum(int[] divs, int sum) {
if (sum == 0) {
return true;
}
auto le = divs.length;
if (le == 0) {
return false;
}
auto last = divs[$ - 1];
int[] newDivs;
for (int i = 0; i < le - 1; i++) {
newDivs ~= divs[i];
}
if (last > sum) {
return isPartSum(newDivs, sum);
} else {
return isPartSum(newDivs, sum) || isPartSum(newDivs, sum - last);
}
}
bool isZumkeller(int n) {
auto divs = getDivisors(n);
auto sum = divs.sum();
// if sum is odd can't be split into two partitions with equal sums
if (sum % 2 == 1) {
return false;
}
// if n is odd use 'abundant odd number' optimization
if (n % 2 == 1) {
auto abundance = sum - 2 * n;
return abundance > 0 && abundance % 2 == 0;
}
// if n and sum are both even check if there's a partition which totals sum / 2
return isPartSum(divs, sum / 2);
}
void main() {
writeln("The first 220 Zumkeller numbers are:");
int i = 2;
for (int count = 0; count < 220; i++) {
if (isZumkeller(i)) {
writef("%3d ", i);
count++;
if (count % 20 == 0) {
writeln;
}
}
}
writeln("\nThe first 40 odd Zumkeller numbers are:");
i = 3;
for (int count = 0; count < 40; i += 2) {
if (isZumkeller(i)) {
writef("%5d ", i);
count++;
if (count % 10 == 0) {
writeln;
}
}
}
writeln("\nThe first 40 odd Zumkeller numbers which don't end in 5 are:");
i = 3;
for (int count = 0; count < 40; i += 2) {
if (i % 10 != 5 && isZumkeller(i)) {
writef("%7d ", i);
count++;
if (count % 8 == 0) {
writeln;
}
}
}
}</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
F#
This task uses [1] <lang fsharp> // Zumkeller numbers: Nigel Galloway. May 16th., 2021 let rec fG n g=match g with h::_ when h>=n->h=n |h::t->fG n t || fG(n-h) t |_->false let fN g=function n when n&&&1=1->false
|n->let e=n/2-g in match compare e 0 with 0->true
|1->let l=[1..e]|>List.filter(fun n->g%n=0)
match compare(l|>List.sum) e with 1->fG e l |0->true |_->false
|_->false
Seq.initInfinite((+)1)|>Seq.map(fun n->(n,sod n))|>Seq.filter(fun(n,g)->fN n g)|>Seq.take 220|>Seq.iter(fun(n,_)->printf "%d " n); printfn "\n" Seq.initInfinite((*)2>>(+)1)|>Seq.map(fun n->(n,sod n))|>Seq.filter(fun(n,g)->fN n g)|>Seq.take 40|>Seq.iter(fun(n,_)->printf "%d " n); printfn "\n" Seq.initInfinite((*)2>>(+)1)|>Seq.filter(fun n->n%10<>5)|>Seq.map(fun n->(n,sod n))|>Seq.filter(fun(n,g)->fN n g)|>Seq.take 40|>Seq.iter(fun(n,_)->printf "%d " n); printfn "\n" </lang>
- Output:
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Factor
<lang factor>USING: combinators grouping io kernel lists lists.lazy math math.primes.factors memoize prettyprint sequences ;
MEMO: psum? ( seq n -- ? )
{
{ [ dup zero? ] [ 2drop t ] }
{ [ over length zero? ] [ 2drop f ] }
{ [ over last over > ] [ [ but-last ] dip psum? ] }
[
[ [ but-last ] dip psum? ]
[ over last - [ but-last ] dip psum? ] 2bi or
]
} cond ;
- zumkeller? ( n -- ? )
dup divisors dup sum
{
{ [ dup odd? ] [ 3drop f ] }
{ [ pick odd? ] [ nip swap 2 * - [ 0 > ] [ even? ] bi and ] }
[ nipd 2/ psum? ]
} cond ;
- zumkellers ( -- list )
1 lfrom [ zumkeller? ] lfilter ;
- odd-zumkellers ( -- list )
1 [ 2 + ] lfrom-by [ zumkeller? ] lfilter ;
- odd-zumkellers-no-5 ( -- list )
odd-zumkellers [ 5 mod zero? not ] lfilter ;
- show ( count list row-len -- )
[ ltake list>array ] dip group simple-table. nl ;
"First 220 Zumkeller numbers:" print 220 zumkellers 20 show
"First 40 odd Zumkeller numbers:" print 40 odd-zumkellers 10 show
"First 40 odd Zumkeller numbers not ending with 5:" print 40 odd-zumkellers-no-5 8 show</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers not ending with 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Go
<lang go>package main
import "fmt"
func getDivisors(n int) []int {
divs := []int{1, n}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
j := n / i
divs = append(divs, i)
if i != j {
divs = append(divs, j)
}
}
}
return divs
}
func sum(divs []int) int {
sum := 0
for _, div := range divs {
sum += div
}
return sum
}
func isPartSum(divs []int, sum int) bool {
if sum == 0 {
return true
}
le := len(divs)
if le == 0 {
return false
}
last := divs[le-1]
divs = divs[0 : le-1]
if last > sum {
return isPartSum(divs, sum)
}
return isPartSum(divs, sum) || isPartSum(divs, sum-last)
}
func isZumkeller(n int) bool {
divs := getDivisors(n)
sum := sum(divs)
// if sum is odd can't be split into two partitions with equal sums
if sum%2 == 1 {
return false
}
// if n is odd use 'abundant odd number' optimization
if n%2 == 1 {
abundance := sum - 2*n
return abundance > 0 && abundance%2 == 0
}
// if n and sum are both even check if there's a partition which totals sum / 2
return isPartSum(divs, sum/2)
}
func main() {
fmt.Println("The first 220 Zumkeller numbers are:")
for i, count := 2, 0; count < 220; i++ {
if isZumkeller(i) {
fmt.Printf("%3d ", i)
count++
if count%20 == 0 {
fmt.Println()
}
}
}
fmt.Println("\nThe first 40 odd Zumkeller numbers are:")
for i, count := 3, 0; count < 40; i += 2 {
if isZumkeller(i) {
fmt.Printf("%5d ", i)
count++
if count%10 == 0 {
fmt.Println()
}
}
}
fmt.Println("\nThe first 40 odd Zumkeller numbers which don't end in 5 are:")
for i, count := 3, 0; count < 40; i += 2 {
if (i % 10 != 5) && isZumkeller(i) {
fmt.Printf("%7d ", i)
count++
if count%8 == 0 {
fmt.Println()
}
}
}
fmt.Println()
}</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Haskell
<lang haskell>import Data.List (group, sort) import Data.List.Split (chunksOf) import Data.Numbers.Primes (primeFactors)
ZUMKELLER NUMBERS -------------------
isZumkeller :: Int -> Bool isZumkeller n =
let ds = divisors n
m = sum ds
in ( even m
&& let half = div m 2
in elem half ds
|| ( all (half >=) ds
&& summable half ds
)
)
summable :: Int -> [Int] -> Bool summable _ [] = False summable x xs@(h : t) =
elem x xs || summable (x - h) t || summable x t
divisors :: Int -> [Int] divisors x =
sort
( foldr
( flip ((<*>) . fmap (*))
. scanl (*) 1
)
[1]
(group (primeFactors x))
)
TEST -------------------------
main :: IO () main =
mapM_
( \(s, n, xs) ->
putStrLn $
s
<> ( '\n' :
tabulated
10
(take n (filter isZumkeller xs))
)
)
[ ("First 220 Zumkeller numbers:", 220, [1 ..]),
("First 40 odd Zumkeller numbers:", 40, [1, 3 ..])
]
DISPLAY ------------------------
tabulated ::
Show a => Int -> [a] -> String
tabulated nCols = go
where
go xs =
let ts = show <$> xs
w = succ (maximum (length <$> ts))
in unlines
( concat
<$> chunksOf
nCols
(justifyRight w ' ' <$> ts)
)
justifyRight :: Int -> Char -> String -> String justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
Java
<lang java> import java.util.ArrayList; import java.util.Collections; import java.util.List;
public class ZumkellerNumbers {
public static void main(String[] args) {
int n = 1;
System.out.printf("First 220 Zumkeller numbers:%n");
for ( int count = 1 ; count <= 220 ; n += 1 ) {
if ( isZumkeller(n) ) {
System.out.printf("%3d ", n);
if ( count % 20 == 0 ) {
System.out.printf("%n");
}
count++;
}
}
n = 1;
System.out.printf("%nFirst 40 odd Zumkeller numbers:%n");
for ( int count = 1 ; count <= 40 ; n += 2 ) {
if ( isZumkeller(n) ) {
System.out.printf("%6d", n);
if ( count % 10 == 0 ) {
System.out.printf("%n");
}
count++;
}
}
n = 1;
System.out.printf("%nFirst 40 odd Zumkeller numbers that do not end in a 5:%n");
for ( int count = 1 ; count <= 40 ; n += 2 ) {
if ( n % 5 != 0 && isZumkeller(n) ) {
System.out.printf("%8d", n);
if ( count % 10 == 0 ) {
System.out.printf("%n");
}
count++;
}
}
}
private static boolean isZumkeller(int n) {
// numbers congruent to 6 or 12 modulo 18 are Zumkeller numbers
if ( n % 18 == 6 || n % 18 == 12 ) {
return true;
}
List<Integer> divisors = getDivisors(n);
int divisorSum = divisors.stream().mapToInt(i -> i.intValue()).sum();
// divisor sum cannot be odd
if ( divisorSum % 2 == 1 ) {
return false;
}
// numbers where n is odd and the abundance is even are Zumkeller numbers
int abundance = divisorSum - 2 * n;
if ( n % 2 == 1 && abundance > 0 && abundance % 2 == 0 ) {
return true;
}
Collections.sort(divisors);
int j = divisors.size() - 1;
int sum = divisorSum/2;
// Largest divisor larger than sum - then cannot partition and not Zumkeller number
if ( divisors.get(j) > sum ) {
return false;
}
return canPartition(j, divisors, sum, new int[2]);
}
private static boolean canPartition(int j, List<Integer> divisors, int sum, int[] buckets) {
if ( j < 0 ) {
return true;
}
for ( int i = 0 ; i < 2 ; i++ ) {
if ( buckets[i] + divisors.get(j) <= sum ) {
buckets[i] += divisors.get(j);
if ( canPartition(j-1, divisors, sum, buckets) ) {
return true;
}
buckets[i] -= divisors.get(j);
}
if( buckets[i] == 0 ) {
break;
}
}
return false;
}
private static final List<Integer> getDivisors(int number) {
List<Integer> divisors = new ArrayList<Integer>();
long sqrt = (long) Math.sqrt(number);
for ( int i = 1 ; i <= sqrt ; i++ ) {
if ( number % i == 0 ) {
divisors.add(i);
int div = number / i;
if ( div != i ) {
divisors.add(div);
}
}
}
return divisors;
}
} </lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers that do not end in a 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Julia
<lang julia>using Primes
function factorize(n)
f = [one(n)]
for (p, x) in factor(n)
f = reduce(vcat, [f*p^i for i in 1:x], init=f)
end
f
end
function cansum(goal, list)
if goal == 0 || list[1] == goal
return true
elseif length(list) > 1
if list[1] > goal
return cansum(goal, list[2:end])
else
return cansum(goal - list[1], list[2:end]) || cansum(goal, list[2:end])
end
end
return false
end
function iszumkeller(n)
f = reverse(factorize(n)) fsum = sum(f) return iseven(fsum) && cansum(div(fsum, 2) - f[1], f[2:end])
end
function printconditionalnum(condition, maxcount, numperline = 20)
count, spacing = 1, div(80, numperline)
for i in 1:typemax(Int)
if condition(i)
count += 1
print(rpad(i, spacing), (count - 1) % numperline == 0 ? "\n" : "")
if count > maxcount
return
end
end
end
end
println("First 220 Zumkeller numbers:") printconditionalnum(iszumkeller, 220) println("\n\nFirst 40 odd Zumkeller numbers:") printconditionalnum((n) -> isodd(n) && iszumkeller(n), 40, 8) println("\n\nFirst 40 odd Zumkeller numbers not ending with 5:") printconditionalnum((n) -> isodd(n) && (string(n)[end] != '5') && iszumkeller(n), 40, 8)
</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers not ending with 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Kotlin
<lang scala>import java.util.ArrayList import kotlin.math.sqrt
object ZumkellerNumbers {
@JvmStatic
fun main(args: Array<String>) {
var n = 1
println("First 220 Zumkeller numbers:")
run {
var count = 1
while (count <= 220) {
if (isZumkeller(n)) {
print("%3d ".format(n))
if (count % 20 == 0) {
println()
}
count++
}
n += 1
}
}
n = 1
println("\nFirst 40 odd Zumkeller numbers:")
run {
var count = 1
while (count <= 40) {
if (isZumkeller(n)) {
print("%6d".format(n))
if (count % 10 == 0) {
println()
}
count++
}
n += 2
}
}
n = 1
println("\nFirst 40 odd Zumkeller numbers that do not end in a 5:")
var count = 1
while (count <= 40) {
if (n % 5 != 0 && isZumkeller(n)) {
print("%8d".format(n))
if (count % 10 == 0) {
println()
}
count++
}
n += 2
}
}
private fun isZumkeller(n: Int): Boolean { // numbers congruent to 6 or 12 modulo 18 are Zumkeller numbers
if (n % 18 == 6 || n % 18 == 12) {
return true
}
val divisors = getDivisors(n)
val divisorSum = divisors.stream().mapToInt { i: Int? -> i!! }.sum()
// divisor sum cannot be odd
if (divisorSum % 2 == 1) {
return false
}
// numbers where n is odd and the abundance is even are Zumkeller numbers
val abundance = divisorSum - 2 * n
if (n % 2 == 1 && abundance > 0 && abundance % 2 == 0) {
return true
}
divisors.sort()
val j = divisors.size - 1
val sum = divisorSum / 2
// Largest divisor larger than sum - then cannot partition and not Zumkeller number
return if (divisors[j] > sum) false else canPartition(j, divisors, sum, IntArray(2))
}
private fun canPartition(j: Int, divisors: List<Int>, sum: Int, buckets: IntArray): Boolean {
if (j < 0) {
return true
}
for (i in 0..1) {
if (buckets[i] + divisors[j] <= sum) {
buckets[i] += divisors[j]
if (canPartition(j - 1, divisors, sum, buckets)) {
return true
}
buckets[i] -= divisors[j]
}
if (buckets[i] == 0) {
break
}
}
return false
}
private fun getDivisors(number: Int): MutableList<Int> {
val divisors: MutableList<Int> = ArrayList()
val sqrt = sqrt(number.toDouble()).toLong()
for (i in 1..sqrt) {
if (number % i == 0L) {
divisors.add(i.toInt())
val div = (number / i).toInt()
if (div.toLong() != i) {
divisors.add(div)
}
}
}
return divisors
}
}</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers that do not end in a 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Lobster
<lang Lobster>import std
// Derived from Julia and Python versions
def get_divisors(n: int) -> [int]:
var i = 2
let d = [1, n]
let limit = sqrt(n)
while i <= limit:
if n % i == 0:
let j = n / i
push(d,i)
if i != j:
push(d,j)
i += 1
return d
def isPartSum(divs: [int], sum: int) -> bool:
if sum == 0:
return true
let len = length(divs)
if len == 0:
return false
let last = pop(divs)
if last > sum:
return isPartSum(divs, sum)
return isPartSum(copy(divs), sum) or isPartSum(divs, sum-last)
def isZumkeller(n: int) -> bool:
let divs = get_divisors(n)
let sum = fold(divs, 0): _a+_b
if sum % 2 == 1:
// if sum is odd can't be split into two partitions with equal sums
return false
if n % 2 == 1:
// if n is odd use 'abundant odd number' optimization
let abundance = sum - 2 * n
return abundance > 0 and abundance % 2 == 0
return isPartSum(divs, sum/2)
def printZumkellers(q: int, oddonly: bool):
var nprinted = 0
var res = ""
for(100000) n:
if (!oddonly or n % 2 != 0):
if isZumkeller(n):
let s = string(n)
let z = length(s)
res = concat_string([res, repeat_string(" ",8-z), s], "")
nprinted += 1
if nprinted % 10 == 0 or nprinted >= q:
print res
res = ""
if nprinted >= q:
return
print "220 Zumkeller numbers:" printZumkellers(220, false) print "\n\n40 odd Zumkeller numbers:" printZumkellers(40, true) </lang>
- Output:
220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54
56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140
150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240
246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336
340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416
420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498
500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580
582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666
672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756
760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852
858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940
942 945 948 952 960 966 972 978 980 984
40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
Mathematica / Wolfram Language
<lang Mathematica>ClearAll[ZumkellerQ] ZumkellerQ[n_] := Module[{d = Divisors[n], t, ds, x},
ds = Total[d];
If[Mod[ds, 2] == 1,
False
,
t = CoefficientList[Product[1 + x^i, {i, d}], x];
t1 + ds/2 > 0
]
];
i = 1; res = {}; While[Length[res] < 220,
r = ZumkellerQ[i]; If[r, AppendTo[res, i]]; i++; ];
res
i = 1; res = {}; While[Length[res] < 40,
r = ZumkellerQ[i]; If[r, AppendTo[res, i]]; i += 2; ];
res</lang>
- Output:
{6,12,20,24,28,30,40,42,48,54,56,60,66,70,78,80,84,88,90,96,102,104,108,112,114,120,126,132,138,140,150,156,160,168,174,176,180,186,192,198,204,208,210,216,220,222,224,228,234,240,246,252,258,260,264,270,272,276,280,282,294,300,304,306,308,312,318,320,330,336,340,342,348,350,352,354,360,364,366,368,372,378,380,384,390,396,402,408,414,416,420,426,432,438,440,444,448,456,460,462,464,468,474,476,480,486,490,492,496,498,500,504,510,516,520,522,528,532,534,540,544,546,550,552,558,560,564,570,572,580,582,588,594,600,606,608,612,616,618,620,624,630,636,640,642,644,650,654,660,666,672,678,680,684,690,696,700,702,704,708,714,720,726,728,732,736,740,744,750,756,760,762,768,770,780,786,792,798,804,810,812,816,820,822,828,832,834,836,840,852,858,860,864,868,870,876,880,888,894,896,906,910,912,918,920,924,928,930,936,940,942,945,948,952,960,966,972,978,980,984}
{945,1575,2205,2835,3465,4095,4725,5355,5775,5985,6435,6615,6825,7245,7425,7875,8085,8415,8505,8925,9135,9555,9765,10395,11655,12285,12705,12915,13545,14175,14805,15015,15435,16065,16695,17325,17955,18585,19215,19305}
Nim
<lang Nim>import math, strutils
template isEven(n: int): bool = (n and 1) == 0 template isOdd(n: int): bool = (n and 1) != 0
func getDivisors(n: int): seq[int] =
result = @[1, n]
for i in 2..sqrt(n.toFloat).int:
if n mod i == 0:
let j = n div i
result.add i
if i != j: result.add j
func isPartSum(divs: seq[int]; sum: int): bool =
if sum == 0: return true if divs.len == 0: return false let last = divs[^1] let divs = divs[0..^2] result = isPartSum(divs, sum) if not result and last <= sum: result = isPartSum(divs, sum - last)
func isZumkeller(n: int): bool =
let divs = n.getDivisors() let sum = sum(divs) # If "sum" is odd, it can't be split into two partitions with equal sums. if sum.isOdd: return false # If "n" is odd use "abundant odd number" optimization. if n.isOdd: let abundance = sum - 2 * n return abundance > 0 and abundance.isEven # If "n" and "sum" are both even, check if there's a partition which totals "sum / 2". result = isPartSum(divs, sum div 2)
when isMainModule:
echo "The first 220 Zumkeller numbers are:"
var n = 2
var count = 0
while count < 220:
if n.isZumkeller:
stdout.write align($n, 3)
inc count
stdout.write if count mod 20 == 0: '\n' else: ' '
inc n
echo()
echo "The first 40 odd Zumkeller numbers are:"
n = 3
count = 0
while count < 40:
if n.isZumkeller:
stdout.write align($n, 5)
inc count
stdout.write if count mod 10 == 0: '\n' else: ' '
inc n, 2
echo()
echo "The first 40 odd Zumkeller numbers which don't end in 5 are:"
n = 3
count = 0
while count < 40:
if n mod 10 != 5 and n.isZumkeller:
stdout.write align($n, 7)
inc count
stdout.write if count mod 8 == 0: '\n' else: ' '
inc n, 2</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Pascal
modified practical numbers and Factors_of_an_integer#using_Prime_decomposition
prime decomposition included to get it run on TIO.RUN
Now using the trick, that one partition sum must include n and improved recursive search.
<lang pascal>program zumkeller;
//https://oeis.org/A083206/a083206.txt
{$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ALL} {$COPERATORS ON}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils
{$IFDEF WINDOWS},Windows{$ENDIF}
;
//###################################################################### //prime decomposition type
tItem = Uint32; tDivisors = array [0..1920] of tItem; tpDivisor = pUint32;
tPot = record
potSoD : Uint64;
potPrim,
potMax :Uint32;
end;
tprimeFac = record
pfPrims : array[0..15] of tPot;
pfSumOfDivs :Uint64;
pfCnt,
pfDivCnt,
pfNum,pfdummy : Uint32;
end;
type
tSmallPrimes = array[0..6541] of Word;
var
SmallPrimes: tSmallPrimes; isSmallPrimesInited : boolean = false;
procedure InitSmallPrimes; var
pr,testPr,j,maxprimidx: Uint32; isPrime : boolean;
Begin
maxprimidx := 0;
SmallPrimes[0] := 2;
pr := 3;
repeat
isprime := true;
j := 0;
repeat
testPr := SmallPrimes[j];
IF sqr(testPr) > pr then
break;
If pr mod testPr = 0 then
Begin
isprime := false;
break;
end;
inc(j);
until false;
if isprime then
Begin
inc(maxprimidx);
SmallPrimes[maxprimidx]:= pr;
end;
inc(pr,2);
until pr > 1 shl 16 -1;
isSmallPrimesInited:= true;
end;
function DivCount(const pD:tprimeFac):NativeUInt;inline; begin
result := pD.pfDivCnt;
end;
function SumOfDiv(const pD:tprimeFac):Uint64;inline; begin
result := pD.pfSumOfDivs;
end;
procedure PrimeDecomposition(n:Uint32;var res:tprimeFac); Label
Finished;
var
DivSum,fac:Uint64;
i,pr,cnt,DivCnt,quot{to minimize divisions} : Uint32;
Begin
if Not(isSmallPrimesInited) then
InitSmallPrimes;
//already done
if res.pfNum = n then
EXIT;
res.pfNum := n;
cnt := 0;
DivCnt := 1;
DivSum := 1;
i := 0;
if n <= 1 then
Begin
with res.pfPrims[0] do
Begin
potPrim := n;
potMax := 1;
end;
cnt := 1;
end
else
Begin
pr := 2;
IF 2*2>n then
GOTO Finished;
quot := n div 2;
IF 2*quot = n then
Begin
with res do
with pfPrims[Cnt] do
Begin
potPrim := 2;
potMax := 0;
fac := 2;
repeat
n := quot;
quot := quot div 2;
inc(potMax);
fac *= 2;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1)DIV (2-1);
potSoD := DivSum;
end;
inc(Cnt);
end;
pr := 3;
IF 3*3>n then
GOTO Finished;
quot := n div 3;
IF 3*quot = n then
begin
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := 3;
potMax := 0;
fac := 3;
repeat
n := quot;
quot := quot div 3;
inc(potMax);
fac *= 3;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1) DIV (3-1);
potSoD := DivSum;
end;
end;
inc(Cnt);
end;
pr := 5;
IF 5*5>n then
GOTO Finished;
quot := n div 5;
IF 5*quot = n then
begin
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := 5;
potMax := 0;
fac := 5;
repeat
n := quot;
quot := quot div 5;
inc(potMax);
fac *= 5;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1) DIV (5-1);
potSoD := DivSum;
end;
end;
inc(Cnt);
end;
pr := 7;
IF 7*7>n then
GOTO Finished;
quot := n div 7;
IF 7*quot = n then
begin
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := 7;
potMax := 0;
fac := 7;
repeat
n := quot;
quot := quot div 7;
inc(potMax);
fac *= 7;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1) DIV (7-1);
potSoD := DivSum;
end;
end;
inc(Cnt);
end;
pr := 11;
IF 11*11>n then
GOTO Finished;
quot := n div 11;
IF 11*quot = n then
begin
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := 11;
potMax := 0;
fac := 11;
repeat
n := quot;
quot := quot div 11;
inc(potMax);
fac *= 11;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1) DIV (11-1);
potSoD := DivSum;
end;
end;
inc(Cnt);
end;
pr := 13;
IF 13*13>n then
GOTO Finished;
quot := n div 13;
IF 13*quot = n then
begin
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := 13;
potMax := 0;
fac := 13;
repeat
n := quot;
quot := quot div 13;
inc(potMax);
fac *= 13;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1) DIV (13-1);
potSoD := DivSum;
end;
end;
inc(Cnt);
end;
i := 6;
repeat pr := SmallPrimes[i];
IF pr*pr>n then
Break;
quot := n div pr;
IF pr*quot = n then
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := pr;
potMax := 0;
fac := pr;
repeat
n := quot;
quot := quot div pr;
inc(potMax);
fac *= pr;
until pr*quot <> n;
DivCnt *= (potMax+1);
DivSum *= (fac-1)DIV(pr-1);
potSoD := DivSum;
end;
inc(Cnt);
end;
inc(i);
until false;
Finished:
//a big prime left over?
IF n > 1 then
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := n;
potMax := 1;
inc(Cnt);
DivCnt *= 2;
DivSum *= n+1;
potSoD := DivSum;
end;
end;
end;
res.pfCnt:= cnt;
res.pfDivCnt := DivCnt;
res.pfSumOfDivs := DivSum;
end;
procedure InsertSort(pDiv:tpDivisor; Left, Right : NativeInt ); var
I, J: NativeInt; Pivot : tItem;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pDiv[i];
j:= i - 1;
while (j >= Left) and (pDiv[j] > Pivot) do
begin
pDiv[j+1]:=pDiv[j];
Dec(j);
end;
pDiv[j+1]:= pivot;
end;
end;
procedure GetDivs(const pD:tprimeFac;var Divs:tDivisors); var
pDivs : tpDivisor; i,len,j,l,p,pPot,k: NativeInt;
Begin
i := DivCount(pD);
pDivs := @Divs[0];
pDivs[0] := 1;
len := 1;
l := 1;
For i := 0 to pD.pfCnt-1 do
with pD.pfPrims[i] do
Begin
//Multiply every divisor before with the new primefactors
//and append them to the list
k := potMax-1;
p := potPrim;
pPot :=1;
repeat
pPot *= p;
For j := 0 to len-1 do
Begin
pDivs[l]:= pPot*pDivs[j];
inc(l);
end;
dec(k);
until k<0;
len := l;
end;
//Sort. Insertsort much faster than QuickSort in this special case
InsertSort(pDivs,0,len-1);
end;
function OutPots(const pD:tprimeFac):Ansistring; var
s: String; i: NativeInt;
Begin
str(pD.pfNum:10,s);
result := s+' :';
str(DivCount(pD):5,s);
result += s+' : ';
For i := 0 to pD.pfCnt-1 do
with pD.pfPrims[i] do
Begin
if i>0 then
result += '*';
str(potPrim,s);
result += s;
if potMax >1 then
Begin
str(potMax,s);
result += '^'+s;
end;
end;
// str(SumOfDiv(pD):12,s);result := ' '+s+' ';
For i := 0 to pD.pfCnt-1 do
with pD.pfPrims[i] do
Begin
str(potSod,s);
result += ';'+s;
end;
end; //prime decomposition //######################################################################
type
tSol = array of Uint32; tpHasSum =pByte;
var
//no more than 1920 divisors von UInt32 ( HCN ) prechecked_Idx : array[0..1920] of Uint32; SumOfDivs : array[0..1920] of Uint64; sol : tSol; Divs: tDivisors; pDiv :tpDivisor; T0: Int64; depth : NativeInt; count,rek_count: NativeInt; finished :Boolean;
procedure Out_One_Sol(const pd:tprimefac); //shows prime decomposition and the used divisors to get the sum ( n is excluded ) var
i : NativeInt;
Begin
i := DivCount(pD); writeln(OutPots(pD)); write(SumOfDiv(pD)shr 1 - pd.pfNum:10,' = '); i:= 0; while prechecked_idx[i] > 0 do Begin write(prechecked_idx[i],'+'); inc(i); end; writeln(i:4,rek_count:12);
end;
procedure OutSol(const sol:tsol;colWidth,ColCount:NativeInt); var
i,col: NativeInt;
Begin
col := ColCount;
For i := 0 to High(sol) do
begin
write(' ',Sol[i]:colWidth-1);
dec(col);
if col = 0 then
Begin
writeln;
col := ColCount;
end;
end;
writeln;
end;
procedure Check_rek(SoD : Int64;i: NativeInt); var
sum : Int64;
begin
inc(rek_Count); WHILE (i>0) AND (pDiv[i]>SoD) do dec(i); inc(depth); while i >= 0 do Begin prechecked_idx[depth] := pDiv[i]; sum := SoD-pDiv[i];
if sum = 0 then
begin
finished := true;
prechecked_idx[depth+1] := 0;
EXIT;
end;
dec(i);
if (i>=0) AND (sum<=SumOfDivs[i]) then
Check_rek(sum,i);
if finished then
EXIT;
prechecked_idx[depth] := 0;
end;
dec(depth);
end;
function GetZumKeller(n: Uint32;var primeDecomp:tPrimefac): boolean; var
SoD,sum : Int64; Div_cnt,i: NativeInt;
begin
rek_count := 0; result := false; PrimeDecomposition(n,primeDecomp); SoD := SumOfDiv(primeDecomp);
//sum must be even and n not deficient if Odd(SoD) or (SoD<2*n) THEN EXIT(false);
//if Odd(n) then Exit(Not(odd(sum)));// to be tested
SoD := SoD shr 1-n; If SoD < 2 then //0,1 is always true Exit(true); //idx [0..DivCount(primeDecomp)-1]; Div_cnt := DivCount(primeDecomp)-1;
if Not(odd(n)) then
if ((n mod 18) in [6,12]) then
EXIT(true);
//Now one needs to get the divisors
GetDivs(primeDecomp,Divs);
//create a table of remaining sum
finished := true;
sum := 1;
SumOfDivs[0] := sum;
For i := 1 to Div_Cnt-1 do
Begin
If (sum+1<Divs[i]) AND (sum<SoD) then
finished := false;
sum += Divs[i];
SumOfDivs[i] := sum;
If sum >SoD then
break;
end;
//practical < SoD
if finished then
Exit(true);
finished := false; IF Div_cnt <= 1920 then Begin prechecked_idx[0]:= 0; depth := -1; pDiv := @Divs[0]; Check_rek(SoD,Div_cnt-1); exit(finished); end;
end;
procedure CheckSpecial(n:Uint32;var primeDecomp:tPrimeFac); var
isZK : boolean;
Begin
isZK:=GetZumKeller(n,primeDecomp);
writeln(n:10,' SumOfDivs ',SumOfDiv(primeDecomp):11,' CountOfDivs ',DivCount(primeDecomp),' isZk ',isZK);
writeln('rec ',rek_count:8,OutPots(primeDecomp));
end;
var
primeDecomp : tPrimeFac; n: NativeInt;
BEGIN
T0 := GetTickCount64;
writeln('Count of zumkeller numbers up to 10,000,000');
n := 1;
count :=0;
repeat
if GetZumKeller(n,primeDecomp) then
begin
// if count AND 16383 = 16383 then write(n,#13);
inc(count);
end;
inc(n);
until n > 10*1000*1000;
writeln(count:10,n-1:10);
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
writeln(#10,'First 220 zumkeller');
T0 := GetTickCount64;
n := 1;
count :=0;
setlength(sol,220);
repeat
if GetZumKeller(n,primeDecomp) then
begin
sol[count] := n;
inc(count);
end;
inc(n,1);
until count >= length(sol);
OutSol(sol,4,20);
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
T0 := GetTickCount64;
n := -1;
count :=0;
setlength(sol,40);
writeln(#10,'First 40 odd zumkeller numbers');
repeat
inc(n,2);
if GetZumKeller(n,primeDecomp) then
begin
sol[count] := n;
inc(count);
end;
until count>=length(sol);
OutSol(sol,10,8);
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
T0 := GetTickCount64;
n := 1;
count :=0;
setlength(sol,40);
writeln(#10,'First 40 odd zumkeller numbers not multiple of 5');
repeat
if GetZumKeller(n,primeDecomp) then
begin
sol[count] := n;
inc(count);
end;
inc(n,2);
if n mod 5 = 0 then
inc(n,2);
until count>=length(sol);
OutSol(sol,10,8);
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
T0 := GetTickCount64;
CheckSpecial(3492,primeDecomp);
CheckSpecial(14184,primeDecomp);
CheckSpecial(58896,primeDecomp);
CheckSpecial(236448,primeDecomp);
CheckSpecial(954432,primeDecomp);
CheckSpecial(2549700,primeDecomp);
CheckSpecial(10884600,primeDecomp);
T0 := GetTickCount64-T0;
writeln('runtime ',T0/1000:0:3,' s');
setlength(sol,0);
{$IFNDEF UNIX} readln; {$ENDIF}
END.</lang>
- Output:
TIO.RUN
Count of zumkeller numbers up to 10,000,000
2287889 10000000
runtime 6.494 s //1,000,000 takes 0.257 s
First 220 zumkeller
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984
runtime 0.000 s
First 40 odd zumkeller numbers
945 1575 2205 2835 3465 4095 4725 5355
5775 5985 6435 6615 6825 7245 7425 7875
8085 8415 8505 8925 9135 9555 9765 10395
11655 12285 12705 12915 13545 14175 14805 15015
15435 16065 16695 17325 17955 18585 19215 19305
runtime 0.001 s
First 40 odd zumkeller numbers not multiple of 5
81081 153153 171171 189189 207207 223839 243243 261261
279279 297297 351351 459459 513513 567567 621621 671517
729729 742203 783783 793611 812889 837837 891891 908523
960687 999999 1024947 1054053 1072071 1073709 1095633 1108107
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
runtime 0.175 s
3492 SumOfDivs 8918 CountOfDivs 18 isZk FALSE
rec 7 3492 : 18 : 2^2*3^2*97;7;91;8918
14184 SumOfDivs 38610 CountOfDivs 24 isZk FALSE
rec 19 14184 : 24 : 2^3*3^2*197;15;195;38610
58896 SumOfDivs 165230 CountOfDivs 30 isZk FALSE
rec 38 58896 : 30 : 2^4*3^2*409;31;403;165230
236448 SumOfDivs 673218 CountOfDivs 36 isZk FALSE
rec 130 236448 : 36 : 2^5*3^2*821;63;819;673218
954432 SumOfDivs 2737358 CountOfDivs 42 isZk FALSE
rec 513 954432 : 42 : 2^6*3^2*1657;127;1651;2737358
2549700 SumOfDivs 7994714 CountOfDivs 54 isZk FALSE
rec 2211 2549700 : 54 : 2^2*3^2*5^2*2833;7;91;2821;7994714
10884600 SumOfDivs 36560160 CountOfDivs 72 isZk FALSE
rec 853112 10884600 : 72 : 2^3*3^2*5^2*6047;15;195;6045;36560160
runtime 0.132 s
Real time: 7.132 s CPU share: 99.18 %
NEW: Much faster: tested count of odd zumkeller numbers ti 1,000,000,000
count of odd zumkeller numbers up to 1,000,000,000
n count count/ time
prechecked
10000000 20637 96.860 % 2.839 s
20000000 41463 96.698 % 7.519 s
30000000 62002 96.637 % 13.391 s
40000000 82513 96.474 % 20.381 s
50000000 103001 96.351 % 28.329 s
60000000 123482 96.283 % 37.077 s
70000000 143933 96.232 % 46.573 s
80000000 164412 96.202 % 56.877 s
90000000 184816 96.165 % 67.944 s
100000000 205283 96.152 % 79.329 s
150000000 307454 95.956 % 148.857 s
200000000 409569 95.835 % 239.997 s
250000000 511807 95.796 % 344.792 s
300000000 613721 95.792 % 478.399 s
400000000 817456 95.743 % 840.497 s
500000000 1021438 95.720 % 1291.123 s
600000000 1225716 95.708 % 1820.230 s
700000000 1430227 95.683 % 2461.841 s
800000000 1634217 95.625 % 3263.611 s
900000000 1838186 95.569 % 4161.572 s
1000000000 2042196 95.526 % 5134.790 s
2042196 999999999 pre checked 1950822
Tested odd zumkeller numbers up to 500,000,000 aka 5*10^8 , which takes 14h
All 205283 odd abundant numbers less than 10^8 that have even abundance are Zumkeller numbers. - T. D. Noe, Nov 14 2010
And yes there was no odd zumkeller with odd abundance->last prime factor must have a even power >0 2,4,6...
1 h5m33 ->138978315 runtime 3933.063 s
+12 h ->482567085
+13 h ->501864363 stopped
count;number;SumOfDivs;CountofDivs;number : prime decomposition
10159 4999995; 12257280; 128 ; 4999995 : 3^3*5*7*11*13*37
10160 5000625; 10396672; 60 ; 5000625 : 3^2*5^4*7*127
20637 9999825; 20570112; 96 ; 9999825 : 3*5^2*11*17*23*31
20638 10000305; 20217600; 48 ; 10000305 : 3^2*5*7*53*599
41463 19999875; 40135680; 64 ; 19999875 : 3*5^3*7*19*401
41464 20000925; 45372096; 120 ; 20000925 : 3^4*5^2*7*17*83
62002 29999475; 66852864; 144 ; 29999475 : 3^2*5^2*11*17*23*31
62003 30000915; 62208000; 64 ; 30000915 : 3^3*5*7*53*599
82513 39999645; 82697472; 48 ; 39999645 : 3^2*5*7*23*5521
82514 40000275; 82985760; 72 ; 40000275 : 3^2*5^2*7*109*233
103001 49999635; 104884416; 48 ; 49999635 : 3^2*5*7*17*9337
103002 50000895; 102735360; 48 ; 50000895 : 3^5*5*7*5879
205283 99999375; 200935680; 80 ; 99999375 : 3*5^4*7*19*401 //205283 odd abundant numbers less than 10^8
205284 100000845; 217728000; 128 ; 100000845 : 3^3*5*7*29*41*89
307454 149999535; 307841040; 72 ; 149999535 : 3^2*5*7^2*59*1153
307455 150000165; 306748416; 48 ; 150000165 : 3^2*5*7*31*15361
409569 199999305; 400443264; 48 ; 199999305 : 3^2*5*11*17*23767
409570 200000115; 403269984; 36 ; 200000115 : 3^2*5*7^2*90703
511807 249999435; 521314560; 48 ; 249999435 : 3^2*5*7*19*41771
511808 250000065; 506782848; 48 ; 250000065 : 3^2*5*7*43*18457
613721 299998755; 609523200; 32 ; 299998755 : 3^3*5*7*317459
613722 300000645; 611696640; 64 ; 300000645 : 3^3*5*7*523*607
715573 349998705; 742072320; 64 ; 349998705 : 3^3*5*7*23*16103
715574 350000595; 717044064; 40 ; 350000595 : 3^4*5*7*123457
817456 399998865; 808206336; 64 ; 399998865 : 3*5*7*17*23*9743
817457 400000293; 803312640; 96 ; 400000293 : 3^2*7*11*17*19*1787
919451 449999235; 922184640; 48 ; 449999235 : 3^2*5*7*29*49261
919452 450000495; 943841280; 64 ; 450000495 : 3^3*5*7*31*15361
1021438 499999185; 1052101440; 72 ; 499999185 : 3^2*5*7^2*23*9859
1021439 500000445; 1027178880; 48 ; 500000445 : 3^5*5*7*58789
ODD Zumkeller Index;CoD Count of Divisors;Average CoD;Zumkeller number
1; 16; 16.0000;945 : 3^3*5*7
2; 18; 18.0000;1575 : 3^2*5^2*7
4; 20; 19.0000;2835 : 3^4*5*7
5; 24; 24.0000;3465 : 3^2*5*7*11
24; 32; 24.4211;10395 : 3^3*5*7*11
36; 36; 27.5000;17325 : 3^2*5^2*7*11
69; 40; 30.4242;31185 : 3^4*5*7*11
101; 48; 33.3125;45045 : 3^2*5*7*11*13
246; 54; 37.7931;121275 : 3^2*5^2*7^2*11
272; 64; 41.1538;135135 : 3^3*5*7*11*13
439; 72; 43.2335;225225 : 3^2*5^2*7*11*13
814; 80; 45.8027;405405 : 3^4*5*7*11*13
1366; 96; 49.0688;675675 : 3^3*5^2*7*11*13
3126; 108; 53.1364;1576575 : 3^2*5^2*7^2*11*13
4025; 120; 55.8843;2027025 : 3^4*5^2*7*11*13
4573; 128; 56.6752;2297295 : 3^3*5*7*11*13*17
7715; 144; 58.4978;3828825 : 3^2*5^2*7*11*13*17
14116; 160; 61.1239;6891885 : 3^4*5*7*11*13*17
23733; 192; 63.7696;11486475 : 3^3*5^2*7*11*13*17
55414; 216; 67.8331;26801775 : 3^2*5^2*7^2*11*13*17
71154; 240; 70.7454;34459425 : 3^4*5^2*7*11*13*17
89984; 256; 72.0990;43648605 : 3^3*5*7*11*13*17*19
149543; 288; 74.2782;72747675 : 3^2*5^2*7*11*13*17*19
268601; 320; 77.3901;130945815 : 3^4*5*7*11*13*17*19
446838; 384; 80.4003;218243025 : 3^3*5^2*7*11*13*17*19
last 501864363
1025232 84.3602;
1025232 80.7680;501864363 : 3^3*7*11*13*31*599
CntOfDivs|Count | last occurence
16 1 945
18 2 2205
20 1 2835
24 37 32445
28 1 25515
30 5 108045
32 44011 501862095
36 47777 501859575
40 16114 501848865
42 6 5294205
44 1 2066715
48 197324 501856425
50 4 972405
52 1 18600435
54 2795 499226175
56 2254 501650415
60 11478 501809175
64 154291 501863985
66 4 19190925
70 8 47647845
72 102440 501846975
78 4 172718325
80 34227 501843195
84 1892 501788925
88 71 498078315
90 1987 501185475
96 211623 501863175
98 4 428830605
100 670 500833125
104 8 496897335
108 13834 501858225
110 3 479773125
112 4445 501803505
120 20477 501833475
126 310 501701445
128 67263 501864363
132 32 485678025
140 138 500731875
144 48901 501862725
150 136 500788575
160 11220 501808125
162 454 501511725
168 1299 501570225
176 4 456744015
180 1599 501780825
192 19903 501838155
200 173 501744375
210 6 481340475
216 2097 501752475
224 274 501854535
240 1368 501860205
252 42 499200975
256 1163 501756255
270 21 495685575
280 1 456080625
288 871 501666165
300 2 463876875
320 92 499926735
324 9 471395925
336 6 485269785
360 13 500675175
384 32 498513015
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory <is_prime divisor_sum divisors vecsum forcomb lastfor>;
sub in_columns {
my($columns, $values) = @_;
my @v = split ' ', $values;
my $width = int(80/$columns);
printf "%${width}d"x$columns."\n", @v[$_*$columns .. -1+(1+$_)*$columns] for 0..-1+@v/$columns;
print "\n";
}
sub is_Zumkeller {
my($n) = @_;
return 0 if is_prime($n);
my @divisors = divisors($n);
return 0 unless @divisors > 2 && 0 == @divisors % 2;
my $sigma = divisor_sum($n);
return 0 unless 0 == $sigma%2 && ($sigma/2) >= $n;
if (1 == $n%2) {
return 1
} else {
my $Z = 0;
forcomb { $Z++, lastfor if vecsum(@divisors[@_]) == $sigma/2 } @divisors;
return $Z;
}
}
use constant Inf => 1e10;
say 'First 220 Zumkeller numbers:'; my $n = 0; my $z; $z .= do { $n < 220 ? (is_Zumkeller($_) and ++$n and "$_ ") : last } for 1 .. Inf; in_columns(20, $z);
say 'First 40 odd Zumkeller numbers:'; $n = 0; $z = ; $z .= do { $n < 40 ? (!!($_%2) and is_Zumkeller($_) and ++$n and "$_ ") : last } for 1 .. Inf; in_columns(10, $z);
say 'First 40 odd Zumkeller numbers not divisible by 5:'; $n = 0; $z = ; $z .= do { $n < 40 ? (!!($_%2 and $_%5) and is_Zumkeller($_) and ++$n and "$_ ") : last } for 1 .. Inf; in_columns(10, $z);</lang>
- Output:
First 220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984
First 40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
First 40 odd Zumkeller numbers not divisible by 5:
81081 153153 171171 189189 207207 223839 243243 261261 279279 297297
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Phix
function isPartSum(sequence f, integer l, t) if t=0 then return true end if if l=0 then return false end if integer last = f[l] return (t>=last and isPartSum(f, l-1, t-last)) or isPartSum(f, l-1, t) end function function isZumkeller(integer n) sequence f = factors(n,1) integer t = sum(f) -- an odd sum cannot be split into two equal sums if remainder(t,2)=1 then return false end if -- if n is odd use 'abundant odd number' optimization if remainder(n,2)=1 then integer abundance := t - 2*n return abundance>0 and remainder(abundance,2)=0 end if -- if n and t both even check for any partition of t/2 return isPartSum(f, length(f), t/2) end function sequence tests = {{220,1,0,20,"%3d "}, {40,2,0,10,"%5d "}, {40,2,5,8,"%7d "}} integer lim, step, rem, cr; string fmt for t=1 to length(tests) do {lim, step, rem, cr, fmt} = tests[t] string odd = iff(step=1?"":"odd "), wch = iff(rem=0?"":"which don't end in 5 ") printf(1,"The first %d %sZumkeller numbers %sare:\n",{lim,odd,wch}) integer i = step+1, count = 0 while count<lim do if (rem=0 or remainder(i,10)!=rem) and isZumkeller(i) then printf(1,fmt,i) count += 1 if remainder(count,cr)=0 then puts(1,"\n") end if end if i += step end while printf(1,"\n") end for
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Aside: not that it really matters here, but passing an explicit length to isPartSum (ie, l) is generally quite a bit
faster than trimming (and therefore cloning) the contents of f, just so that we can rely on length(f), and obviously
that would get more significant were f much longer, though it does in fact max out at a mere 80 here.
In contrast, reversing the "or" tests on the final return of isPartSum() has a significant detrimental effect, since
it triggers a full recursive search for almost all l=0 failures before ever letting a single t=0 succeed. Quite why
I don't get anything like the same slowdown when I modify the Go code is beyond me...
PicoLisp
<lang PicoLisp>(de propdiv (N)
(make
(for I N
(and (=0 (% N I)) (link I)) ) ) )
(de sum? (G L)
(cond
((=0 G) T)
((= (car L) G) T)
((cdr L)
(if (> (car L) G)
(sum? G (cdr L))
(or
(sum? (- G (car L)) (cdr L))
(sum? G (cdr L)) ) ) ) ) )
(de zum? (N)
(let (L (propdiv N) S (sum prog L))
(and
(not (bit? 1 S))
(if (bit? 1 N)
(let A (- S (* 2 N))
(and (gt0 A) (not (bit? 1 A)))
)
(sum?
(- (/ S 2) (car L))
(cdr L) ) ) ) ) )
(zero C) (for (I 2 (> 220 C) (inc I))
(when (zum? I)
(prin (align 3 I) " ")
(inc 'C)
(and
(=0 (% C 20))
(prinl) ) ) )
(prinl) (zero C) (for (I 1 (> 40 C) (inc 'I 2))
(when (zum? I)
(prin (align 9 I) " ")
(inc 'C)
(and
(=0 (% C 8))
(prinl) ) ) )
(prinl) (zero C)
- cheater
(for (I 81079 (> 40 C) (inc 'I 2))
(when (and (<> 5 (% I 10)) (zum? I))
(prin (align 9 I) " ")
(inc 'C)
(and
(=0 (% C 8))
(prinl) ) ) )</lang>
- Output:
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984
945 1575 2205 2835 3465 4095 4725 5355
5775 5985 6435 6615 6825 7245 7425 7875
8085 8415 8505 8925 9135 9555 9765 10395
11655 12285 12705 12915 13545 14175 14805 15015
15435 16065 16695 17325 17955 18585 19215 19305
81081 153153 171171 189189 207207 223839 243243 261261
279279 297297 351351 459459 513513 567567 621621 671517
729729 742203 783783 793611 812889 837837 891891 908523
960687 999999 1024947 1054053 1072071 1073709 1095633 1108107
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Python
Procedural
Modified from a footnote at OEIS A083207 (see reference in problem text) by Charles R Greathouse IV. <lang python>from sympy import divisors
from sympy.combinatorics.subsets import Subset
def isZumkeller(n):
d = divisors(n)
s = sum(d)
if not s % 2 and max(d) <= s/2:
for x in range(1, 2**len(d)):
if sum(Subset.unrank_binary(x, d).subset) == s/2:
return True
return False
def printZumkellers(N, oddonly=False):
nprinted = 0
for n in range(1, 10**5):
if (oddonly == False or n % 2) and isZumkeller(n):
print(f'{n:>8}', end=)
nprinted += 1
if nprinted % 10 == 0:
print()
if nprinted >= N:
return
print("220 Zumkeller numbers:")
printZumkellers(220)
print("\n\n40 odd Zumkeller numbers:")
printZumkellers(40, True)
</lang>
- Output:
220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54
56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140
150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240
246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336
340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416
420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498
500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580
582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666
672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756
760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852
858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940
942 945 948 952 960 966 972 978 980 984
40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
Functional
Relying on the standard Python libraries, as an alternative to importing SymPy:
<lang python>Zumkeller numbers
from itertools import (
accumulate, chain, count, groupby, islice, product
) from functools import reduce from math import floor, sqrt import operator
- ---------------------- ZUMKELLER -----------------------
- isZumkeller :: Int -> Bool
def isZumkeller(n):
True if there exists a disjoint partition
of the divisors of m, such that the two sets have
the same sum.
(In other words, if n is in OEIS A083207)
ds = divisors(n)
m = sum(ds)
if even(m):
half = m // 2
return half in ds or (
all(map(ge(half), ds)) and (
summable(half, ds)
)
)
else:
return False
- summable :: Int -> [Int] -> Bool
def summable(x, xs):
True if any subset of the sorted
list xs sums to x.
if xs:
if x in xs:
return True
else:
t = xs[1:]
return summable(x - xs[0], t) or summable(x, t)
else:
return False
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
First 220 Zumkeller numbers,
and first 40 odd Zumkellers.
tenColumns = tabulated(10)
print('First 220 Zumkeller numbers:\n')
print(tenColumns(
take(220)(
filter(isZumkeller, count(1))
)
))
print('\nFirst 40 odd Zumkeller numbers:\n')
print(tenColumns(
take(40)(
filter(isZumkeller, enumFromThen(1)(3))
)
))
- ---------------------- TABULATION ----------------------
- tabulated :: Int -> [a] -> String
def tabulated(nCols):
String representation of a list
of values as rows of n columns.
def go(xs):
ts = [str(x) for x in xs]
w = 1 + max(len(x) for x in ts)
return '\n'.join([
.join(row) for row
in chunksOf(nCols)([
t.rjust(w, ' ') for t in ts
])
])
return go
- ----------------------- GENERIC ------------------------
- chunksOf :: Int -> [a] -> a
def chunksOf(n):
A series of lists of length n, subdividing the
contents of xs. Where the length of xs is not evenly
divible, the final list will be shorter than n.
def go(xs):
return (
xs[i:n + i] for i in range(0, len(xs), n)
) if 0 < n else None
return go
- divisors :: Int -> [Int]
def divisors(n):
The ordered divisors of n.
def go(a, x):
return [a * b for a, b in product(
a,
accumulate(chain([1], x), operator.mul)
)]
return sorted(
reduce(go, [
list(g) for _, g in groupby(primeFactors(n))
], [1])
) if 1 < n else [1]
- enumFromThen :: Int -> Int -> [Int]
def enumFromThen(m):
A non-finite stream of integers
starting at m, and continuing
at the interval between m and n.
return lambda n: count(m, n - m)
- even :: Int -> Bool
def even(x):
True if x is an integer
multiple of two.
return 0 == x % 2
- ge :: Eq a => a -> a -> Bool
def ge(a):
def go(b):
return operator.ge(a, b)
return go
- primeFactors :: Int -> [Int]
def primeFactors(n):
A list of the prime factors of n.
def f(qr):
r = qr[1]
return step(r), 1 + r
def step(x):
return 1 + (x << 2) - ((x >> 1) << 1)
def go(x):
root = floor(sqrt(x))
def p(qr):
q = qr[0]
return root < q or 0 == (x % q)
q = until(p)(f)(
(2 if 0 == x % 2 else 3, 1)
)[0]
return [x] if q > root else [q] + go(x // q)
return go(n)
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n,
or xs itself if n > length xs.
def go(xs):
return (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
return go
- until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p):
The result of repeatedly applying f until p holds.
The initial seed value is x.
def go(f):
def g(x):
v = x
while not p(v):
v = f(v)
return v
return g
return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
Racket
<lang racket>#lang racket
(require math/number-theory)
(define (zum? n)
(let* ((set (divisors n))
(sum (apply + set)))
(cond
[(odd? sum) #f]
[(odd? n) ; if n is odd use 'abundant odd number' optimization
(let ((abundance (- sum (* n 2)))) (and (positive? abundance) (even? abundance)))]
[else
(let ((sum/2 (quotient sum 2)))
(let loop ((acc (car set)) (set (cdr set)))
(cond [(= acc sum/2) #t]
[(> acc sum/2) #f]
[(null? set) #f]
[else (or (loop (+ (car set) acc) (cdr set))
(loop acc (cdr set)))])))])))
(define (first-n-matching-naturals count pred)
(for/list ((i count) (j (stream-filter pred (in-naturals 1)))) j))
(define (tabulate title ns (row-width 132))
(displayln title)
(let* ((cell-width (+ 2 (order-of-magnitude (apply max ns))))
(cells/row (quotient row-width cell-width)))
(let loop ((ns ns) (col cells/row))
(cond [(null? ns) (unless (= col cells/row) (newline))]
[(zero? col) (newline) (loop ns cells/row)]
[else (display (~a #:width cell-width #:align 'right (car ns)))
(loop (cdr ns) (sub1 col))]))))
(tabulate "First 220 Zumkeller numbers:" (first-n-matching-naturals 220 zum?))
(newline)
(tabulate "First 40 odd Zumkeller numbers:"
(first-n-matching-naturals 40 (λ (n) (and (odd? n) (zum? n)))))
(newline) (tabulate "First 40 odd Zumkeller numbers not ending in 5:"
(first-n-matching-naturals 40 (λ (n) (and (odd? n) (not (= 5 (modulo n 10))) (zum? n)))))</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers not ending in 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Raku
(formerly Perl 6)
<lang perl6>use ntheory:from<Perl5> <factor is_prime>;
sub zumkeller ($range) {
$range.grep: -> $maybe {
next if $maybe < 3;
next if $maybe.&is_prime;
my @divisors = $maybe.&factor.combinations».reduce( &[*] ).unique.reverse;
next unless [&&] +@divisors > 2, +@divisors %% 2, (my $sum = sum @divisors) %% 2, ($sum /= 2) >= $maybe;
my $zumkeller = False;
if $maybe % 2 {
$zumkeller = True
} else {
TEST: loop (my $c = 1; $c < @divisors / 2; ++$c) {
@divisors.combinations($c).map: -> $d {
next if (sum $d) != $sum;
$zumkeller = True and last TEST;
}
}
}
$zumkeller
}
}
say "First 220 Zumkeller numbers:\n" ~
zumkeller(^Inf)[^220].rotor(20)».fmt('%3d').join: "\n";
put "\nFirst 40 odd Zumkeller numbers:\n" ~
zumkeller((^Inf).map: * * 2 + 1)[^40].rotor(10)».fmt('%7d').join: "\n";
- Stretch. Slow to calculate. (minutes)
put "\nFirst 40 odd Zumkeller numbers not divisible by 5:\n" ~
zumkeller(flat (^Inf).map: {my \p = 10 * $_; p+1, p+3, p+7, p+9} )[^40].rotor(10)».fmt('%7d').join: "\n";</lang>
- Output:
First 220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198
204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282
294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368
372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462
464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540
544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708
714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810
812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896
906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984
First 40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
First 40 odd Zumkeller numbers not divisible by 5:
81081 153153 171171 189189 207207 223839 243243 261261 279279 297297
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
REXX
The construction of the partitions were created in the order in which the most likely partitions would match. <lang rexx>/*REXX pgm finds & shows Zumkeller numbers: 1st N; 1st odd M; 1st odd V not ending in 5.*/ parse arg n m v . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 220 /*Not specified? Then use the default.*/ if m== | m=="," then m= 40 /* " " " " " " */ if v== | v=="," then v= 40 /* " " " " " " */ @zum= ' Zumkeller numbers are: ' /*literal used for displaying messages.*/ sw= linesize() - 1 /*obtain the usable screen width. */ say if n>0 then say center(' The first ' n @zum, sw, "═")
- = 0 /*the count of Zumkeller numbers so far*/
$= /*initialize the $ list (to a null).*/
do j=1 until #==n /*traipse through integers 'til done. */
if \Zum(j) then iterate /*if not a Zumkeller number, then skip.*/
#= # + 1; call add$ /*bump Zumkeller count; add to $ list.*/
end /*j*/
if $\== then say $ /*Are there any residuals? Then display*/ say if m>0 then say center(' The first odd ' m @zum, sw, "═")
- = 0 /*the count of Zumkeller numbers so far*/
$= /*initialize the $ list (to a null).*/
do j=1 by 2 until #==m /*traipse through integers 'til done. */
if \Zum(j) then iterate /*if not a Zumkeller number, then skip.*/
#= # + 1; call add$ /*bump Zumkeller count; add to $ list.*/
end /*j*/
if $\== then say $ /*Are there any residuals? Then display*/ say if v>0 then say center(' The first odd ' v " (not ending in 5) " @zum, sw, '═')
- = 0 /*the count of Zumkeller numbers so far*/
$= /*initialize the $ list (to a null).*/
do j=1 by 2 until #==v /*traipse through integers 'til done. */
if right(j,1)==5 then iterate /*skip if odd number ends in digit "5".*/
if \Zum(j) then iterate /*if not a Zumkeller number, then skip.*/
#= # + 1; call add$ /*bump Zumkeller count; add to $ list.*/
end /*j*/
if $\== then say $ /*Are there any residuals? Then display*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ add$: _= strip($ j, 'L'); if length(_)<sw then do; $= _; return; end /*add to $*/
say strip($, 'L'); $= j; return /*say, add*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; r= 0; q= 1; do while q<=x; q=q*4; end
do while q>1; q= q%4; _= x-r-q; r= r%2; if _>=0 then do; x= _; r= r+q; end; end
return r /*R is the integer square root of X. */
/*──────────────────────────────────────────────────────────────────────────────────────*/ PDaS: procedure; parse arg x 1 b; odd= x//2 /*obtain X and B (the 1st argument).*/
if x==1 then return 1 1 /*handle special case for unity. */
r= iSqrt(x) /*calculate integer square root of X. */
a= 1 /* [↓] use all, or only odd numbers. */
sig= a + b /*initialize the sigma (so far) ___ */
do j=2+odd by 1+odd to r - (r*r==x) /*divide by some integers up to √ X */
if x//j==0 then do; a=a j; b= x%j b /*if ÷, add both divisors to α & ß. */
sig= sig +j +x%j /*bump the sigma (the sum of divisors).*/
end
end /*j*/ /* [↑] % is the REXX integer division*/
/* [↓] adjust for a square. ___*/
if j*j==x then return sig+j a j b /*Was X a square? If so, add √ X */
return sig a b /*return the divisors (both lists). */
/*──────────────────────────────────────────────────────────────────────────────────────*/ Zum: procedure; parse arg x . /*obtain a # to be tested for Zumkeller*/
if x<6 then return 0 /*test if X is too low " " */
if x<945 then if x//2==1 then return 0 /* " " " " " " for odd " */
parse value PDaS(x) with sigma pdivs /*obtain sigma and the proper divisors.*/
if sigma//2 then return 0 /*Is the sigma odd? Not Zumkeller.*/
#= words(pdivs) /*count the number of divisors for X. */
if #<3 then return 0 /*Not enough divisors? " " */
if x//2 then do; _= sigma - x - x /*use abundant optimization for odd #'s*/
return _>0 & _//2==0 /*Abundant is > 0 and even? It's a Zum*/
end
if #>23 then return 1 /*# divisors is 24 or more? It's a Zum*/
do i=1 for #; @.i= word(pdivs, i) /*assign proper divisors to the @ array*/
end /*i*/
c=0; u= 2**#; !.= .
do p=1 for u-2; b= x2b(d2x(p)) /*convert P──►binary with leading zeros*/
b= right(strip(b, 'L', 0), #, 0) /*ensure enough leading zeros for B. */
r= reverse(b); if !.r\==. then iterate /*is this binary# a palindrome of prev?*/
c= c + 1; yy.c= b; !.b= /*store this particular combination. */
end /*p*/
do part=1 for c; p1= 0; p2= 0 /*test of two partitions add to same #.*/
_= yy.part /*obtain one method of partitioning. */
do cp=1 for # /*obtain the sums of the two partitions*/
if substr(_, cp, 1) then p1= p1 + @.cp /*if a one, then add it to P1.*/
else p2= p2 + @.cp /* " " zero, " " " " P2.*/
end /*cp*/
if p1==p2 then return 1 /*Partition sums equal? Then X is Zum.*/
end /*part*/
return 0 /*no partition sum passed. X isn't Zum*/</lang>
- output when using the default inputs:
══════════════════════════════════════════════ The first 220 Zumkeller numbers are: ═══════════════════════════════════════════════ 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 ═════════════════════════════════════════════ The first odd 40 Zumkeller numbers are: ═════════════════════════════════════════════ 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 ═══════════════════════════════════ The first odd 40 (not ending in 5) Zumkeller numbers are: ═══════════════════════════════════ 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "The first 220 Zumkeller numbers are:" + nl
permut = [] zumind = [] zumodd = [] limit = 19305 num1 = 0 num2 = 0
for n = 2 to limit
zumkeller = []
zumList = []
permut = []
calmo = []
zumind = []
num = 0
nold = 0
for m = 1 to n
if n % m = 0
num = num + 1
add(zumind,m)
ok
next
for p = 1 to num
add(zumList,1)
add(zumList,2)
next
permut(zumList)
lenZum = len(zumList)
for n2 = 1 to len(permut)/lenZum
str = ""
for m = (n2-1)*lenZum+1 to n2*lenZum
str = str + string(permut[m])
next
if str != ""
strNum = number(str)
add(calmo,strNum)
ok
next
calmo = sort(calmo)
for x = len(calmo) to 2 step -1
if calmo[x] = calmo[x-1]
del(calmo,x)
ok
next
zumkeller = []
calmoLen = len(string(calmo[1]))
calmoLen2 = calmoLen/2
for y = 1 to len(calmo)
tmpStr = string(calmo[y])
tmp1 = left(tmpStr,calmoLen2)
tmp2 = number(tmp1)
add(zumkeller,tmp2)
next
zumkeller = sort(zumkeller)
for x = len(zumkeller) to 2 step -1
if zumkeller[x] = zumkeller[x-1]
del(zumkeller,x)
ok
next
for z = 1 to len(zumkeller)
zumsum1 = 0
zumsum2 = 0
zum1 = []
zum2 = []
for m = 1 to len(string(zumkeller[z]))
zumstr = string(zumkeller[z])
tmp = number(zumstr[m])
if tmp = 1
add(zum1,zumind[m])
else
add(zum2,zumind[m])
ok
next
for z1 = 1 to len(zum1)
zumsum1 = zumsum1 + zum1[z1]
next
for z2 = 1 to len(zum2)
zumsum2 = zumsum2 + zum2[z2]
next
if zumsum1 = zumsum2
num1 = num1 + 1
if n != nold
if num1 < 221
if (n-1)%22 = 0
see nl + " " + n
else
see " " + n
ok
ok
if zumsum1%2 = 1
num2 = num2 + 1
if num2 < 41
add(zumodd,n)
ok
ok
ok
nold = n
ok
next
next
see "The first 40 odd Zumkeller numbers are:" + nl for n = 1 to len(zumodd)
if (n-1)%8 = 0
see nl + " " + zumodd[n]
else
see " " + zumodd[n]
ok
next
see nl + "done..." + nl
func permut(list)
for perm = 1 to factorial(len(list))
for i = 1 to len(list)
add(permut,list[i])
next
perm(list)
next
func perm(a)
elementcount = len(a)
if elementcount < 1
return
ok
pos = elementcount-1
while a[pos] >= a[pos+1]
pos -= 1
if pos <= 0 permutationReverse(a, 1, elementcount)
return
ok
end
last = elementcount
while a[last] <= a[pos]
last -= 1
end
temp = a[pos]
a[pos] = a[last]
a[last] = temp
permReverse(a, pos+1, elementcount)
func permReverse(a,first,last)
while first < last
temp = a[first]
a[first] = a[last]
a[last] = temp
first += 1
last -= 1
end
</lang> Output:
working... The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 done...
Ruby
<lang ruby>class Integer
def divisors
res = [1, self]
(2..Integer.sqrt(self)).each do |n|
div, mod = divmod(n)
res << n << div if mod.zero?
end
res.uniq.sort
end
def zumkeller?
divs = divisors
sum = divs.sum
return false unless sum.even? && sum >= self*2
half = sum / 2
max_combi_size = divs.size / 2
1.upto(max_combi_size).any? do |combi_size|
divs.combination(combi_size).any?{|combi| combi.sum == half}
end
end
end
def p_enum(enum, cols = 10, col_width = 8)
enum.each_slice(cols) {|slice| puts "%#{col_width}d"*slice.size % slice}
end
puts "#{n=220} Zumkeller numbers:" p_enum 1.step.lazy.select(&:zumkeller?).take(n), 14, 6
puts "\n#{n=40} odd Zumkeller numbers:" p_enum 1.step(by: 2).lazy.select(&:zumkeller?).take(n)
puts "\n#{n=40} odd Zumkeller numbers not ending with 5:" p_enum 1.step(by: 2).lazy.select{|x| x % 5 > 0 && x.zumkeller?}.take(n) </lang>
- Output:
220 Zumkeller numbers:
6 12 20 24 28 30 40 42 48 54 56 60 66 70
78 80 84 88 90 96 102 104 108 112 114 120 126 132
138 140 150 156 160 168 174 176 180 186 192 198 204 208
210 216 220 222 224 228 234 240 246 252 258 260 264 270
272 276 280 282 294 300 304 306 308 312 318 320 330 336
340 342 348 350 352 354 360 364 366 368 372 378 380 384
390 396 402 408 414 416 420 426 432 438 440 444 448 456
460 462 464 468 474 476 480 486 490 492 496 498 500 504
510 516 520 522 528 532 534 540 544 546 550 552 558 560
564 570 572 580 582 588 594 600 606 608 612 616 618 620
624 630 636 640 642 644 650 654 660 666 672 678 680 684
690 696 700 702 704 708 714 720 726 728 732 736 740 744
750 756 760 762 768 770 780 786 792 798 804 810 812 816
820 822 828 832 834 836 840 852 858 860 864 868 870 876
880 888 894 896 906 910 912 918 920 924 928 930 936 940
942 945 948 952 960 966 972 978 980 984
40 odd Zumkeller numbers:
945 1575 2205 2835 3465 4095 4725 5355 5775 5985
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305
40 odd Zumkeller numbers not ending with 5:
81081 153153 171171 189189 207207 223839 243243 261261 279279 297297
351351 459459 513513 567567 621621 671517 729729 742203 783783 793611
812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709
1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Rust
<lang rust> use std::convert::TryInto;
/// Gets all divisors of a number, including itself fn get_divisors(n: u32) -> Vec<u32> {
let mut results = Vec::new();
for i in 1..(n / 2 + 1) {
if n % i == 0 {
results.push(i);
}
}
results.push(n);
results
}
/// Calculates whether the divisors can be partitioned into two disjoint /// sets that sum to the same value fn is_summable(x: i32, divisors: &[u32]) -> bool {
if !divisors.is_empty() {
if divisors.contains(&(x as u32)) {
return true;
} else if let Some((first, t)) = divisors.split_first() {
return is_summable(x - *first as i32, &t) || is_summable(x, &t);
}
}
false
}
/// Calculates whether the number is a Zumkeller number /// Zumkeller numbers are the set of numbers whose divisors can be partitioned /// into two disjoint sets that sum to the same value. Each sum must contain /// divisor values that are not in the other sum, and all of the divisors must /// be in one or the other. fn is_zumkeller_number(number: u32) -> bool {
if number % 18 == 6 || number % 18 == 12 {
return true;
}
let div = get_divisors(number);
let divisor_sum: u32 = div.iter().sum();
if divisor_sum == 0 {
return false;
}
if divisor_sum % 2 == 1 {
return false;
}
// numbers where n is odd and the abundance is even are Zumkeller numbers
let abundance = divisor_sum as i32 - 2 * number as i32;
if number % 2 == 1 && abundance > 0 && abundance % 2 == 0 {
return true;
}
let half = divisor_sum / 2;
return div.contains(&half)
|| (div.iter().filter(|&&d| d < half).count() > 0
&& is_summable(half.try_into().unwrap(), &div));
}
fn main() {
println!("\nFirst 220 Zumkeller numbers:");
let mut counter: u32 = 0;
let mut i: u32 = 0;
while counter < 220 {
if is_zumkeller_number(i) {
print!("{:>3}", i);
counter += 1;
print!("{}", if counter % 20 == 0 { "\n" } else { "," });
}
i += 1;
}
println!("\nFirst 40 odd Zumkeller numbers:");
let mut counter: u32 = 0;
let mut i: u32 = 3;
while counter < 40 {
if is_zumkeller_number(i) {
print!("{:>5}", i);
counter += 1;
print!("{}", if counter % 20 == 0 { "\n" } else { "," });
}
i += 2;
}
} </lang>
- Output:
First 220 Zumkeller numbers: 6, 12, 20, 24, 28, 30, 40, 42, 48, 54, 56, 60, 66, 70, 78, 80, 84, 88, 90, 96 102,104,108,112,114,120,126,132,138,140,150,156,160,168,174,176,180,186,192,198 204,208,210,216,220,222,224,228,234,240,246,252,258,260,264,270,272,276,280,282 294,300,304,306,308,312,318,320,330,336,340,342,348,350,352,354,360,364,366,368 372,378,380,384,390,396,402,408,414,416,420,426,432,438,440,444,448,456,460,462 464,468,474,476,480,486,490,492,496,498,500,504,510,516,520,522,528,532,534,540 544,546,550,552,558,560,564,570,572,580,582,588,594,600,606,608,612,616,618,620 624,630,636,640,642,644,650,654,660,666,672,678,680,684,690,696,700,702,704,708 714,720,726,728,732,736,740,744,750,756,760,762,768,770,780,786,792,798,804,810 812,816,820,822,828,832,834,836,840,852,858,860,864,868,870,876,880,888,894,896 906,910,912,918,920,924,928,930,936,940,942,945,948,952,960,966,972,978,980,984
Sidef
<lang ruby>func is_Zumkeller(n) {
return false if n.is_prime return false if n.is_square
var sigma = n.sigma
# n must have an even abundance return false if (sigma.is_odd || (sigma < 2*n))
# true if n is odd and has an even abundance return true if n.is_odd # conjecture
var divisors = n.divisors
for k in (2 .. divisors.end) {
divisors.combinations(k, {|*a|
if (2*a.sum == sigma) {
return true
}
})
}
return false
}
say "First 220 Zumkeller numbers:" say (1..Inf -> lazy.grep(is_Zumkeller).first(220).join(' '))
say "\nFirst 40 odd Zumkeller numbers: " say (1..Inf `by` 2 -> lazy.grep(is_Zumkeller).first(40).join(' '))
say "\nFirst 40 odd Zumkeller numbers not divisible by 5: " say (1..Inf `by` 2 -> lazy.grep { _ % 5 != 0 }.grep(is_Zumkeller).first(40).join(' '))</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 First 40 odd Zumkeller numbers not divisible by 5: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Standard ML
<lang Standard ML> exception Found of string ;
val divisors = fn n => let
val rec divr = fn ( c, divlist ,i) =>
if c <2*i then c::divlist
else divr (if c mod i = 0 then (c,i::divlist,i+1) else (c,divlist,i+1) )
in
divr (n,[],1)
end;
val subsetSums = fn M => fn input =>
let
val getnrs = fn (v,x) => (* out: list of numbers index where v is true + x *)
let
val rec runthr = fn (v,i,x,lst)=> if i>=M then (v,i,x,lst) else runthr (v,i+1,x,if Vector.sub(v,i) then (i+x)::lst else lst) ;
in
#4 (runthr (v,0,x,[]))
end;
val nwVec = fn (v,nrs) =>
let
val rec upd = fn (v,i,[]) => (v,i,[])
| (v,i,h::t) => upd ( case Int.compare (h,M) of
LESS => ( Vector.update (v,h,true),i+1,t) | GREATER => (v,i+1,t) | EQUAL => raise Found ("done "^(Int.toString h)) )
in
#1 (upd (v,0,nrs))
end;
val rec setSums = fn ([],v) => ([],v)
| (x::t,v) => setSums(t, nwVec(v, getnrs (v,x)))
in
#2 (setSums (input,Vector.tabulate (M+1,fn 0=> true|_=>false) ))
end;
val rec Zumkeller = fn n =>
let
val d = divisors n;
val s = List.foldr op+ 0 d ;
val hs = s div 2 -n ;
in
if s mod 2 = 1 orelse 0 > hs then false else
Vector.sub ( subsetSums hs (tl d) ,hs) handle Found nr => true
end; </lang> call loop and output - interpreter <lang Standard ML> - val Zumkellerlist = fn step => fn no5 => let
val rec loop = fn incr => fn (i,n,v) =>
if i= (case incr of 1 => 221 | 2 => 41 | _ => 5 )
then (0,n,v)
else if n mod 5 = 0 andalso no5 then loop incr (i,n+incr,v) else
if Zumkeller n then loop incr (i+1,n+incr,(i,n)::v) else loop incr (i,n+incr,v) in
rev (#3 ( loop step (1,3,[])))
end; - List.app (fn x=> print (Int.toString (#2 x) ^ ", ")) (Zumkellerlist 1 false) ; 6, 12, 20, 24, 28, 30, 40, 42, 48, 54, 56, 60, 66, 70, 78, 80, 84, 88, 90, 96, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 150, 156, 160, 168, 174, 176, 180, 186, 192, 198, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 294, 300, 304, 306, 308, 312, 318, 320, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 396, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 496, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 650, 654, 660, 666, 672, 678, 680, 684, 690, 696, 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 740, 744, 750, 756, 760, 762, 768, 770, 780, 786, 792, 798, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836, 840, 852, 858, 860, 864, 868, 870, 876, 880, 888, 894, 896, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945, 948, 952, 960, 966, 972, 978, 980, 984
- List.app (fn x=> print (Int.toString (#2 x) ^ ", ")) (Zumkellerlist 2 false) ;
945, 1575, 2205, 2835, 3465, 4095, 4725, 5355, 5775, 5985, 6435, 6615, 6825, 7245, 7425, 7875, 8085, 8415, 8505, 8925, 9135, 9555, 9765, 10395, 11655, 12285, 12705, 12915, 13545, 14175, 14805, 15015, 15435, 16065, 16695, 17325, 17955, 8585, 19215, 19305
- List.app (fn x=> print (Int.toString (#2 x) ^ ", ")) (Zumkellerlist 2 true) ;
81081, 153153, 171171, 189189, 207207, 223839, 243243, 261261, 279279, 297297, 351351, 459459, 513513, 567567, 621621, 671517, 729729,
742203, 783783, 793611, 812889, 837837, 891891, 908523, 960687, 999999, 1024947, 1054053, 1072071, 1073709, 1095633, 1108107, 1145529,
1162161, 1198197, 1224531, 1270269, 1307691, 1324323, 1378377
</lang>
Swift
<lang swift>import Foundation
extension BinaryInteger {
@inlinable
public var isZumkeller: Bool {
let divs = factors(sorted: false)
let sum = divs.reduce(0, +)
guard sum & 1 != 1 else {
return false
}
guard self & 1 != 1 else {
let abundance = sum - 2*self
return abundance > 0 && abundance & 1 == 0 }
return isPartSum(divs: divs[...], sum: sum / 2) }
@inlinable
public func factors(sorted: Bool = true) -> [Self] {
let maxN = Self(Double(self).squareRoot())
var res = Set<Self>()
for factor in stride(from: 1, through: maxN, by: 1) where self % factor == 0 {
res.insert(factor)
res.insert(self / factor)
}
return sorted ? res.sorted() : Array(res) }
}
@usableFromInline func isPartSum<T: BinaryInteger>(divs: ArraySlice<T>, sum: T) -> Bool {
guard sum != 0 else {
return true
}
guard !divs.isEmpty else {
return false
}
let last = divs.last!
if last > sum {
return isPartSum(divs: divs.dropLast(), sum: sum)
}
return isPartSum(divs: divs.dropLast(), sum: sum) || isPartSum(divs: divs.dropLast(), sum: sum - last)
}
let zums = (2...).lazy.filter({ $0.isZumkeller }) let oddZums = zums.filter({ $0 & 1 == 1 }) let oddZumsWithout5 = oddZums.filter({ String($0).last! != "5" })
print("First 220 zumkeller numbers are \(Array(zums.prefix(220)))") print("First 40 odd zumkeller numbers are \(Array(oddZums.prefix(40)))") print("First 40 odd zumkeller numbers that don't end in a 5 are: \(Array(oddZumsWithout5.prefix(40)))")</lang>
- Output:
First 220 zumkeller numbers are: [6, 12, 20, 24, 28, 30, 40, 42, 48, 54, 56, 60, 66, 70, 78, 80, 84, 88, 90, 96, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 150, 156, 160, 168, 174, 176, 180, 186, 192, 198, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 294, 300, 304, 306, 308, 312, 318, 320, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 396, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 496, 498, 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550, 552, 558, 560, 564, 570, 572, 580, 582, 588, 594, 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 650, 654, 660, 666, 672, 678, 680, 684, 690, 696, 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 740, 744, 750, 756, 760, 762, 768, 770, 780, 786, 792, 798, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836, 840, 852, 858, 860, 864, 868, 870, 876, 880, 888, 894, 896, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945, 948, 952, 960, 966, 972, 978, 980, 984] First 40 odd zumkeller numbers are: [945, 1575, 2205, 2835, 3465, 4095, 4725, 5355, 5775, 5985, 6435, 6615, 6825, 7245, 7425, 7875, 8085, 8415, 8505, 8925, 9135, 9555, 9765, 10395, 11655, 12285, 12705, 12915, 13545, 14175, 14805, 15015, 15435, 16065, 16695, 17325, 17955, 18585, 19215, 19305] First 40 odd zumkeller numbers that don't end in a 5 are: [81081, 153153, 171171, 189189, 207207, 223839, 243243, 261261, 279279, 297297, 351351, 459459, 513513, 567567, 621621, 671517, 729729, 742203, 783783, 793611, 812889, 837837, 891891, 908523, 960687, 999999, 1024947, 1054053, 1072071, 1073709, 1095633, 1108107, 1145529, 1162161, 1198197, 1224531, 1270269, 1307691, 1324323, 1378377]
Visual Basic .NET
<lang vbnet>Module Module1
Function GetDivisors(n As Integer) As List(Of Integer)
Dim divs As New List(Of Integer) From {
1, n
}
Dim i = 2
While i * i <= n
If n Mod i = 0 Then
Dim j = n \ i
divs.Add(i)
If i <> j Then
divs.Add(j)
End If
End If
i += 1
End While
Return divs
End Function
Function IsPartSum(divs As List(Of Integer), sum As Integer) As Boolean
If sum = 0 Then
Return True
End If
Dim le = divs.Count
If le = 0 Then
Return False
End If
Dim last = divs(le - 1)
Dim newDivs As New List(Of Integer)
For i = 1 To le - 1
newDivs.Add(divs(i - 1))
Next
If last > sum Then
Return IsPartSum(newDivs, sum)
End If
Return IsPartSum(newDivs, sum) OrElse IsPartSum(newDivs, sum - last)
End Function
Function IsZumkeller(n As Integer) As Boolean
Dim divs = GetDivisors(n)
Dim sum = divs.Sum()
REM if sum is odd can't be split into two partitions with equal sums
If sum Mod 2 = 1 Then
Return False
End If
REM if n is odd use 'abundant odd number' optimization
If n Mod 2 = 1 Then
Dim abundance = sum - 2 * n
Return abundance > 0 AndAlso abundance Mod 2 = 0
End If
REM if n and sum are both even check if there's a partition which totals sum / 2
Return IsPartSum(divs, sum \ 2)
End Function
Sub Main()
Console.WriteLine("The first 220 Zumkeller numbers are:")
Dim i = 2
Dim count = 0
While count < 220
If IsZumkeller(i) Then
Console.Write("{0,3} ", i)
count += 1
If count Mod 20 = 0 Then
Console.WriteLine()
End If
End If
i += 1
End While
Console.WriteLine()
Console.WriteLine("The first 40 odd Zumkeller numbers are:")
i = 3
count = 0
While count < 40
If IsZumkeller(i) Then
Console.Write("{0,5} ", i)
count += 1
If count Mod 10 = 0 Then
Console.WriteLine()
End If
End If
i += 2
End While
Console.WriteLine()
Console.WriteLine("The first 40 odd Zumkeller numbers which don't end in 5 are:")
i = 3
count = 0
While count < 40
If i Mod 10 <> 5 AndAlso IsZumkeller(i) Then
Console.Write("{0,7} ", i)
count += 1
If count Mod 8 = 0 Then
Console.WriteLine()
End If
End If
i += 2
End While
End Sub
End Module</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
Wren
I've reversed the order of the recursive calls in the last line of the isPartSum function which, as noted in the Phix entry, seems to make little difference to Go but (as one might have expected) speeds up this Wren script enormously. The first part is now near instant but was taking several minutes previously. Overall it's now only about 5.5 times slower than Go itself which is a good result for the Wren interpreter. <lang ecmascript>import "/math" for Int, Nums import "/fmt" for Fmt import "io" for Stdout
var isPartSum // recursive isPartSum = Fn.new { |divs, sum|
if (sum == 0) return true if (divs.count == 0) return false var last = divs[-1] divs = divs[0...-1] if (last > sum) return isPartSum.call(divs, sum) return isPartSum.call(divs, sum-last) || isPartSum.call(divs, sum)
}
var isZumkeller = Fn.new { |n|
var divs = Int.divisors(n)
var sum = Nums.sum(divs)
// if sum is odd can't be split into two partitions with equal sums
if (sum % 2 == 1) return false
// if n is odd use 'abundant odd number' optimization
if (n % 2 == 1) {
var abundance = sum - 2 * n
return abundance > 0 && abundance % 2 == 0
}
// if n and sum are both even check if there's a partition which totals sum / 2
return isPartSum.call(divs, sum / 2)
}
System.print("The first 220 Zumkeller numbers are:") var count = 0 var i = 2 while (count < 220) {
if (isZumkeller.call(i)) {
Fmt.write("$3d ", i)
Stdout.flush()
count = count + 1
if (count % 20 == 0) System.print()
}
i = i + 1
}
System.print("\nThe first 40 odd Zumkeller numbers are:") count = 0 i = 3 while (count < 40) {
if (isZumkeller.call(i)) {
Fmt.write("$5d ", i)
Stdout.flush()
count = count + 1
if (count % 10 == 0) System.print()
}
i = i + 2
}
System.print("\nThe first 40 odd Zumkeller numbers which don't end in 5 are:") count = 0 i = 3 while (count < 40) {
if ((i % 10 != 5) && isZumkeller.call(i)) {
Fmt.write("$7d ", i)
Stdout.flush()
count = count + 1
if (count % 8 == 0) System.print()
}
i = i + 2
} System.print()</lang>
- Output:
The first 220 Zumkeller numbers are: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 The first 40 odd Zumkeller numbers are: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377
zkl
<lang zkl>fcn properDivs(n){ // does not include n // if(n==1) return(T); // we con't care about this case
( pd:=[1..(n).toFloat().sqrt()].filter('wrap(x){ n%x==0 }) )
.pump(pd,'wrap(pd){ if(pd!=1 and (y:=n/pd)!=pd ) y else Void.Skip })
} fcn canSum(goal,divs){
if(goal==0 or divs[0]==goal) return(True);
if(divs.len()>1){
if(divs[0]>goal) return(canSum(goal,divs[1,*])); // tail recursion
else return(canSum(goal - divs[0], divs[1,*]) or canSum(goal, divs[1,*]));
}
False
} fcn isZumkellerW(n){ // a filter for a iterator
ds,sum := properDivs(n), ds.sum(0) + n;
// if sum is odd, it can't be split into two partitions with equal sums
if(sum.isOdd) return(Void.Skip);
// if n is odd use 'abundant odd number' optimization
if(n.isOdd){
abundance:=sum - 2*n;
return( if(abundance>0 and abundance.isEven) n else Void.Skip);
}
canSum(sum/2,ds) and n or Void.Skip // sum is even
}</lang> <lang zkl>println("First 220 Zumkeller numbers:"); zw:=[2..].tweak(isZumkellerW); do(11){ zw.walk(20).pump(String,"%4d ".fmt).println() }
println("\nFirst 40 odd Zumkeller numbers:"); zw:=[3..*, 2].tweak(isZumkellerW); do(4){ zw.walk(10).pump(String,"%5d ".fmt).println() }
println("\nThe first 40 odd Zumkeller numbers which don't end in 5 are:"); zw:=[3..*, 2].tweak(fcn(n){ if(n%5) isZumkellerW(n) else Void.Skip }); do(5){ zw.walk(8).pump(String,"%7d ".fmt).println() }</lang>
- Output:
First 220 Zumkeller numbers: 6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 First 40 odd Zumkeller numbers: 945 1575 2205 2835 3465 4095 4725 5355 5775 5985 6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 The first 40 odd Zumkeller numbers which don't end in 5 are: 81081 153153 171171 189189 207207 223839 243243 261261 279279 297297 351351 459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377