A260112 Minimal number of steps to get from 0 to n by (a) adding 1 or (b) multiplying by 4.

0, 1, 2, 3, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 10, 11, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 5, 6, 7, 8, 6

Offset: 0

Author

Peter Kagey, Jul 16 2015

Keywords

• nonn
• easy

Comments

a(n) = (Weight of quaternary expansion of n) + (length of quaternary expansion of n) - 1.

Examples

			For a(308) = 9, the nine steps are: 308 => 77 => 76 => 19 => 18 => 17 => 16 => 4 => 1 => 0.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..10000

Crossrefs

Analogous sequences with a different multiplier k: A056792 (k=2), A061282 (k=3).

Cf. A053737, A110591, A007090: base 4 sequences.

Programs

Haskell

c i = if i `mod` 4 == 0 then i `div` 4 else i - 1
b 0 foldCount = foldCount
b sheetCount foldCount = b (c sheetCount) (foldCount + 1)
a260112 n = b n 0 -- Peter Kagey, Sep 02 2015

Maple

a:= n-> (l-> nops(l)+add(i, i=l)-1)(convert(n, base, 4)):
seq(a(n), n=0..105);  # Alois P. Heinz, Jul 16 2015

PARI

a(n)=sumdigits(n,4)+#digits(n,4)-1 \\ Charles R Greathouse IV, Jul 16 2015

Ruby

def a(n); n.to_s(4).length + n.to_s(4).split('').map(&:to_i).reduce(:+) - 1 end

Formula

a(n) = A053737(n) + A110591(n) - 1. - Michel Marcus, Jul 17 2015