A082007 Triangle (an infinite binary tree) read by rows; see Comments lines for definition.

0, 1, 2, 3, 6, 9, 12, 4, 5, 7, 8, 10, 11, 13, 14, 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225, 240, 16, 17, 31, 32, 46, 47, 61, 62, 76, 77, 91, 92, 106, 107, 121, 122, 136, 137, 151, 152, 166, 167, 181, 182, 196, 197

Offset: 0

Author

N. J. A. Sloane, Oct 06 2009, based on a posting by Steve Witham (sw(AT)tiac.net) to the Math Fun Mailing List, Sep 30 2009

Keywords

• nonn
• tabf
• easy

Comments

At stage 0 we begin with the triangle L_0

.........................0

........................1.2

This has 2 nodes on the lowest level, and 2^2-1 nodes in total.

At stage 1 we construct L_1 by adding 2^2 copies of L_0 to the lowest level nodes in L_0. Thus L_1 has 3+12 = 2^4-1 nodes in total (labeled 0 to 14), with 2^3 nodes at the lowest level.

At stage 2 we construct L_2 by adding 2^4 copies of L_1 to the lowest level nodes in L_1. Thus L_2 has 15+240 = 2^8-1 nodes in total (labeled 0 to 254), with 2^(2^3-1) nodes at the lowest level.

...

At stage k we construct L_k by adding 2^(2^k) copies of L_(k-1) to the lowest level nodes in L_(k-1). Thus L_k has 2^(2^(k+1))-1 nodes in total (labeled 0 to 2^(2^(k+1))-2), with 2^(2^(k+1)-1) nodes at the lowest level.

...

From Steve Witham, Oct 08 2009: This is a special case of what's called the "Van Emde Boas layout" - see p. 203 of the Meyer et al. reference. "Split the tree in the middle, at height h/2. This breaks the tree into a top recursive subtree of height floor(h/2) and several bottom subtrees of height ceil(h/2). There are sqrt(N) bottom subtrees, each of size sqrt(N)."

Contribution from Steve Witham (sw(AT)tiac.net), Oct 13 2009: (Start)

Starting the sequence (and its index) at 1 (as in A082008) instead of 0 (as in A082007) seems more natural. This was conceived as a way to arrange a heapsort in memory to improve locality of reference. The classic Williams/Floyd heapsort also works a little more naturally when the origin is 1.

This sequence is a permutation of the integers >= 0. (End)

Moreover, the first 2^(2^n) - 1 terms are a permutation of the first 2^(2^n) - 1 nonnegative integers. - Ivan Neretin, Mar 12 2017

Examples

			The beginning of the tree:
.....................................0
....................................1.2
............................3.....6......9.....12
..........................4...5..7.8...10.11.13..14
............15.......................30......................45.......240
..........16..17...................31..32..................46..47...241.242
...18....21...24....27......33....36...39....42......48....51...54....57
19.20.22.23.25.26.28.29..34.35.37.38.40.41.43.44..49.50.52.53.55.56.58.59
etc.
(15 and 30 are children of 4, 45 and 60 are children of 5, and so on.)
Rows 0 and 1 form L_0, rows 0 through 3 form L_1, rows 0 through 7 form L_2, and so on.
		

References

• Ulrich Meyer, Peter Sanders and Jop Sibeyn, Algorithms for Memory Hierarchies: Advanced Lectures.

Links

• Ivan Neretin, Table of n, a(n) for n = 0..8190
• Steve Witham, Clumpy Heapsort. - Steve Witham (sw(AT)tiac.net), Oct 13 2009

Crossrefs

Cf. A082008, A082009.

Programs

Mathematica

w = {{0}}; Do[k = 2^Floor@Log2[n - 1]; AppendTo[w, Flatten@Table[w[[n - k]] + (2^k - 1) i, {i, 2^k}]], {n, 2, 7}]; a = Flatten@w (* Ivan Neretin, Mar 12 2017 *)

Python

from math import log
def A082007( n ):
  if n == 0: return 0
  y = 2 ** int( log( n + 1, 2 ) )
  yc = 2 ** 2 ** int( log( log( y, 2 ), 2 ) )
  yr = y / yc
  return (yc-1) * int( (n+1-y)/yr + 1 ) + A082007( yr + (n+1)%yr - 1 )
# Steve Witham (sw(AT)tiac.net), Oct 11 2009