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.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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
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
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.

License Agreements, Terms of Use, Privacy Policy. .

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