

A369236


Minimum number of steps to reach n by steps x > x+1 or x^2, starting from 0.


0



0, 1, 2, 3, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 9, 10, 4, 5, 6, 7, 8, 9, 10, 11, 12, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 > x1 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(n1) < a(m), because each of these results is only one step away. Since n > 1, n1 cannot be a perfect square, so there will be no choice except to subtract until we reach (m1)^2. This implies that a(n1) is at least a((m1)^2) + n  (m1^2), which is strictly greater than a((m1)^2) + 2. However, a((m1)^2) is only one step away from a(m1), which is only one step away (in the opposite direction) from a(m). This implies that a(m) <= a((m1)^2) + 2 < a(n1). This contradicts the assumption that a(n1) < a(m), thus proving that it is always faster to take the square root when possible.


LINKS



FORMULA

a(n) = a(sqrt(n)) + 1 if n is a square.
a(n) = a(n1) + 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..N1), 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



STATUS

approved



