A030308 Triangle T(n, k): Write n in base 2, reverse order of digits, to get the n-th row.

0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• base
• easy
• tabf

Comments

This is the quite common, so-called "bittest" function, see PARI code. - M. F. Hasler, Jul 21 2013

For a given number m and a digit position k the corresponding sequence index n can be calculated by n(m, k) = m*(1 + floor(log_2(m))) - 2^(1 + floor(log_2(m))) + k + 1. For example: counted from right to left, the second digit of m = 13 (binary 1101) is '0'. Hence the sequence index is n = n(13, 2) = 39. - Hieronymus Fischer, May 05 2007

A070939(n) is the length of n-th row; A000120(n) is the sum of n-th row; A030101(n) is the n-th row seen as binary number; A000035(n) = T(n, 0). - Reinhard Zumkeller, Jun 17 2012

Examples

			Triangle begins :
0
1
0, 1
1, 1
0, 0, 1
1, 0, 1
0, 1, 1
1, 1, 1
0, 0, 0, 1
1, 0, 0, 1 - _Philippe Deléham_, Oct 12 2011
		

Links

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

Crossrefs

Cf. A030190.

Cf. A030341, A030386, A031235, A030567, A031007, A031045, A031087, A031298 for the base-3 to base-10 analogs.

Programs

Haskell

a030308 n k = a030308_tabf !! n !! k
a030308_row n = a030308_tabf !! n
a030308_tabf = iterate bSucc [0] where
   bSucc []       = [1]
   bSucc (0 : bs) = 1 : bs
   bSucc (1 : bs) = 0 : bSucc bs
-- Reinhard Zumkeller, Jun 17 2012

Maple

A030308_row := n -> op(convert(n,base, 2)):
seq(A030308_row(n), n=0..23); # Peter Luschny, Nov 28 2017

Mathematica

Flatten[Table[Reverse[IntegerDigits[n, 2]], {n, 0, 23}]] (* T. D. Noe, Oct 12 2011 *)

PARI

A030308(n,k)=bittest(n,k) \\ Assuming that columns are numbered starting with k=0, as suggested by the formula from R. Zumkeller. - M. F. Hasler, Jul 21 2013

Python

for n in range(20): print([int(z) for z in str(bin(n)[2:])[::-1]]) # Indranil Ghosh, Mar 31 2017

Sage

A030308_row = lambda n: n.bits() if n > 0 else [0]
for n in (0..23): print(A030308_row(n)) # Peter Luschny, Nov 28 2017

Scala

(0 to 31).map(Integer.toString(, 2).reverse).mkString.split("").map(Integer.parseInt()).toList // Alonso del Arte, Feb 10 2020

Formula

a(n) = floor(m/2^(k - 1)) mod 2, where m = max(j|A001855(j) < n) and k = n - A001855(m). - Hieronymus Fischer, May 05 2007, Sep 10 2007

T(n, k) = (n // 2^k) mod 2, for 0 <= k <= log[2](n) and n > 0; T(0, 0) = 0. ('//' denotes integer division). - Peter Luschny, Apr 20 2023

Extensions

Initial 0 and better name by Philippe Deléham, Oct 12 2011