The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 -> 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. LINKS Table of n, a(n) for n=0..80. 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 Sequence in context: A307727 A309081 A333251 * A334869 A326694 A053207 Adjacent sequences: A369233 A369234 A369235 * A369237 A369238 A369239 KEYWORD easy,look,nonn AUTHOR Cole Solomonson, Jan 17 2024 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 18 21:05 EDT 2024. Contains 373487 sequences. (Running on oeis4.)