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,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

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

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

Cf. A056792.

Sequence in context: A331297 A322806 A332809 * A322815 A244041 A331835

Adjacent sequences: A290798 A290799 A290800 * A290802 A290803 A290804

Keyword

nonn,look

Author

Ely Golden, Aug 10 2017

Status

approved