# The Kimberling Sequence

### Introduction

Of course, we've got a lot of challenges, so here is another one.

The Kimberling sequence (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:

The gif took me longer than writing the actual post

• Given an non-negative integer n, output the first n terms of the sequence
• You may provide a function or a program
• This is , 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.

• I'm working on a method using stack rotation – Cyoce Dec 24 '15 at 6:18
• @Cyoce Good luck :) – Adnan Dec 24 '15 at 22:10
• it's looking like I'll need it – Cyoce Dec 24 '15 at 23:11

# Pyth, 22 bytes

JS*3QVQ@JN=J.i>JhN_<JN


Try it online: Demonstration

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


# 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!

# 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}

# 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


# 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

• You can use .W to golf off 4 bytes: VQ+.W<hHyN-~tN/x%Z_2Z2hNN. – Jakube Dec 24 '15 at 8:26
• That's cool -- could you roughly explain how it works? – Lynn Dec 24 '15 at 13:41
• .W has the form: .W<condition><apply><start-value>. I used the start value hN, like you did in KhN. .W changes this value as long as the <condition> is true. I used the same condition as you <hHyN. The condition is a lambda-function with the parameter H, so the current value (in your code K) is H. And I also used the same <apply> statement as you, I only replaced K with Z, because the <apply> statement is a lambda-function with parameter Z. We can ignore the =K, .W handles this. It replaces the old value with the calculated one. At the end print +...N – Jakube Dec 24 '15 at 14:02

# 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.

The innermost function is a recursive dyadic function that returns the nth 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!