A082007 - OEIS

%I #21 Nov 18 2024 22:32:02

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

%T 165,180,195,210,225,240,16,17,31,32,46,47,61,62,76,77,91,92,106,107,

%U 121,122,136,137,151,152,166,167,181,182,196,197

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

%C At stage 0 we begin with the triangle L_0

%C .........................0

%C ........................1.2

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

%C At stage 1 we construct L_1 by adding 2^2 copies of L_0 to

%C the lowest level nodes in L_0. Thus L_1 has 3+12 = 2^4-1

%C nodes in total (labeled 0 to 14), with 2^3 nodes at the lowest level.

%C At stage 2 we construct L_2 by adding 2^4 copies of L_1 to

%C the lowest level nodes in L_1. Thus L_2 has 15+240 = 2^8-1

%C nodes in total (labeled 0 to 254), with 2^(2^3-1) nodes at the lowest level.

%C ...

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

%C ...

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

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

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

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

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

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

%H Ivan Neretin, <a href="/A082007/b082007.txt">Table of n, a(n) for n = 0..8190</a>

%H Steve Witham, <a href="http://www.tiac.net/~sw/2009/10/Clumpy_heapsort/">Clumpy Heapsort</a>. [From Steve Witham (sw(AT)tiac.net), Oct 13 2009]

%e The beginning of the tree:

%e .....................................0

%e ....................................1.2

%e ............................3.....6......9.....12

%e ..........................4...5..7.8...10.11.13..14

%e ............15.......................30......................45.......240

%e ..........16..17...................31..32..................46..47...241.242

%e ...18....21...24....27......33....36...39....42......48....51...54....57

%e 19.20.22.23.25.26.28.29..34.35.37.38.40.41.43.44..49.50.52.53.55.56.58.59

%e etc.

%e (15 and 30 are children of 4, 45 and 60 are children of 5, and so on.)

%e Rows 0 and 1 form L_0, rows 0 through 3 form L_1, rows 0 through 7 form L_2, and so on.

%t 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 *)

%o (Python)

%o from math import log

%o def A082007( n ):

%o   if n == 0: return 0

%o   y = 2 ** int( log( n + 1, 2 ) )

%o   yc = 2 ** 2 ** int( log( log( y, 2 ), 2 ) )

%o   yr = y / yc

%o   return (yc-1) * int( (n+1-y)/yr + 1 ) + A082007( yr + (n+1)%yr - 1 )

%o # Steve Witham (sw(AT)tiac.net), Oct 11 2009

%Y Cf. A082008, A082009.

%K nonn,tabf,easy

%O 0,3

%A _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