A080080 T(n,k) = length of longest carry sequence when adding k to n in binary representation, 1 <= k <= n (triangular array).

1, 0, 1, 2, 1, 1, 0, 0, 0, 1, 1, 0, 3, 1, 1, 0, 2, 2, 1, 1, 1, 3, 2, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2, 0, 1, 0, 4, 1, 1, 0, 1, 1, 0, 0, 3, 3, 1, 1, 1, 2, 1, 1, 0, 4, 3, 3, 1, 2, 1, 1, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 4, 2, 2, 2, 2, 1, 1, 1, 3, 1, 1, 0, 3, 3, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1

Offset: 1

Author

Reinhard Zumkeller, Jan 26 2003

Keywords

• nonn
• tabl
• nice

Comments

T(n,1) = A007814(n+1), T(n,n) = 1; for n>1: T(n,n-1) = A043545(n+1); T(n,k) <= A070940(n) = T(n, A080079(n)).

T(n,k) = A050600(n+k,k) - 1. - Reinhard Zumkeller, Aug 03 2014

Examples

			Triangle begins:
              1
            0   1
          2   1   1
        0   0   0   1
      1   0   3   1   1
    0   2   2   1   1   1
  3   2   2   1   2   1   1
		

Links

• Reinhard Zumkeller, Rows n=1..150 of triangle, flattened
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A050600.

Programs

Haskell

import Data.Bits (xor, (.&.), shiftL)
a080080 :: Int -> Int -> Int
a080080 n k = addc n k 0 where
   addc x y z | y == 0    = z - 1
              | otherwise = addc (x `xor` y) (shiftL (x .&. y) 1) (z + 1)
a080080_row n = map (a080080 n) [1..n]
a080080_tabl = map a080080_row [1..]
-- Reinhard Zumkeller, Apr 22 2013