OFFSET
1,2
COMMENTS
A permutation of the positive integers.
In general, suppose that L and U are complementary sequences of positive integers such that
(1) L(1)=1; and
(2) if n>1, then n=L(k) or n=U(k) for some k<n.
The tree generated by the sequence L is defined as follows:
T(0,0)=1; T(1,0)=2; T(n,2j)=L(T(n-1,j));
T(n,2j+1)=U(T(n-1,j)); for j=0,1,...,2^(n-1)-1, n>=2.
The numbers, taken in the order generated, form a permutation of the positive integers.
LINKS
FORMULA
Let L(n) be the n-th triangular number (A000217).
Let U(n) be the n-th non-triangular number (A014132).
The tree-array T(n,k) is then given by rows:
T(0,0)=1; T(1,0)=2;
T(n,2j)=L(T(n-1,j));
T(n,2j+1)=U(T(n-1,j));
for j=0,1,...,2^(n-1)-1, n>=2.
a(1) = 1; after which: a(2n) = A014132(a(n)), a(2n+1) = A000217(a(n+1)). - Antti Karttunen, May 20 2015
EXAMPLE
First levels of the tree:
1
|
...................2...................
3 4
6......../ \........5 10......./ \........7
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
21 9 15 8 55 14 28 11
231 27 45 13 120 20 36 12 1540 65 105 19 406 35 66 16
Beginning with 3 and 4, the numbers are generated in pairs, such as (3,4), (6,5), (10,7), (21,9),...
MATHEMATICA
tr[n_]:=n*(n+1)/2; nt[n_]:= n+Round@ Sqrt[2*n]; a[1]=1; a[n_Integer] := a[n] = If[ EvenQ@n, nt@a[n/2], tr@ a@ Ceiling[n/2]]; a/@Range[58] (* Giovanni Resta, May 20 2015 *)
PROG
(Haskell)
a183079 n k = a183079_tabf !! (n-1) !! (k-1)
a183079_row n = a183079_tabf !! n
a183079_tabf = [1] : iterate (\row -> concatMap f row) [2]
where f x = [a000217 x, a014132 x]
a183079_list = concat a183079_tabf
-- Reinhard Zumkeller, Dec 12 2012
(Scheme, with memoizing definec-macro)
(definec (A183079 n) (cond ((<= n 1) n) ((even? n) (A014132 (A183079 (/ n 2)))) (else (A000217 (A183079 (/ (+ n 1) 2))))))
;; Antti Karttunen, May 18 2015
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Clark Kimberling, Dec 23 2010
EXTENSIONS
Formula added to the name and a new tree illustration to the Example section by Antti Karttunen, May 20 2015
STATUS
approved