cp's OEIS Frontend

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

%I A290801 #61 May 04 2020 16:37:05
%S A290801 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 A290801 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 A290801 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 A290801 a(n) is the least number of steps to get to n from 0 using only the operations of incrementation, decrementation, and squaring.
%C A290801 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 A290801 a(n) <= n, since applying the incrementation operation n times trivially yields n.
%C A290801 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 A290801 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 A290801 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 A290801 Ely Golden, <a href="/A290801/b290801.txt">Table of n, a(n) for n = 0..10000</a>
%H A290801 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 A290801 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 A290801 Esolang, <a href="https://esolangs.org/wiki/Deadfish">Deadfish programming language specification</a>
%H A290801 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A290801 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 A290801 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 A290801 (Python)
%o A290801 #Second program, after Mathematica code
%o A290801 from sympy.core.cache import cacheit
%o A290801 from sympy.core.power import isqrt
%o A290801 @cacheit
%o A290801 def a(n):
%o A290801     if n<4: return n
%o A290801     else:
%o A290801         s=isqrt(n)
%o A290801         return 1 + (a(s) if s**2==n else min(a(s) + n - s**2, a(s + 1) + (s + 1)**2 - n))
%o A290801 print([a(n) for n in range(91)]) # _Indranil Ghosh_, Aug 12 2017
%Y A290801 Cf. A056792.
%K A290801 nonn,look
%O A290801 0,3
%A A290801 _Ely Golden_, Aug 10 2017