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