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 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"
 