A290801 - OEIS

%I #61 May 04 2020 16:37:05

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

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

%U 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

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

%C 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.

%C a(n) <= n, since applying the incrementation operation n times trivially yields n.

%C 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.

%C 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.

%C 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.

%H Ely Golden, <a href="/A290801/b290801.txt">Table of n, a(n) for n = 0..10000</a>

%H Ely Golden, <a href="/A290801/a290801_3.txt">Table of n, a(n) for n = 0..10000 (including all operation sequences for n of length a(n))</a>

%H Ely Golden, <a href="/A290801/a290801_1.py.txt">Python program to compute a(n) as well as all valid operation sequences for n of length a(n)</a>

%H Esolang, <a href="https://esolangs.org/wiki/Deadfish">Deadfish programming language specification</a>

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%e 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.

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

%o (Python)

%o #Second program, after Mathematica code

%o from sympy.core.cache import cacheit

%o from sympy.core.power import isqrt

%o @cacheit

%o def a(n):

%o     if n<4: return n

%o     else:

%o         s=isqrt(n)

%o         return 1 + (a(s) if s**2==n else min(a(s) + n - s**2, a(s + 1) + (s + 1)**2 - n))

%o print([a(n) for n in range(91)]) # _Indranil Ghosh_, Aug 12 2017

%Y Cf. A056792.

%K nonn,look

%O 0,3

%A _Ely Golden_, Aug 10 2017