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

 Abundant odd numbers
 Abundant, deficient and perfect number classifications
 Proper divisors , Factors of an integer
 
/* 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"
 