OFFSET
1,3
COMMENTS
At each iteration, one may choose from one of the three operations: add 1, subtract 1, or, if the number is even, divide by two. a(n) gives the minimum number of iterations required to reach 1, starting from n.
FORMULA
log_2(n) <= a(n) <= log_2(n)*3/2.
The maximum of a(n) - log_2(n) is reached for numbers which have the binary expansion {10}*11 or 1{10}*11, where {10}* means any nonzero number of repetitions of '10'.
a(n) = A061339(n)-1. - Rémy Sigrist, Apr 22 2022
EXAMPLE
For n = 1, the value 1 is already reached, so a(1) = 0 iterations are needed.
For n = 2, one can either subtract 1 or divide by 2 to reach 1, i.e., a(2) = 1 iterations are needed.
For n = 3, one must subtract 1 twice in order to reach the goal 1 in the minimum number of a(3) = 2 steps: Initially, one cannot divide by 2 since 3 is even, and if 1 is added, to get 3 + 1 = 4, at least two divisions by 2 (for a total of 3 steps) would be needed to reach 1.
For n = 7, the fastest is to add 1 (to get 7 + 1 = 8) and then divide three times by 2, to reach 1 in the minimum number of a(7) = 4 steps.
PROG
(PARI) apply( {A353058(n, o=[n])=for(i=0, n, o[1]>1||return(i); o=Set(concat([if(n%2, [n-1, n+1], n\2)|n<-o])))}, [1..90])
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Apr 20 2022
STATUS
approved