OFFSET
0,3
COMMENTS
a(n) is the shortest number of commands, excluding the output command, to write the number n in the esoteric programming language Deadfish (see link Deadfish programming language specification for more information), ignoring the rule of setting n to zero if n ever equals 256.
a(n) <= n, since applying the incrementation operation n times trivially yields n.
a(n+1) <= a(n)+1, a(n-1) <= a(n)+1, and a(n^2) <= a(n)+1. This is because it is always possible to apply some valid operation to a series of valid operations that yields n in order to yield n+1, n-1, or n^2, respectively.
These also imply that |a(n+1)-a(n)| <= 1, since a(n-1) <= a(n)+1 implies a(n) <= a(n+1)+1 implies -a(n+1) <= 1-a(n) implies a(n+1) >= a(n)-1. Therefore the first differences of this sequence will always be -1, 0, or 1.
For n >= 4, at least one squaring operation must be used in the sequence of length a(n) yielding n. This is because using only incrementation or decermentation yields a sequence at least as long as n, but a(4) < 4, and because a(n+1) <= a(n)+1, thus a(n) < n for n >= 4, which leads to a contradiction.
LINKS
EXAMPLE
a(5) = 4 since increment(square(increment(increment(0)))) is the shortest possible sequence of increment, decrement, or square operations which results in 5, and this sequence has 4 operations.
MATHEMATICA
a[n_] := a[n] = If[n < 4, n, Block[{s = Floor@ Sqrt@ n}, 1 + If[s^2 == n, a[s], Min[a[s] + n - s^2, a[s + 1] + (s + 1)^2 - n]]]]; Array[a, 90, 0] (* Giovanni Resta, Aug 11 2017 *)
PROG
(Python)
#Second program, after Mathematica code
from sympy.core.cache import cacheit
from sympy.core.power import isqrt
@cacheit
def a(n):
if n<4: return n
else:
s=isqrt(n)
return 1 + (a(s) if s**2==n else min(a(s) + n - s**2, a(s + 1) + (s + 1)**2 - n))
print([a(n) for n in range(91)]) # Indranil Ghosh, Aug 12 2017
CROSSREFS
KEYWORD
nonn,look
AUTHOR
Ely Golden, Aug 10 2017
STATUS
approved