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

%I #16 Dec 13 2015 07:05:12

%S 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,

%T 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,

%U 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

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

%C 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)).

%C T(n,k) = A050600(n+k,k) - 1. - _Reinhard Zumkeller_, Aug 03 2014

%H Reinhard Zumkeller, <a href="/A080080/b080080.txt">Rows n=1..150 of triangle, flattened</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%e Triangle begins:

%e 1

%e 0 1

%e 2 1 1

%e 0 0 0 1

%e 1 0 3 1 1

%e 0 2 2 1 1 1

%e 3 2 2 1 2 1 1

%o (Haskell)

%o import Data.Bits (xor, (.&.), shiftL)

%o a080080 :: Int -> Int -> Int

%o a080080 n k = addc n k 0 where

%o addc x y z | y == 0 = z - 1

%o | otherwise = addc (x `xor` y) (shiftL (x .&. y) 1) (z + 1)

%o a080080_row n = map (a080080 n) [1..n]

%o a080080_tabl = map a080080_row [1..]

%o -- _Reinhard Zumkeller_, Apr 22 2013

%Y Cf. A050600.

%K nonn,tabl,nice

%O 1,4

%A _Reinhard Zumkeller_, Jan 26 2003