Lynn created a stack based mini-language, the task was to generate the primes up to 500 in 60 or less operation. Here is my 55-operation password:
[0,0,2,1,4,1,0,2,1,1,4,4,4,30,0,2,0,2,0,20,10,0,3,10,2,0,3,1,0,10,3,6,6,6,6,5,4,7,5,0,7,3,10,2,0,3,20,2,1,0,3,0,3,30,2]
Try it online!
The available operations are
0 push 1
1 duplicate top of stack
2 add top two values
3 subtract
4 multiply
5 integer divide top value by second value
6 push the second value without popping it
7 swap top two values
c>7 while loop, runs until top of stack is 0
the loops ends at the first instruction >=c
0,0,2,1,4,1,0,2,1,1,4,4,4 pushes the initial number 500.
The remainder of the code is best explained inside out:
6,6,6,6,5,4,7,5 is a divisibility test. Given k and n as the top two values on the stack this calculates \$\lfloor {\lfloor {n \over k} \rfloor \cdot k \over n}\rfloor\$, which is only 1 if k divides n: Try it online!
1,0,10,3,div test,0,7,3,10,2,0,3 is a primality test, or a composite test since this returns truthy (non-zero) values for composite numbers:
1 -- duplicate n
0 -- push 1 - stack: [1, k=n, n]
-- in the next iterations of the loop,
-- the top of stack will be the inverted result
-- of the divisibility test
10 10 -- while loop:
-- runs until [0, d, n] is on the stack,
-- where d is the largest divisor of n <n
3 -- subtract top value (always 1) from k
div -- the divisibility test
0 -- push 1
7 -- swap top two values
3 -- subtract (1 - div test result)
2 -- add the top 0 to the last k
0,3 -- subtract 1
-- if the loop ended with [0, 1, n], this is now 0
-- otherwise we have a positive number
Try it online!
0,20,10,0,3,10,2,0,3,comp. test,20,2,1 generates the next prime less than n:
0 -- push 1. This means the current number is composite
-- Even if it isn't, we still want to find a prime <n
20 -- while loop. This iterates until the composite tests returns 0
10 10 -- we have an positive number on the top of the stack ...
0 3 -- by subtracting 1 until it is 0, ...
2 -- and adding this to the last prime candidate ...
-- we can get rid of it.
0 3 -- subtract 1 to get new prime candidate pc
comp -- check if pc is composite
20 -- end of loop, top of stack is now [0, p], with p prime
2 -- add 0+p
1 -- duplicate the prime, such that we store the result,
-- and can use the value to find the next prime
Try it online!
30,0,2,0,2,next prime,0,3,0,3,30,2 repeats this until the prime 2 is found:
30 30 -- while loop
0 2 -- add 1
0 2 -- add 1
np -- find the prime less than this
0 3 -- subtract 1
0 3 -- subtract 1
-- if the prime was 2, this is now 0
-- and the while loop terminates
2 -- add the 0 to the 2 to remove it
Try it online!
