|
|
A307485
|
|
A permutation of the nonnegative integers: one odd, two even, four odd, eight even, etc.; extended to nonnegative integer with a(0) = 0.
|
|
3
|
|
|
0, 1, 2, 4, 3, 5, 7, 9, 6, 8, 10, 12, 14, 16, 18, 20, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 43, 45, 47, 49, 51, 53, 55
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
The simple idea of "list the first odd number, first two even numbers, next four odd numbers, next eight even numbers..." leads to a permutation of the positive integers, which can quite naturally be extended to a permutation of the nonnegative integers, with a(0) = 0.
|
|
LINKS
|
|
|
FORMULA
|
Ignoring a(0) = 0, the k-th block (k >= 1) has 2^(k-1) terms, indexed from 2^(k-1) through 2^k-1, all having the same parity as k.
The difference between the last and the first term of this range is: a(2^k-1) - a(2^(k-1)) = 2^k - 2 = (2^(k-1) - 1)*2 = (starting index - 1) times two = ending index minus one.
The 1st, 3rd, ..., (2n+1)-th block = (n+1)-th odd block starts with A007583(n) = (1, 3, 11, 43, 171, ...), n >= 0.
The 2nd, 4th, ..., (2n+2)-th block = (n+1)-th even block starts with 2*A007583(n) = (2, 6, 22, 86, 342, ...), n >= 0, i.e., twice the starting value of the preceding odd block.
a(n) = 2*n - floor(2^k/3) where k = floor(log_2(4n+1)), n >= 0. (And 2^k == (-1)^k (mod 3) => floor(2^k/3) = (2^k-m)/3 with m = 1 if k even, m = 2 if k odd.)
|
|
EXAMPLE
|
The first odd number is a(1) = 1,
the first two even numbers are a(2..3) = (2, 4),
the next four odd numbers are a(4..7) = (3, 5, 7, 9),
the next eight even numbers are a(8..15) = (6, 8, ..., 20), etc.
the next sixteen odd numbers are a(16..31) = (11, 13, ..., 41),
the next thirty-two even numbers are a(32..63) = (22, 24, ..., 84), etc.
the next 64 odd numbers are a(64..127) = (43, 45, ..., 169),
the next 128 even numbers are a(128..255) = (86, 88, ..., 340), etc.
|
|
MATHEMATICA
|
Join[{0}, Flatten[Riffle[TakeList[Range[1, 169, 2], 2^Range[0, 6, 2]], TakeList[Range[ 2, 340, 2], 2^Range[ 1, 7, 2]]]]] (* Harvey P. Dale, Dec 17 2022 *)
|
|
PROG
|
(PARI) A307485(n)=2*n-2^logint(n<<2+1, 2)\3
|
|
CROSSREFS
|
Cf. A103889 (odd & even swapped), A004442 (pairs reversed: n + (-1)^n).
Cf. A233275 (different permutation based on entangling odd & even numbers).
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|