|
Search: id:A082007
|
|
|
| A082007 |
|
Triangle (an infinite binary tree) read by rows; see Comments lines for definition. |
|
+0 4
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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.
...
Comment from Steve Witham, Oct 08 2009: This is a special case of what's called the "Van Emde Boas layout" - see p. 203 0f 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)
|
|
REFERENCES
|
Ulrich Meyer, Peter Sanders and Jop Sibeyn, Algorithms for Memory Hierarchies: Advanced Lectures.
|
|
LINKS
|
Steve Witham, Clumpy Heapsort
Steve Witham, Clumpy Heapsort. [From Steve Witham (sw(AT)tiac.net), Oct 13 2009]
|
|
EXAMPLE
|
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.
|
|
PROGRAM
|
Contribution from Steve Witham (sw(AT)tiac.net), Oct 11 2009: (Start)
(Python)
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 )
(End)
|
|
CROSSREFS
|
Cf. A082008, A082009.
Sequence in context: A018331 A032704 A029805 this_sequence A064417 A131975 A057474
Adjacent sequences: A082004 A082005 A082006 this_sequence A082008 A082009 A082010
|
|
KEYWORD
|
nonn,tabf,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Oct 06 2009, based on a posting by Steve Witham (sw(AT)tiac.net) to the Math Fun Mailing List, Sep 30 2009
|
|
EXTENSIONS
|
Added Python function. [From Steve Witham (sw(AT)tiac.net), Oct 11 2009]
|
|
|
Search completed in 0.002 seconds
|