[Question]
  [
### Introduction
Of course, we've got a lot of [sequence](/questions/tagged/sequence "show questions tagged 'sequence'") challenges, so here is another one.
The Kimberling sequence ([A007063](http://oeis.org/A007063)) goes as following:
```
1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, ...
```
This is produced by shuffling the normal iteration:
```
[1] 2  3  4  5  6  7  8
```
The first term of the sequence is `1`. After that, we reshuffle the sequence until all the terms on the left are used. The shuffling has the pattern `right - left - right - left - ...`. Since there are no terms at the left of the `1`, there is no shuffling. We get the following:
```
 2 [3] 4  5  6  7  8  9
```
On the ith iteration, we discard the ith item and put that in our sequence. This is the **2nd** iteration, so we discard the **2nd** item. The sequence becomes: `1, 3`. For our next iteration, we are going to shuffle the current iteration with the pattern above. We take the first unused item at the right of the ith item. This happens to be `4`. We will append this to our new iteration:
```
 4
```
Now we're going to take the first unused item at the left of the ith item. This is `2`. We will append this to our new iteration:
```
 4  2
```
Since there are no items left at the left of the ith item, we'll just append the rest of the sequence to the new iteration:
```
 4  2 [5] 6  7  8  9  10  11  ...
```
This is our **3rd** iteration, so we'll discard the **3rd** item, which is `5`. This is the third item in our sequence:
```
 1, 3, 5
```
To get the next iteration, just repeat the process. I've made a gif if it isn't clear:
[![enter image description here](https://i.stack.imgur.com/5HcEJ.gif)](https://i.stack.imgur.com/5HcEJ.gif)
The gif took me longer than writing the actual post
### Task
* Given an non-negative integer **n**, output the first **n** terms of the sequence
* You may provide a function or a program
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the submission with the least amount of bytes wins!
### Test cases:
```
Input: 4
Output: 1, 3, 5, 4
Input: 8
Output: 1, 3, 5, 4, 10, 7, 15, 8
Input: 15
Output: 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28
```
**Note:** The commas in the output are not necessary. You may for example use newlines, or output a list, etc.
  
[Answer]
# Julia, ~~78~~ 71 bytes
```
n->[(i=j=x;while j<2i-3 j=i-(j%2>0?1-j:j+2)÷2;i-=1end;i+j-1)for x=1:n]
```
This is an unnamed function that accepts an integer and returns an integer array. To call it, assign it to a variable.
The approach here is the same as that described on OEIS.
Ungolfed:
```
# This computes the element of the sequence
function K(x)
    i = j = x
    while j < 2i - 3
        j = i - (j % 2 > 0 ? 1 - j : j + 2)÷2
        i -= 1
    end
    return i + j - 1
end
# This gives the first n terms of the sequence
n -> [K(i) for i = 1:n]
```
Saved 7 bytes thanks to Mauris!
[Answer]
# Pyth, 22 bytes
```
JS*3QVQ@JN=J.i>JhN_<JN
```
Try it online: [Demonstration](http://pyth.herokuapp.com/?code=JS%2A3QVQ%40JN%3DJ.i%3EJhN_%3CJN&input=10)
Simply performs the shuffling technique described in the OP. 
### Explanation:
```
JS*3QVQ@JN=J.i>JhN_<JN
JS*3Q                    assign the list [1, 2, ..., 3*input-1] to J
     VQ                  for N in range(Q):
       @JN                  print J[N]
            .i              interleave 
              >JhN             J[N+1:] with
                  _<JN         reverse J[:N]
          =J                assign the resulting list to J
```
[Answer]
# APL, ~~56~~ 44 bytes
```
{⍵<⍺+⍺-3:(⍺-1)∇⍺-4÷⍨3+(1+2×⍵)×¯1*⍵⋄⍺+⍵-1}⍨¨⍳
```
This is an unnamed monadic train that accepts an integer on the right and returns an array. It's roughly the same approach as [my Julia answer](https://codegolf.stackexchange.com/a/67569/20469).
The innermost function is a recursive dyadic function that returns the *n*th term in the Kimberling sequence, given *n* as identical left and right arguments.
```
{⍵<⍺+⍺-3:                                    ⍝ If ⍵ < 2⍺ - 3
         (⍺-1)∇⍺-4÷⍨3+(1+2×⍵)×¯1*⍵           ⍝ Recurse, incrementing a and setting
                                             ⍝ ⍵ = ⍺ - (3 + (-1)^⍵ * (1 + 2⍵))/4
                                   ⋄⍺+⍵-1}   ⍝ Otherwise return ⍺ + ⍵ - 1
```
With that in hand, we're able to get individual terms of the sequence. However, the problem then becomes that this is a *dyadic* function, meaning it requires arguments on both sides. Enter the `⍨` operator! Given a function `f` and an input `x`, `f⍨x` is the same as `x f x`. So in our case, referring to the aforementioned function as `f`, we can construct the following monadic train:
```
f⍨¨⍳
```
We apply `f` to each integer from 1 to the input, yielding an array.
Saved 12 bytes thanks to Dennis!
[Answer]
# Mathematica 130 bytes
```
(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&
```
We begin with a list consisting of the range from `1` to `3x`, where `x` is the desired number of Kimberling sequence terms.
At each step, `n`, `TakeDrop` breaks the the current list into a front list of `2n+1` terms (where the work is done) and rear list (which will be later joined with the reworked front list). The front list is matched with the following pattern, `{t___,z,r___}` where z is the Kimberling term at the center of the front list. `r` is `Riffle`'d with the reverse of `t` and then the rear list is appended. `z` is removed and appended to (`AppendTo`) the growing Kimberling sequence.
`n` is incremented by `1` and the current list is processed by the same function via `Nest.`
---
**Example**
```
(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&[100]
```
> 
> {1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33,
> 46, 53, 6, 36, 23, 2, 55, 62, 59, 76, 65, 54, 11, 34, 48, 70, 79, 99,
> 95, 44, 97, 58, 84, 25, 13, 122, 83, 26, 115, 82, 91, 52, 138, 67,
> 90, 71, 119, 64, 37, 81, 39, 169, 88, 108, 141, 38, 16, 146, 41, 21,
> 175, 158, 165, 86, 191, 45, 198, 216, 166, 124, 128, 204, 160, 12,
> 232, 126, 208, 114, 161, 156, 151, 249, 236, 263, 243, 101, 121, 72,
> 120, 47, 229}
> 
> 
> 
[Answer]
# Python 2, 76 bytes
```
for a in range(input()):
 b=a+1
 while-~b<2*a:b=a-(b^b%-2)/2;a-=1
 print a+b
```
## Explanation
This is the OEIS formula after many golf-y transformations! It worked out *beautifully*. The original code was
```
i=b=a+1
while b<2*i-3:b=i-(b+2,1-b)[b%2]/2;i-=1
print i+b-1
```
I first got rid of `i`, replacing it with `a+1` everywhere and expanding the expressions:
```
b=a+1
while b<2*a-1:b=a+1-(b+2,1-b)[b%2]/2;a-=1
print a+b
```
Then, rewrote `b<2*a-1` as `-~b<2*a` to save a byte of whitespace, and moved the `+1` into the selection, division by 2, and negation:
```
while-~b<2*a:b=a-(b,-b-1)[b%2]/2;a-=1
```
Then, `-b-1` is just `~b`, so we can write `(b,~b)[b%2]`. This is equivalent to `b^0 if b%2 else b^-1` using the XOR operator, or alternatively, `b^b%-2`.
```
while-~b<2*a:b=a-(b^b%-2)/2;a-=1
```
[Answer]
# Pyth, ~~29~~ 25 bytes
```
VQ+.W<hHyN-~tN/x%Z_2Z2hNN
```
Jakube saved 4 bytes, but I have no clue how to read the code anymore.
Here is the old solution:
```
VQKhNW<hKyN=K-~tN/x%K_2K2)+KN
```
Translation of my Python answer. I'm not very good at Pyth, so maybe there's still ways to shorten this.
```
VQ                              for N in range(input()):
  KhN                             K = N+1
     W<hKyN                       while 1+K < 2*N:
           =K-~tN/x%K_2K2)         K = (N--) - (K%-2 xor K) / 2
                          +KN     print K + N
```
]