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

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.

Links

Table of n, a(n) for n=1..88.

Index to sequences related to the complexity of 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

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

Sequence in context: A128998 A137813 A003313 * A277608 A117497 A117498

Adjacent sequences: A353055 A353056 A353057 * A353059 A353060 A353061

Keyword

nonn

Author

M. F. Hasler, Apr 20 2022

Status

approved