Zumkeller numbers: Difference between revisions
(add task to ARM64 assembly Raspberry Pi) |
|||
Line 1,917: | Line 1,917: | ||
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377 |
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377 |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<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> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
Revision as of 01:26, 13 February 2020
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
- 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.
ARM Assembly
<lang ARM Assembly>
/* ARM assembly Raspberry PI */ /* program zumkeller.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 */ /*******************************************/ .equ STDOUT, 1 @ Linux output console .equ EXIT, 1 @ Linux syscall .equ WRITE, 4 @ Linux syscall
.equ NBDIVISORS, 100
/*******************************************/ /* Structures */ /********************************************/ /* structurea area divisors */
.struct 0
div_ident: // ident
.struct div_ident + 4
div_flag: // value 0, 1 or 2
.struct div_flag + 4
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 /*******************************************/ /* code section */ /*******************************************/ .text .global main main: @ program start
ldr r0,iAdrszMessStartPgm @ display start message bl affichageMess
ldr r0,iAdrszMessEntete @ display message bl affichageMess mov r2,#1 @ counter number mov r3,#0 @ counter zumkeller number mov r4,#0 @ counter for line display
1:
mov r0,r2 @ number mov r1,#0 @ display flag bl testZumkeller cmp r0,#1 @ zumkeller ? bne 3f @ no 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 @ carriage return at end of display line mov r0,#'\n' strb r0,[r1] mov r0,#0 strb r0,[r1,#1] @ end of display line ldr r0,iAdrsNumber @ display result message bl affichageMess mov r4,#0
2:
add r3,r3,#1 @ increment counter
3:
add r2,r2,#1 @ increment number cmp r3,#220 @ end ? blt 1b
/* odd zumkeller numbers */ ldr r0,iAdrszMessEntete1 bl affichageMess mov r2,#1 mov r3,#0 mov r4,#0
4:
mov r0,r2 @ number mov r1,#0 @ display flag 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
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 iAdrszMessEntete: .int szMessEntete iAdrszMessEntete1: .int szMessEntete1 iAdrsNumber: .int sNumber
/******************************************************************/ /* test if number is Zumkeller number */ /******************************************************************/ /* r0 contains the number */ /* r1 contains display flag (<>0: display, 0: no display ) /* r0 return 1 if Zumkeller number else return 0 */ testZumkeller:
push {r1-r8,lr} @ save registers mov r8,r0 @ save number mov r7,r1 @ save flag ldr r1,iAdrtbDivisors bl divisors @ create area of divisors cmp r0,#0 @ 0 divisors or error ? movle r0,#-1 ble 100f mov r5,r0 @ number of dividers mov r6,r1 @ number of odd dividers cmp r7,#1 @ display divisors ? bne 1f ldr r0,iAdrszMessListDivi @ yes bl affichageMess mov r0,r5 mov r1,#0 ldr r2,iAdrtbDivisors bl printHeap
1:
tst r6,#1 @ number of odd divisors is odd ? movne r0,#0 @ yes -> end bne 100f mov r0,r5 mov r1,#0 ldr r2,iAdrtbDivisors bl sumDivisors @ compute divisors sum tst r0,#1 @ sum is odd ? movne r0,#0 bne 100f @ yes -> end lsr r6,r0,#1 @ compute sum /2 mov r0,r6 @ r0 contains sum / 2 mov r1,#1 @ first heap mov r3,r5 @ number divisors mov r4,#0 @ N° element to start bl searchHeap cmp r0,#-2 beq 100f @ end cmp r0,#-1 beq 100f @ end
cmp r7,#1 @ print flag ? bne 2f ldr r0,iAdrszMessListDiviHeap bl affichageMess mov r0,r5 @ yes print divisors of first heap ldr r2,iAdrtbDivisors mov r1,#1 bl printHeap
2:
mov r0,#1 @ ok
100:
pop {r1-r8,lr} @ restaur registers bx lr @ return
iAdrtbDivisors: .int tbDivisors iAdrszMessListDiviHeap: .int szMessListDiviHeap /******************************************************************/ /* search sum divisors = sum / 2 */ /******************************************************************/ /* r0 contains sum to search */ /* r1 contains flag (1 or 2) */ /* r2 contains address of divisors area */ /* r3 contains elements number */ /* r4 contains N° element to start */ /* r0 return -2 end search */ /* r0 return -1 no heap */ /* r0 return 0 Ok */ /* recursive routine */ searchHeap:
push {r1-r8,lr} @ save registers
1:
cmp r4,r3 @ indice = elements number moveq r0,#-2 @ yes -> end beq 100f lsl r6,r4,#3 @ compute element address add r6,r2 ldr r7,[r6,#div_flag] @ flag equal ? cmp r7,#0 bne 6f ldr r5,[r6,#div_ident] cmp r5,r0 @ element value = remaining amount beq 7f @ yes bgt 6f @ too large @ too less mov r8,r0 @ save sum sub r0,r0,r5 @ new sum to find add r4,r4,#1 @ next divisors bl searchHeap @ other search cmp r0,#0 @ find -> ok beq 5f mov r0,r8 @ sum begin sub r4,r4,#1 @ prev divisors bl razFlags @ zero in all flags > current element
4:
add r4,r4,#1 @ last divisors b 1b
5:
str r1,[r6,#div_flag] @ flag -> area element flag b 100f
6:
add r4,r4,#1 @ last divisors b 1b
7:
str r1,[r6,#div_flag] @ flag -> area element flag mov r0,#0 @ search ok b 100f
8:
mov r0,#-1 @ end search
100:
pop {r1-r8,lr} @ restaur registers bx lr @ return
/******************************************************************/ /* raz flags */ /******************************************************************/ /* r0 contains sum to search */ /* r1 contains flag (1 or 2) */ /* r2 contains address of divisors area */ /* r3 contains elements number */ /* r4 contains N° element to start */ /* r5 contains sum en cours */ razFlags:
push {r0-r6,lr} @ save registers mov r0,#0
1:
cmp r4,r3 @ indice > nb elements ? bge 100f @ yes -> end lsl r5,r4,#2 add r5,r5,r2 @ compute address element ldr r6,[r5,#div_flag] @ load flag cmp r1,r6 @ equal ? streq r0,[r5,#div_flag] @ yes -> store 0 add r4,r4,#1 @ increment indice b 1b @ and loop
100:
pop {r0-r6,lr} @ restaur registers bx lr @ return
/******************************************************************/ /* compute sum of divisors */ /******************************************************************/ /* r0 contains elements number */ /* r1 contains flag (0 1 or 2) /* r2 contains address of divisors area /* r0 return divisors sum */ sumDivisors:
push {r1-r6,lr} @ save registers mov r3,#0 @ indice mov r6,#0 @ sum
1:
lsl r4,r3,#3 @ N° element * 8 add r4,r2 ldr r5,[r4,#div_flag] @ compare flag cmp r5,r1 bne 2f ldr r5,[r4,#div_ident] @ load value add r6,r6,r5 @ and add
2:
add r3,r3,#1 cmp r3,r0 blt 1b mov r0,r6 @ return sum
100:
pop {r1-r6,lr} @ restaur registers bx lr @ return
/******************************************************************/ /* print heap */ /******************************************************************/ /* r0 contains elements number */ /* r1 contains flag (0 1 or 2) */ /* r2 contains address of divisors area */ printHeap:
push {r0-r8,lr} @ save registers mov r7,r0 mov r8,r1 mov r3,#0 @ indice
1:
lsl r4,r3,#3 @ N° element * 8 add r4,r2 ldr r5,[r4,#div_flag] cmp r5,r8 bne 2f ldr r0,[r4,#div_ident] ldr r1,iAdrsValue @ and convert ascii string bl conversion10 ldr r0,iAdrszMessResult @ display result message bl affichageMess
2:
add r3,r3,#1 cmp r3,r7 blt 1b ldr r0,iAdrszCarriageReturn bl affichageMess
100:
pop {r0-r8,lr} @ restaur registers bx lr @ return
/******************************************************************/ /* divisors function */ /******************************************************************/ /* r0 contains the number */ /* r1 contains address of divisors area /* r0 return divisors number */ /* r1 return counter odd divisors */ divisors:
push {r2-r11,lr} @ save registers cmp r0,#1 @ = 1 ? movle r0,#0 ble 100f mov r7,r0 mov r8,r1 mov r11,#1 @ counter odd divisors mov r0,#1 @ first divisor = 1 str r0,[r8,#div_ident] mov r0,#0 str r0,[r8,#div_flag] tst r7,#1 @ number is odd ? addne r11,#1 mov r0,r7 @ last divisor = N add r10,r8,#8 @ store at next element str r0,[r10,#div_ident] mov r0,#0 str r0,[r10,#div_flag]
mov r6,#2 @ first divisor mov r5,#2 @ Counter divisors
2: @ begin loop
mov r0,r7 @ dividende = number mov r1,r6 @ divisor bl division cmp r3,#0 @ remainder = 0 ? bne 3f cmp r2,r6 blt 4f @ quot<divisor end lsl r10,r5,#3 @ N° element * 8 add r10,r10,r8 @ and add at area begin address str r2,[r10,#div_ident] mov r0,#0 str r0,[r10,#div_flag] add r5,r5,#1 @ increment counter cmp r5,#NBDIVISORS @ area maxi ? bge 99f tst r2,#1 addne r11,#1 @ count odd divisors cmp r2,r6 @ quotient = divisor ? ble 4f lsl r10,r5,#3 @ N° element * 8 add r10,r10,r8 @ and add at area begin address str r6,[r10,#div_ident] mov r0,#0 str r0,[r10,#div_flag] add r5,r5,#1 @ increment counter cmp r5,#NBDIVISORS @ area maxi ? bge 99f tst r6,#1 addne r11,#1 @ count odd divisors
3:
cmp r2,r6 ble 4f add r6,r6,#1 @ increment divisor b 2b @ and loop
4:
mov r0,r5 @ return divisors number mov r1,r11 @ retourn count odd divisors b 100f
99: @ error
ldr r0,iAdrszMessErrorArea bl affichageMess mov r0,#-1
100:
pop {r2-r11,lr} @ restaur registers bx lr @ return
iAdrszMessListDivi: .int szMessListDivi iAdrszMessErrorArea: .int szMessErrorArea /***************************************************/ /* ROUTINES INCLUDE */ /***************************************************/ .include "../affichage.inc" </lang>
- 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.
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 int* Bin(int n, int length);
//returns the the binary ordered subset of rank r. //Adapted from Sympy impementation. vector<int> subset_unrank_bin(vector<int>& d, int r);
vector <int> factors(int x);
bool isPrime(int number);
bool isZum(int n);
int main()
{
vector<int> zumz;
int n = 2;
cout << "The first 220 Zumkeller numbers:\n\n"; while (zumz.size() < 220) { if (isZum(n)) zumz.push_back(n); n++; } for (int i = 0; i < zumz.size(); i++) { if (i % 10 == 0) cout << endl; cout << setw(10) << zumz[i] << ' '; }
cout << "\n\nFirst 40 odd Zumkeller numbers:\n\n"; vector<int> zumz2; n = 2; while (zumz2.size() < 40) { if (n % 2 && isZum(n)) zumz2.push_back(n); n++; } for (int i = 0; i < zumz2.size(); i++) { if (i % 10 == 0) cout << endl; cout << setw(10) << zumz2[i] << ' '; }
cout << "\n\nFirst 40 odd Zumkeller numbers not ending in 5:\n\n"; vector<int> zumz3; n = 2; while (zumz3.size() < 40) { if (n % 2 && (n % 10) != 5 && isZum(n)) { zumz3.push_back(n); } n++; } for (int i = 0; i < zumz3.size(); i++) { if (i % 10 == 0) cout << endl; cout << setw(10) << zumz3[i] << ' '; }
return 0; }
//returns n in binary right justified with //length passed and padded with zeroes int* Bin(int n, int length) { int* bin, rem, i = 0;
bin = new int[length]; //array to hold result for (int i = 0; i < length; i++) //fill with zeroes bin[i] = 0; //convert n to binary and store right justified in bin while (n > 0) { rem = n % 2; n = n / 2; if (rem) bin[length - 1 - i] = 1; i++; }
return bin; }
//returns the the binary ordered subset of rank r. //Adapted from Sympy impementation. vector<int> subset_unrank_bin(vector<int>& d, int r) { vector<int> subset; int* bits; //convert r to binary array of same size as d bits = Bin(r, d.size() - 1); //get binary ordered subset for (int i = 0; i < d.size() - 1; i++) { if (bits[i]) { subset.push_back(d[i]); } }
return subset; }
vector <int> factors(int x) {
vector <int> result; int i = 1; // This will loop from 1 to int(sqrt(x)) while (i * i <= x) { // 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); } i++; } // Return the list of factors of x return result; }
bool isPrime(int number) { if (number < 2) return false; if (number == 2) return true; if (number % 2 == 0) return false; for (int i = 3; (i * i) <= number; i += 2) if (number % i == 0) return false;
return true; }
bool isZum(int n) { //if prime it ain't no zum if (isPrime(n)) return false;
//get sum of divisors
vector<int> d = factors(n);
sort(d.begin(), d.end());
int s = accumulate(d.begin(), d.end(), 0);
//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! if (n % 2 || d.size() >= 24) return true;
if (!(s % 2) && d[d.size() - 1] <= s / 2) { //using log2 prevents overflow for (int x = 2; (int)log2(x) < (d.size() - 1); x++) { vector<int> I = subset_unrank_bin(d, x); int sum = accumulate(I.begin(), I.end(), 0); if (sum == s / 2) //congratulations it's a zum num!! return true; } }
//if we get here it ain't no zum return false; }
</lang>
- Output:
The 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
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
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
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
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
Phix
<lang 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</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
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
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
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
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*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ PDaS: procedure; parse arg x 1 z 1 b; odd= x//2 /*get X & Z & B (the 1st argument).*/
if x==1 then return 1 1 /*handle special case for unity. */ r= 0; q= 1 /* [↓] ══integer square root══ ___ */ do while q<=z; q=q*4; end /*R: an integer which will be √ X */ do while q>1; q=q%4; _= z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end end /*while q>1*/ /* [↑] compute the integer sqrt 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
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
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]
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