A353058 Minimum number of iterations {add or subtract 1, or half if even} needed to reach 1, starting from n.

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, 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, 8, 8, 8, 7, 8, 8, 9, 8, 9, 8, 8, 7, 8, 8, 9, 8, 9, 9, 9, 8

Offset: 1

Author

M. F. Hasler, Apr 20 2022

Keywords

• nonn

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.

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.

Examples

			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.
		

Links

• Index to sequences related to the complexity of n

Crossrefs

Cf. A003313 (shortest addition chain), A137813 (minimal set with n-topology), A128998 (shortest addition-subtraction chain).

Programs

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])

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