1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I'm not sure this fits the topic of this site, maybe try stack overflow? $\endgroup$ – theREALyumdub Jan 9 '16 at 0:20
  • 2
    $\begingroup$ "Shortest program" questions generally go on codegolf.stackexchange.com, but this one has a sufficiently mathematical flavour that I think it fits better here. $\endgroup$ – user856 Jan 9 '16 at 0:24
  • 5
    $\begingroup$ Why are you interested in this problem? Questions that involve the current year in unexplained ways always arouse suspicion that we're being asked to help cheating in an ongoing competition somewhere. $\endgroup$ – hmakholm left over Monica Jan 9 '16 at 0:27
  • 1
    $\begingroup$ x := 2016 why do more? $\endgroup$ – NoChance Jan 9 '16 at 0:56
  • 2
    $\begingroup$ You want a loop that returns: $2^{11}-2^{5}.$ $\endgroup$ – Fred Kline Jan 9 '16 at 1:05
2
$\begingroup$

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

$\endgroup$

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