OFFSET
0,3
COMMENTS
Each step is a free choice of either x+1 or x^2.
Finding the minimum number of steps to any number is equivalent to finding the minimum number of reverse steps (x -> x-1 or sqrt(x)) to get from n to 0. Working backwards like this, when n is not square, we can only subtract. When n is square, and n > 1, it is always optimal to take the square root for the next step. Proof: Assume there is some n = m^2, n > 1 such that it takes fewer steps to get to zero by subtracting rather than taking the square root. This implies that a(n-1) < a(m), because each of these results is only one step away. Since n > 1, n-1 cannot be a perfect square, so there will be no choice except to subtract until we reach (m-1)^2. This implies that a(n-1) is at least a((m-1)^2) + n - (m-1^2), which is strictly greater than a((m-1)^2) + 2. However, a((m-1)^2) is only one step away from a(m-1), which is only one step away (in the opposite direction) from a(m). This implies that a(m) <= a((m-1)^2) + 2 < a(n-1). This contradicts the assumption that a(n-1) < a(m), thus proving that it is always faster to take the square root when possible.
FORMULA
a(n) = a(sqrt(n)) + 1 if n is a square.
a(n) = a(n-1) + 1 if n is not a square.
EXAMPLE
a(10) = 5, because (0 + 1 + 1 + 1)^2 + 1 = 10; therefore, starting with zero, there are 4 additions and 1 squaring required to get to 10, for a total of 5 steps.
MAPLE
N:= 200: # for a(0) to a(N)
with(GraphTheory):
V:= [$0..N]:
E:= {seq([i, i+1], i=0..N-1), seq([i, i^2], i=1..floor(sqrt(N)))}:
G:= Graph(V, E):
map(t -> t[2], DijkstrasAlgorithm(G, 0)); # Robert Israel, Jan 23 2024
PROG
(Python)
k = 10 #generates k^2 terms
a = [0, 1, 2, 3]
for n in range(2, k):
a = a + list(range(a[n] + 1, a[n] + 2 * (n + 1)))
(PARI) a(n) = if(n==1, 1, my(ret=0); while(n>1, n=sqrtint(n, &r); ret+=r+1); ret); \\ Kevin Ryde, Jan 18 2024
CROSSREFS
KEYWORD
AUTHOR
Cole Solomonson, Jan 17 2024
STATUS
approved