%I #18 May 06 2022 07:33:49
%S 0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,7,6,7,6,6,5,6,6,
%T 7,6,7,7,7,6,7,7,8,7,8,7,7,6,7,7,8,7,8,8,8,7,8,8,8,7,8,7,7,6,7,7,8,7,
%U 8,8,8,7,8,8,9,8,9,8,8,7,8,8,9,8,9,9,9,8
%N Minimum number of iterations {add or subtract 1, or half if even} needed to reach 1, starting from n.
%C 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.
%C This differs from A003313 (length of shortest addition chain), A128998 (length of shortest addition-subtraction chain) and A137813 (minimal set with n-topology) starting at index n = 27 where a(27) = 7 while the other three have A(27) = 6.
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F log_2(n) <= a(n) <= log_2(n)*3/2.
%F 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'.
%F a(n) = A061339(n)-1. - _Rémy Sigrist_, Apr 22 2022
%e For n = 1, the value 1 is already reached, so a(1) = 0 iterations are needed.
%e For n = 2, one can either subtract 1 or divide by 2 to reach 1, i.e., a(2) = 1 iterations are needed.
%e 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.
%e 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.
%o (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])
%Y Cf. A003313 (shortest addition chain), A137813 (minimal set with n-topology), A128998 (shortest addition-subtraction chain).
%K nonn
%O 1,3
%A _M. F. Hasler_, Apr 20 2022