The Kimberling Sequence

Question

Introduction

Of course, we've got a lot of sequence 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 i^th iteration, we discard the i^th 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 i^th 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 i^th 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 i^th 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

^{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, 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.

• Cyoce: I'm working on a method using stack rotation
• Adnan: @Cyoce Good luck :)
• Cyoce: it's looking like I'll need it

Answer 1

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 2

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

Answer 3

APL, (削除) 56 (削除ここまで) 44 bytes

{⍵<⍺+⍺-3:(⍺-1)∇⍺-4÷⍨3+(×ばつ⍵)×ばつ ̄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*⍵ ⍝ 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 4

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 5

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 6

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

• Jakube: You can use .W to golf off 4 bytes: VQ+.W<hHyN-~tN/x%Z_2Z2hNN.
• lynn: That's cool -- could you roughly explain how it works?
• Jakube: .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