|
%I #54 Nov 28 2023 10:56:42
%S 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,
%T 31,33,35,37,39,41,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,
%U 56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,43,45,47,49,51,53,55
%N A permutation of the nonnegative integers: one odd, two even, four odd, eight even, etc.; extended to nonnegative integer with a(0) = 0.
%C 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.
%H Orap Andrew a.k.a. Dalgerok, <a href="https://codeforces.com/contest/1151/problem/C">Codeforces Round #553 - C. Problem for Nazar</a>, on Codeforces.com, April 2019.
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>.
%F 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.
%F 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.
%F The 1st, 3rd, ..., (2n+1)-th block = (n+1)-th odd block starts with A007583(n) = (1, 3, 11, 43, 171, ...), n >= 0.
%F 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.
%F 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.)
%F Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/4 - log(2)/2 (A196521). - _Amiram Eldar_, Nov 28 2023
%e The first odd number is a(1) = 1,
%e the first two even numbers are a(2..3) = (2, 4),
%e the next four odd numbers are a(4..7) = (3, 5, 7, 9),
%e the next eight even numbers are a(8..15) = (6, 8, ..., 20), etc.
%e the next sixteen odd numbers are a(16..31) = (11, 13, ..., 41),
%e the next thirty-two even numbers are a(32..63) = (22, 24, ..., 84), etc.
%e the next 64 odd numbers are a(64..127) = (43, 45, ..., 169),
%e the next 128 even numbers are a(128..255) = (86, 88, ..., 340), etc.
%t 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 *)
%o (PARI) A307485(n)=2*n-2^logint(n<<2+1,2)\3
%Y Cf. A196521, A307613 (inverse permutation), A307612 (partial sums).
%Y Cf. A103889 (odd & even swapped), A004442 (pairs reversed: n + (-1)^n).
%Y Odd numbers: A005408. Even numbers: A005843.
%Y Cf. A233275 (different permutation based on entangling odd & even numbers).
%K nonn,easy
%O 0,3
%A _M. F. Hasler_, Apr 18 2019
|
