The GOLF CPU Golfing Challenge: Prime Partitions

14

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.

Examples:

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!

Nathan Merrill

Posted 2015-07-01T17:13:46.723

Reputation: 13 591

Time for me to promote GOLF-C, which offers a faster way to run .golf programs.. and maybe to work on it some more

– Claudiu – 2015-07-01T17:31:52.193

@Claudiu Golf-C would certainly be allowed here – Nathan Merrill – 2015-07-01T17:32:43.307

1Is there a size limit? – lirtosiast – 2015-07-01T19:44:12.033

I suspect the Goldbach and Levy conjectures will come in handy here... – 2012rcampion – 2015-07-01T21:12:35.810

@ThomasKwa no, no size limit, but no hard coding primes (beyond the first couple) – Nathan Merrill – 2015-07-01T21:13:09.373

@NathanMerrill could you add an example requiring at least 2 primes, where all the primes are large (> 10000)? – Tyilo – 2015-07-07T22:37:51.300

@Tyilo That would require a distance of more than 10000 between two adjacent primes. I don't think anybody knows of such a prime (although it most likely exists) – Nathan Merrill – 2015-07-07T22:47:35.753

@NathanMerrill maybe I'm missing something, but why do the primes have to be adjacent? – Tyilo – 2015-07-07T23:01:36.210

@Tyilo a large prime is either the sum of 3 odd primes or 1 odd prime and 2. When given a prime you take the difference between the it and the next lowest prime (which is even), and then find two primes to add up to that number), unless the difference is 2. – Nathan Merrill – 2015-07-07T23:11:08.937

@NathanMerrill oh that makes sense, thanks. Do you think you could lower the maximum value N can have, so my second solution is valid? Do you have a specific reason why 2^63-1 must be supported? – Tyilo – 2015-07-08T04:09:07.837

@Tyilo sounds reasonable. As long as you can run the examples listed above, I'd be willing to accept the answer. – Nathan Merrill – 2015-07-08T12:41:52.193

Answers

1

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
skip_n2:
# hardcoded case n=4
cmp c, n, 4
jz skip_n4, c
  mov r, 2
  mov s, 2
  halt 0
skip_n4:

# Sieve of Eratosthenes
mov i, 1
sieve_loop:
  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

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

  jmp sieve_loop

end_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
not_prime:

# 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

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

search:
mov i, 1
sub n, n, 1

search_loop:
  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

Testcases:

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.
robert@unity:~/golf-cpu$ 

2012rcampion

Posted 2015-07-01T17:13:46.723

Reputation: 1 319

7

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
5
5
10223
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
else:
    if is_even(x):
        for p in primes:
            if is_prime(x - p):
                print p, x - p
                exit
    else:
        if is_prime(x - 2):
            print 2, x - 2
        else:
            for p in primes:
                if is_prime(x - 2 * p):
                    print p, p, 2 * p
                    exit

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
find_pair:
    mov p, 2
find_pair_loop:
    mov d, p
    jz find_pair_even, b

    add d, d, p

find_pair_even:
    sub q, x, d

    call is_prime
    jnz print_prime2_or_3, a

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

print_prime2_or_3:
    jz print_prime2, b

    mov x, p
    call write_int_ln

print_prime2:
    mov x, p
    call write_int_ln

    mov x, q
    call print_prime

print_prime_odd2:
    mov p, 2
    call print_prime2

print_prime:
    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
build_primes:
    sw 0, -1
    sw 8, -1
    sw 16, 1
    mov y, 16

    mov p, 2

build_primes_outer:
    mulu i, r, p, p
    jnz build_primes_final, r

    geu a, i, x
    jnz build_primes_final, a

build_primes_inner:
    shl m, i, 3
    sw m, -1

    add i, i, p

    geu a, i, x
    jz build_primes_inner, a

build_primes_next:
    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

build_primes_final:
    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

build_primes_ret:
    ret

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

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

write_int_ln:
    call write_int
    mov m, ord("\n")
    sw -1, m
    ret

Tyilo

Posted 2015-07-01T17:13:46.723

Reputation: 1 372

Can you print the number of cycles for the numbers listed in the example? – Nathan Merrill – 2015-07-07T12:59:58.227

@NathanMerrill Done. – Tyilo – 2015-07-07T17:32:49.570