A233275 -id:A233275 - cp's OEIS frontend

A307485 A permutation of the nonnegative integers: one odd, two even, four odd, eight even, etc.; extended to nonnegative integer with a(0) = 0.

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

Offset: 0

M. F. Hasler, Apr 18 2019

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.

			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.

Orap Andrew a.k.a. Dalgerok, Codeforces Round #553 - C. Problem for Nazar, on Codeforces.com, April 2019.
Index entries for sequences that are permutations of the natural numbers.

Cf. A196521, A307613 (inverse permutation), A307612 (partial sums).
Cf. A103889 (odd & even swapped), A004442 (pairs reversed: n + (-1)^n).
Odd numbers: A005408. Even numbers: A005843.
Cf. A233275 (different permutation based on entangling odd & even numbers).

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

PARI
```
A307485(n)=2*n-2^logint(n<<2+1,2)\3
```

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.)
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/4 - log(2)/2 (A196521). - Amiram Eldar, Nov 28 2023

A307613 Inverse of the permutation A307485: one odd, two even, four odd, eight even, etc; extended with a(0) = 0.

Original entry on oeis.org

0, 1, 2, 4, 3, 5, 8, 6, 9, 7, 10, 16, 11, 17, 12, 18, 13, 19, 14, 20, 15, 21, 32, 22, 33, 23, 34, 24, 35, 25, 36, 26, 37, 27, 38, 28, 39, 29, 40, 30, 41, 31, 42, 64, 43, 65, 44, 66, 45, 67, 46, 68, 47, 69, 48, 70, 49, 71, 50, 72, 51, 73, 52, 74, 53, 75, 54, 76, 55, 77

Offset: 0

M. F. Hasler, Apr 18 2019

nonn

See A307485 for further information, motivation & references.

Also, a(n) is the smallest k not yet in the sequence such that bitxor(k,a(n-1)) >= a(n-1). - Giorgos Kalogeropoulos, May 31 2019

			  Index n : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
A307485(n): 0, 1, 2, 4, 3, 5, 7, 9, 6, 8, ...
This sequence, the inverse permutation, is obtained by reading the above "from bottom to top", i.e., find the index in 2nd row, return the number above it: e.g., a(3) = 4, a(4) = 3, a(5) = 5, a(6) = 8, a(7) = 6, etc.

OEIS' Index to sequences related to permutations of the integers.

Cf. A307485 (inverse permutation), A307612 (partial sums thereof).
Cf. A103889 (odd & even swapped), A004442 (pairs reversed: n + (-1)^n).
Odd numbers: A005408. Even numbers: A005843.
Cf. A233275 (different permutation based on entangling odd & even numbers).

a[1]=1; a[n_] := a[n] = (t=1; While[BitXor[a[n-1],t] < a[n-1] || MemberQ[Array[a, n-1], t], t++]; t)
Join[{0}, Table[a[k], {k,100}]]  (* Giorgos Kalogeropoulos, May 31 2019 *)

my(A=apply(A307485,[1..99]), B=vecsort(A,,1)); for(i=1,#B,A[B[i]]==i||return(A307613=B[1..i-1]))

cp's OEIS Frontend

A307485 A permutation of the nonnegative integers: one odd, two even, four odd, eight even, etc.; extended to nonnegative integer with a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula