This challenge is the first of a series of problems that should be written in the GOLF CPU. You can find the next one here

A partition of a number, N, is a list of numbers that add up to N. A prime partition is a list of prime numbers that add up to N.

For this challenge, you are given a single integer N ≥ 2. You need generate the shortest possible prime partition for N. If there are multiple possible partitions, you can print any of them.


9: [2, 7]
12: [5, 7]
95: [89, 3, 3]
337: [337]
1023749: [1023733, 13, 3]
20831531: [20831323, 197, 11]

Your program should be written in GOLF CPU. For input/output you can either use STDIO or the registers. The list can be in any order, and if you are using STDOUT, can be separated by whitespace or commas (no brackets needed). Obviously, hardcoding the solutions isn't allowed, nor is hardcoding more than the first few primes.

This is a problem, so the answer that solves the examples above with the fewest amount of cycles wins!

  • \$\begingroup\$ Time for me to promote GOLF-C, which offers a faster way to run .golf programs.. and maybe to work on it some more \$\endgroup\$
    – Claudiu
    Commented Jul 1, 2015 at 17:31
  • \$\begingroup\$ @Claudiu Golf-C would certainly be allowed here \$\endgroup\$ Commented Jul 1, 2015 at 17:32
  • 1
    \$\begingroup\$ Is there a size limit? \$\endgroup\$
    – lirtosiast
    Commented Jul 1, 2015 at 19:44
  • \$\begingroup\$ I suspect the Goldbach and Levy conjectures will come in handy here... \$\endgroup\$ Commented Jul 1, 2015 at 21:12
  • \$\begingroup\$ @ThomasKwa no, no size limit, but no hard coding primes (beyond the first couple) \$\endgroup\$ Commented Jul 1, 2015 at 21:13

2 Answers 2


Total cycles for examples: 477,918,603

Update 1: Updated to use Lemoine's conjecture.

Update 2: Updated to use the Sieve of Eratosthenes instead of naively finding the primes.

Run with:

python3 assemble.py 52489-prime-partitions.golf
python3 golf.py 52489-prime-partitions.bin x=<INPUT>

Example run:

$ python3 golf.py 52489-prime-partitions.bin x=10233
Execution terminated after 194500 cycles with exit code 0.

Cycle count for example input:

Input    Cycles
9        191
12       282
95       1,666
337      5,792
1023749  21,429,225
20831531 456,481,447

We consider the first (N+1)*8 bytes of the heap, to be an array containing N+1 64-bit values. (As the heap is limited in size, this will only work for N < 2^57). The value of the entry at i*8 indicates wether i is a prime:

Value Description
-1    Not a prime
0     Unknown
1     The largest prime found
n > 1 This is a prime and the next prime is n

When we are done building the array it will look like [-1, -1, 3, 5, -1, 7, -1, 11, -1, -1, -1, 13, ...].

We use the Sieve of Eratosthenes to build the array.

Next the program does the following in pseudo-code:

if is_prime(x):
    print x
    if is_even(x):
        for p in primes:
            if is_prime(x - p):
                print p, x - p
        if is_prime(x - 2):
            print 2, x - 2
            for p in primes:
                if is_prime(x - 2 * p):
                    print p, p, 2 * p

This is guaranteed to work because of Lemoine's conjecture and Goldbach's weak conjecture. Lemoine's conjecture hasn't be proven yet, but it's probably true for numbers below 2^57.

    call build_primes

    mov q, x
    call is_prime

    jnz print_prime, a

    and b, x, 1
    jz find_pair, b

    # Check if x - 2 is a prime
    sub q, x, 2
    call is_prime
    jnz print_prime_odd2, a

# Input: x, b
    mov p, 2
    mov d, p
    jz find_pair_even, b

    add d, d, p

    sub q, x, d

    call is_prime
    jnz print_prime2_or_3, a

    shl i, p, 3
    lw p, i
    jmp find_pair_loop

    jz print_prime2, b

    mov x, p
    call write_int_ln

    mov x, p
    call write_int_ln

    mov x, q
    call print_prime

    mov p, 2
    call print_prime2

    call write_int_ln
    halt 0

# Input: x
# Memory layout: [-1, -1, 3, 5, -1, 7, -1, 11, ...]
# x: max integer
# p: current prime
# y: pointer to last found prime
# i: current integer
    sw 0, -1
    sw 8, -1
    sw 16, 1
    mov y, 16

    mov p, 2

    mulu i, r, p, p
    jnz build_primes_final, r

    geu a, i, x
    jnz build_primes_final, a

    shl m, i, 3
    sw m, -1

    add i, i, p

    geu a, i, x
    jz build_primes_inner, a

    inc p
    shl m, p, 3
    lw a, m
    jnz build_primes_next, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_outer

    inc p
    geu a, p, x
    jnz build_primes_ret, a

    shl m, p, 3
    lw a, m
    jnz build_primes_final, a

    sw y, p
    mov y, m
    sw y, 1

    jmp build_primes_final


# Input: q
# Output: a
    shl m, q, 3
    lw a, m
    neq a, a, -1
    ret a

    divu x, m, x, 10
    jz write_int_done, x
    call write_int
    add m, m, ord("0")
    sw -1, m

    call write_int
    mov m, ord("\n")
    sw -1, m
  • \$\begingroup\$ Can you print the number of cycles for the numbers listed in the example? \$\endgroup\$ Commented Jul 7, 2015 at 12:59
  • \$\begingroup\$ @NathanMerrill Done. \$\endgroup\$
    – Tyilo
    Commented Jul 7, 2015 at 17:32

159,326,251 cycles

Input is n, output is r, s, and t (ignoring zeros).

# Input in register n
# Outputs in registers r, s, t
# (I use the return value as a debug parameter)

# hardcoded case n=2
cmp c, n, 2
jz skip_n2, c
  mov r, 2
  halt 0
# hardcoded case n=4
cmp c, n, 4
jz skip_n4, c
  mov r, 2
  mov s, 2
  halt 0

# Sieve of Eratosthenes
mov i, 1
  add i, i, 2
  lb a, i
  jnz sieve_loop, a

  mulu j, k, i, i
  geu c, j, n
  jnz end_sieve_loop, c

    sb j, 1
    add j, j, i
    lequ c, j, n
    jnz sieve_inner_loop, c

  jmp sieve_loop


lb a, n

# if n is even, skip to search
and c, n, 1
jz search, c

# if n is prime, the partition is simply [n]
jnz not_prime, a
  mov r, n
  halt 1

# if n is odd, check n-2
sub i, n, 2
lb a, i

jnz sub_3, a
# if n-2 is prime, the partition is [2, n-2]
mov r, 2
mov s, i
halt 2

# otherwise the partition is [3] + partition(n-3)
mov t, 3
sub n, n, 3

mov i, 1
sub n, n, 1

  add i, i, 2
  sub n, n, 2
  lb a, i
  jnz search_loop, a
  lb a, n
  jnz search_loop, a
  mov r, i
  mov s, n
  halt 3


robert@unity:~/golf-cpu$ ./assemble.py partition.golf
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=9
2, 7, 0
Execution terminated after 51 cycles with exit code 2.
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=12
5, 7, 0
Execution terminated after 77 cycles with exit code 3.
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=95
3, 89, 3
Execution terminated after 302 cycles with exit code 3.
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=337
337, 0, 0
Execution terminated after 1122 cycles with exit code 1.
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=1023749
13, 1023733, 3
Execution terminated after 6654139 cycles with exit code 3.
robert@unity:~/golf-cpu$ ./golf.py -p r,s,t partition.bin n=20831531
229, 20831299, 3
Execution terminated after 152670560 cycles with exit code 3.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.