A290801 a(n) is the least number of steps to get to n from 0 using only the operations of incrementation, decrementation, and squaring.

0, 1, 2, 3, 3, 4, 5, 6, 5, 4, 5, 6, 7, 7, 6, 5, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 7, 8, 9, 10, 11, 12, 13, 12, 11, 10, 9, 8, 7, 8, 9, 10, 11, 12, 13, 14, 13, 12, 11, 10, 9, 8, 7, 6, 7, 8, 9, 10, 11, 12, 13, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 6, 7, 8, 9, 10, 11, 12, 13

Offset: 0

Author

Ely Golden, Aug 10 2017

Keywords

• nonn
• look

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.

Examples

			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.
		

Links

• Ely Golden, Table of n, a(n) for n = 0..10000
• Ely Golden, Table of n, a(n) for n = 0..10000 (including all operation sequences for n of length a(n))
• Ely Golden, Python program to compute a(n) as well as all valid operation sequences for n of length a(n)
• Esolang, Deadfish programming language specification
• Index to sequences related to the complexity of n

Crossrefs

Cf. A056792.

Programs

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

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