A153036 Integer parts of the full Stern-Brocot tree.

0, 1, 0, 2, 0, 0, 1, 3, 0, 0, 0, 0, 1, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Author

Reinhard Zumkeller, Dec 22 2008

Keywords

• nonn
• tabf

Examples

			a(1): 1;
a(2..3): 1x0, 2;
a(4..7): 2x0, 1x1, 3;
a(8..15): 4x0, 2x1, 1x2, 4;
a(16..31): 8x0, 4x1, 2x2, 1x3, 5;
a(32..63): 16x0, 8x1, 4x2, 2x3, 1x4, 6;
a(64..127): 32x0, 16x1, 8x2, 4x3, 2x4, 1x5, 7;
a(128..255): 64x0, 32x1, 16x2, 8x3, 4x4, 2x5, 1x6, 8;
a(256..511): 128x0, 64x1, 32x2, 16x3, 8x4, 4x5, 2x6, 1x7, 9.
		

Links

• Jon Maiga, Computer-generated formulas for A153036, Sequence Machine.
• N. J. A. Sloane, Stern-Brocot or Farey Tree
• Index entries for sequences related to Stern's sequences

Crossrefs

Cf. A130321.

If every block of terms of length 2^k is reversed, we get A290256; other permutations within these blocks give A007814 and A272729-1.

Cf. A090996, A043545, A007814, A145342.

Formula

a(n+1) = floor(A007305(n+2)/A047679(n)). [Corrected by Andrey Zabolotskiy, Jul 23 2020]

a(n) = if n=2^k-1 then k else Log2(n)-1-Log2(2^(Log2(n)+1)-(n+1)), where Log2=A000523.

From Andrey Zabolotskiy, Oct 07 2021: (Start)

Formulas discovered by Sequence Machine (and also essentially by Kevin Ryde):

a(n) = A090996(n) - A043545(n).

a(n) = A007814(A145342(n+1)). (End)

Extensions

a(0) = 0 added by Andrey Zabolotskiy, Jul 23 2020