What is the shortest LOOP program that outputs 2016?

118 Views Asked by At

Use a minor restriction of the LOOP language described under Wikipedia's "LOOP (Programming Language)". The restriction is to eliminate constants. So, the language contains increment: $x_i++$, decrement: $x_i--$, assignment: $x_i := x_j$, sequencing and loop.

The output of the program is the final value of $x_0$, and the length of a program is the total count of increment/decrement/assignment/loop. For example, the following program has a length of 8 and outputs 34. (I use x and y instead of $x_0$ and $x_1$.)

x++
y++
y++
loop y
  loop y
    y++
    loop y
      x++

Notes:

  1. I have added the recreational-mathematics tag, as this question is similar to "Small Representations of 2016".

  2. This question is mainly for fun, but hopefully more challenging/interesting than the usual questions asking to use certain digits.

  3. As explained in Wikipedia all variables are implicitly initialized to 0.

  4. Programmers should also find this challenging.

  5. It is not an official contest, so I am not cheating!

1

There are 1 best solutions below

0
On

Totally serious answer, tongue nowhere near interior of cheek: This is trivial.

Presumably another condition is that all variables shall be initialized to $0$, since otherwise

x_0:=x_1

would work if $x_1$ is initialized properly.

The restriction that $c$ is $0$ or $1$ means that there are only finitely many programs of length no larger than $n$ using no more than $v$ variables. So it's trivial to write a Python script to calculate $L(n)$, the length of the shortest program that outputs $n$: There is such a program of length $n$. A program of length no larger than $n$ cannot assign values to more than $n$ variables. So enumerate all the programs of length less than or equal to $n$ using only the variables $x_0,\dots,x_n$, execute each one to see whether it outputs $n$ and record the length if it does.

Probably we won't get an answer for $L(2016)$ before the year 2017. Next question: Does there exist $n$ such that we can calculate $L(n)$ by this method and have it return before year $n$?