A082009 -id:A082009 - cp's OEIS frontend

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

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

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

			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.

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

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

Cf. A082008, A082009.

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

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

A082006 In the following square array numbers (not occurring earlier) are entered like this: a(1, 1), a(1, 2), a(2, 1), a(3, 1), a(2, 2), a(1, 3), a(1, 4), a(2, 3), a(3, 2), a(4, 1), a(5, 1), a(4, 2), ... such that every entry is coprime to the members of the row and column it belongs, with the condition that the n-th diagonal sum is a multiple of n. 1 2 7 9 31 25... 4 5 11 23 27... 3 13 8... 19 21... 17 ... ... Sequence contains numbers as they are entered.

Original entry on oeis.org

1, 2, 4, 3, 5, 7, 9, 11, 13, 19, 17, 21, 8, 23, 31, 25, 27, 29, 37, 41

Offset: 1

Amarnath Murthy, Apr 05 2003

Next term T(6,1) =a(21)> 500000, a(21) is odd. The sum of the first diagonal is 1 (a multiple of 1). The sum of the second diagonal is T(1,2)+T(2,1)=2+4=6 (a multiple of 2). The sum of the 3rd diagonal is T(1,3)+T(2,2)+T(3,1)=7+5+3=15 (a multiple of 3). The sum of the 4th diagonal is T(1,4)+T(2,3)+T(3,2)+T(4,1)=9+11+13+19=52 (a multiple of 4). The members of the first row (1,2,7,9,31,25,..) are mutually coprime. The members of the 2nd row (4,5,11,23,27,..) are mutually coprime. The members of the first column (1,4,3,19,17,..) are mutually coprime. The members of the 2nd column (2,5,13,21,..) are mutually coprime. The a(n) transverses the table in meandering fashion: first diagonal up, 2nd diagonal down, 3rd diagonal up, 4th down etc. - R. J. Mathar, May 06 2006
From Alois P. Heinz, Oct 06 2009: (Start)
T(6,1) is undefined, so there are no further terms.
For T(6,1) would be == 3 (mod 6) w.r.t. antidiagonal 6, (T(6,1)+159=6k) and it would be == 1 or == 5 (mod 6) w.r.t. column 1 (coprime to 3 & 4) which is impossible, unless backtracking is allowed and earlier elements are altered. But that is not intended by the author, because "sequence contains numbers as they are entered", and it would not make a valid definition at all. (End)

			Table is
1 2 7 9 31 25
4 5 11 23 27
3 13 8 29
19 21 37
17 41
?

Cf. A082002, A082003, A082004, A082005, A082007, A082008, A082009, A082010.

More terms from R. J. Mathar, May 06 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python