[Question]
  [
Consider the following sequence:
```
0 1 3 2 5 4 8 6 7 12 9 10 11 17 13 14 15 16 23 ...
```
Looks pretty pattern-less, right? Here's how it works. Starting with `0`, jump up `n` integers, with `n` starting at `1`. That's the next number in the sequence. Then, append any numbers "skipped" and that haven't been seen yet in ascending order. Then, increment `n` and jump from the last number appended. Repeat this pattern.
So, for example, when we reach `11`, we're at `n=5`. We increment `n` to be `n=6`, jump up to `17`, then append `13 14 15 16` since those haven't been seen yet. Our next jump is `n=7`, so the next element in the sequence is `23`.
### The Challenge
Given input `x`, output the `x`th term of this sequence, the first `x` terms of the sequence, or build an infinite list of the terms of the sequence. You can choose 0- or 1-indexing.
## I/O and Rules
* The input and output can be given by [any convenient method](http://meta.codegolf.stackexchange.com/q/2447/42963).
* The input and output can be assumed to fit in your language's native number type.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* [Standard loopholes](http://meta.codegolf.stackexchange.com/q/1061/42963) are forbidden.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so all usual golfing rules apply, and the shortest code (in bytes) wins.
  
[Answer]
# JavaScript (ES7), 41 bytes
Returns the **n-th** term of the sequence, 0-indexed.
```
n=>(d=(n--*8-23)**.5)%1?n:'121'[n]^n-~d/2
```
[Try it online!](https://tio.run/##FYtBCsIwEADvfcUSkO4mpDaRQrFGHyIKoWlEKRtpxYvo12N7m4GZh3/7uZ/uz5fmFIYcXWZ3xOCQtZattjuSsmpoY068L4015ZkvV9a/sLU5pgkZHNQdMBzA1CsoRfApAPrEcxqHakw3FB4FqCVSIGgZVonIRF3xzX8 "JavaScript (Node.js) – Try It Online")
## How?
### Main case: \$n > 3\$
The first four terms of the sequence are special, so let's put them aside for now.
For \$n > 3\$, the sequence looks like that:
```
 n  | [4] 5 [6] 7 8 [ 9] 10 11 12 [13] 14 15 16 17 [18] 19 20 21 22 23 [24] 25 26 27 ...
----+------------------------------------------------------------------------------------
a(n)| [5] 4 [8] 6 7 [12]  9 10 11 [17] 13 14 15 16 [23] 18 19 20 21 22 [30] 24 25 26 ...
----+------------------------------------------------------------------------------------
 k  |  2  -  3  - -   4   -  -  -   5   -  -  -  -   6   -  -  -  -  -   7   -  -  - ...
```
We can notice that there are in fact two interleaved sub-sequences:
* Most values belong to the sub-sequence \$A\$ for which we simply have:
$$A(n) = n - 1$$
* Some other values belong to the sub-sequence \$B\$ (highlighted with brackets in the above diagram) whose indices follow the arithmetic sequence **3, 3, 4, 6, 9, 13, 18, 24** ... and for which we have:
$$B(n,k) = n + k - 1$$
where \$n\$ is the index in the main sequence and \$k\$ is the index in the sub-sequence \$B\$.
The indices of \$B\$ in the main sequence are given by:
$$n\_k = \frac{k^2 - k + 6}{2}$$
Given \$n\$, we know that the corresponding term in the main sequence belongs to \$B\$ if \$n\$ is an integer solution of the quadratic equation:
$$x^2 - x + 6 - 2n = 0$$
whose discriminant is:
$$\Delta = 1 - 4(6 - 2n) = 8n - 23$$
and whose positive solution is:
$$x = \frac{1 + \sqrt{\Delta}}{2}$$
We expect \$\sqrt{\Delta}\$ to be an integer. Hence the test:
```
(d = (n-- * 8 - 23) ** .5) % 1
```
### Special cases: \$0 \le n \le 3\$
For \$n < 3\$, the discriminant is negative and taking its square root results in **NaN**. For \$n = 3\$, the discriminant is \$1\$. Therefore, these first four terms of the sequence are considered to belong to the sub-sequence \$B\$.
Should we just apply our standard formula **n - ~d / 2**, we'd get:
$$-\frac 1 2, \frac 1 2, \frac 3 2, 3$$
instead of:
$$0, 1, 3, 2$$
Which is why we XOR these results with \$0,1,2\text{ and }1\$ respectively.
[Answer]
# [Husk](https://github.com/barbuz/Husk), 12 bytes
```
Θṁṙ_1C+ḣ2tNN
```
[Try it online!](https://tio.run/##yygtzv7//9yMhzsbH@6cGW/orP1wx2KjEj@///8B "Husk – Try It Online")
Outputs as an infinite list. [Here](https://tio.run/##ASEA3v9odXNr///ihpHOmOG5geG5mV8xQyvhuKMydE5O////MjA) is a version that prints the first **N**.
### Explanation
```
Θṁṙ_1C+ḣ2tNN – Full program. Takes no input, outputs to STDOUT.
         tN  – Construct the infinite list of natural numbers, starting from 2.
      +ḣ2    – And append [1, 2] to it. Yields [1,2,2,3,4,5,6,7,8,9,10,11,...].
     C     N – Cut the infinite list of positive integers into pieces of those
               sizes. Yields [[1],[2,3],[4,5],[6,7,8],[9,10,11,12],...].
 ṁ           – Map and flatten the results thereafter.
  ṙ_1        – Rotate each to the right by 1 unit.
               Yields [1,3,2,5,4,8,6,7,12,9,10,11,...]
Θ            – Prepend a 0. Yields [0,1,3,2,5,4,8,6,7,12,9,10,11,...]
```
[Answer]
# [Haskell](https://www.haskell.org/), 43 bytes
```
0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)
```
[Try it online!](https://tio.run/##BcFBCoMwEAXQfU8x2SUMkURxM5CTtF18xKoYh9B4/k7f29HPtVbr5WVJskwyyuymB5wWyBNReRwGxPxm9mANzivnYBcOpULte@hN/sa5Uk6JerDf8qnYusWltT8 "Haskell – Try It Online")
Defines an infinite list:
```
  0:1:3:2:(5!3)
≡ 0:1:3:2:5:4:(8!4)
≡ 0:1:3:2:5:4:8:6:7:(12!5)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:(17!6)
≡ 0:1:3:2:5:4:8:6:7:12:9:10:11:17:13:14:15:16:(23!7) …
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 15 bytes
```
+‘ɼṪRṙ-œ|@
0Ç¡ḣ
```
This is a full program that, given **n**, prints the first **n** items of the sequence.
[Try it online!](https://tio.run/##AScA2P9qZWxsef//K@KAmMm84bmqUuG5mS3Fk3xACjDDh8Kh4bij////MTk "Jelly – Try It Online")
### How it works
```
0Ç¡ḣ        Main link. Argument: n
0           Set the return value to 0.
 Ç¡         Call the helper link n times, first with argument 0, then n-1 times
            with the previous return value as argument.
   ḣ        Head; extract the first n items of the last return value.
+‘ɼṪRṙ-œ|@  Helper link. Argument: A (array)
 ‘ɼ         Increment the value in the register (initially 0) and yield it.
+           Add that value to all items in the sequence.
   Ṫ        Tail; extract the last item.
    R       Range; map k to [1, .., k].
     ṙ-     Rotate -1 units to the left, yielding [k, 1, ..., k-1].
       œ|@  Perform multiset union of A and the previous return value.
```
[Answer]
## C (gcc), ~~73~~ ~~67~~ 64 bytes
```
t,d;f(x){for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);t=x<4?x^x/2:x-1;}
```
[Try it online!](https://tio.run/##DYzLCsIwEEX3/YqhImRI66N05ST6IyJIxmigplIjDLT99pizORwuXNc@ncubEN3w4weYb@Iw7l7nnBomrwRnP04q2b5h2xEboaQta43SpmVRrK2URkpWTH@Rm@y7k7RHWvP7HqJCmCsolBNQISYIYOFARQa6Yq0Dwmcqi1f1lq@xbsCrgEjVmv8)
Defines a function `f` that takes 0-indexed `n` and produces the `n`th number in the sequence.
We can analyze the sequence as follows:
```
f(n)  = n   where n = 0, 1
f(2)  = 3   // 2 and 3 are swapped
f(3)  = 2
f(4)  = 5   // (+2,+3)
f(6)  = 8   // (+3,+4)
f(9)  = 12  // (+4,+5)
f(13) = 17  // (...)
...
f(n)  = n-1 // for all cases not yet covered
```
First we handle the middle section:
```
for(t=4,d=2;d<x;t+=d++)x-t||(d+=x+=d);
```
Note that the arguments on the left (4, 6, 9, 13, ...) follow a pattern: first add two, then add three, then add four, and so on. We start at `t=4` and add `d` (which starts at 2) each iteration of the loop, incrementing `d` in the process.
The body of the loop is more interesting. Remember that we want to map 4 to 5, 6 to 8, 9 to 12, etc.; that's just adding `d-1` if `x` is `t`. However, this logic comes before the last case, `f(n) = n - 1`, so we know we're going to subtract 1 at the end. Therefore, we can simply add `d` if `x == t` (`x-t||(x+=d)`). However, we will also need to break out of the loop immediately after this -- so we add *that* to `d` to get the absurd-looking `d+=x+=d`, which will always make the `d<x` condition fail.
This covers everything except for the first four values. Looking at them in binary, we get:
```
00 -> 00
01 -> 01
10 -> 11
11 -> 10
```
So, we want to flip the last bit if `2 <= x < 4`. This is accomplished with `x^x/2`. `x/2` gives the second least significant bit, so XORing this with the original number flips the last bit if the number is 2 or 3.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13~~ 10 [bytes](https://github.com/DennisMitchell/jelly)
-3 Thanks to Dennis (use 0-indexing to save 2 from cumulative sum setup and a final decrement)
```
Ḷ»2Äi+_>2$
```
A monadic link accepting an integer, **0**-indexed **n**, which returns an integer, **a(n)**
**[Try it online!](https://tio.run/##y0rNyan8///hjm2HdhsdbsnUjrczUvn//78lAA "Jelly – Try It Online")** Or see a [test-suite](https://tio.run/##y0rNyan8///hjm2HdhsdbsnUjrczUgFxD7c/alrz/7@ZKQA "Jelly – Try It Online")
[Answer]
## [Perl 5](https://www.perl.org/) with `-pl`, 70 bytes
```
$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]
```
[Try it online!](https://tio.run/##FcpLDoIwFEbh@b8Kbe4A0ha4vE3ThH0YZETVhNgGdMbarTI7@XLCvC5NJG0HZ5PURBJW7MKEz/YYnCJjyV01j5K0lOq@zuGc35LB7WRSylWRZWScX09HTIamY6dpjLEAo0SFGg1adOhxAf@RwSW4AtfgBtyCO3D/9eH99K8t6rD8AA "Perl 5 – Try It Online")
[Answer]
# [MATL](https://github.com/lmendo/MATL), 22 bytes
```
1y:"t0)@+h5M:yX-h]qw:)
```
Outputs the first `n` terms of the sequence.
[Try it online!](https://tio.run/##y00syfn/37DSSqnEQNNBO8PU16oyQjcjtrDcShMobgkA "MATL – Try It Online")
### Explanation
```
1         % Push 1
y         % Implicit input: n. Duplicate from below
":        % For each k in [1 2 ... n]
  t0)     %   Duplicate sequence so far. Get last entry, say m
  @+      %   Add k: gives m+k
  h       %   Concatenate horizontally
  5M      %   Push m+k again
  :       %   Range [1 2 ... m+k]
  y       %   Duplicate from below
  X-      %   Set difference
  h       %   Concatenate horizontally
]         % End
q         % Subtract 1, element-wise
w         % Swap. Brings original copy of n to the top
:)        % Keep the first n entries. Implicit display
```
[Answer]
# [Haskell](https://www.haskell.org/), 51 bytes
```
0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]
```
[Try it online!](https://tio.run/##BcFBEsIgDADAr@TQA0yFIXpDeEnbQ8BWmSIypqc@3rj7It7XWoXjLM6jf3wUXZIO5iw9hqDQ64EztapGfZuu1i735Cca0dpkcJE3lQYR@re0A9RB@wroHLCWX94qPVlM7v0P "Haskell – Try It Online")
Quite a bit longer than [Lynn's Haskell answer](https://codegolf.stackexchange.com/a/167325/56433), but the different approach might be interesting non the less.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 73 bytes
```
f=->x,l,n{!l[x]&&(i=l[-1];f[x,l+[i+n]+([*(i+1...i+n)]-l),n+1])||l[0...x]}
```
[Try it online!](https://tio.run/##DchBCoAgEADAr9QltF1Fo1vYR5a9dBCERSIIjOzt5nHmuo@ntRjMXlAwv6NQ4WlSKQgZz1uk/kAJMoOiWSXw1tpOzUY0ZvCsaxVyfQt/7RwiLSuSY/Tcfg "Ruby – Try It Online")
Recursive function that returns the first x numbers of the list.
[Answer]
# QBasic, 58 bytes
```
DO
b=r+j
?b
r=b
FOR x=a+1TO b-1
?x
r=x
NEXT
a=b
j=j+1
LOOP
```
Outputs indefinitely. You may want to add a `SLEEP 1` inside the loop or make it `LOOP WHILE b<100` or something like that in order to see the results.
This basically just implements the spec. Observe that the numbers we go back for will always be the numbers between the most recently jumped-to number and the jumped-to number prior to that. So we store these bounds as `a` and `b` and use a `FOR` loop to print all the numbers between them.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 14 bytes
```
0)sƒ¤N+LÁ«}Ùs£
```
[Try it online!](https://tio.run/##ASAA3/8wNWFiMWX//zApc8aSwqROK0zDgcKrfcOZc8Kj//8yMA "05AB1E – Try It Online")
[Answer]
# [R](https://www.r-project.org/), 70 bytes
```
function(e){for(i in 1:e)F=c(setdiff((F+i):1-1,F),F[1]+i,F);rev(F)[e]}
```
[Try it online!](https://tio.run/##TcsxDsIwDADAPa/wZls1Q5BYirLmE6VDFWLkJUVJgaHq2wMj2y1Xu4aur5I2Wwtl3nWtZGAF/Jg5hkQtb3dTJYqD8ehPXiJLnPw82E/Xmt8Uecrz0f/q@cK7A0jLRqiEYoIMAVCUjAVvBaXlZ0Bkd7jPUouVRyPuXw "R – Try It Online")
* 1-indexed
* -4 bytes using `F` constant thanks to @JAD suggestion
* -5 bytes reversing the list thanks to @Giuseppe suggestion
* -2 bytes removing useless braces in for loop thanks to @JAD suggestion
* -2 bytes using `setdiff` instead of `x[x %in% y]`
---
[Previous version (79 bytes)](https://tio.run/##TcyxCsMgEIDhPU9hh3B39AKxY1JXXyLNIKJwUIykdgo@u3Xs9v3Lf7ZoWvwmX@RIGOiKx4miJCm99MqmOHmjZU2rNb4j34XRPad5wc5JE203N0oa7U51tVvYa/t7PGa6BqW8KwgRgYWBlFHAEYUYXgn4E7IBoKG2Hw)
[Answer]
# [Python 2](https://docs.python.org/2/), 123 bytes
```
def f(z):[s.extend([s[-1]+n]+[x for x in range(s[-1]+1,s[-1]+n)if not x in s]) for n in range(1,z)if len(s)<z];return s    
```
[Try it online!](https://tio.run/##Rc3LCsIwEIXhV5llQqs4Lr08SchC6EQDMikzEdK8fIxtwbP9Pzjzkl@Jz03hDu7k20QBgqn24vRIJRNPxqk7oB/YD65ASAIFIoM8@ElmSzjuxMYAnPIm1NuV85/jWH/kTWzU3qq/CuWPdAp9bZbIub8j2vYF "Python 2 – Try It Online")
Given input x, output the first x terms of the sequence, 
I'm learning Python and this challenges make things more interesting.
Edit: shave some whitespace
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 16 bytes
```
RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ
```
[Try it online!](https://tio.run/##ASkA1v9qZWxsef//UsOE4bmsxbtrwrLhuIok4bmZ4oKsLcOYLjtG4bij////Ng "Jelly – Try It Online")
One byte longer than the existing Jelly answer but this could possibly be golfed a little. `RÄṬŻk²Ḋ$` could maybe be shorter.
[**18 bytes**](https://tio.run/##ATMAzP9qZWxsef//UsOE4bmsxbtrwrLhuIok4oCY4bmZ4oKsMUbFu8W74buk4oCZ4bij////MTA "Jelly – Try It Online")
```
RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ
```
Longer but different.
[Answer]
# [Ruby](https://www.ruby-lang.org/), 63 bytes
```
->x,n=0{n+=1while 0>d=n*n+n<=>2*x-6;[0,1,3,2][x]||[x+n,x-1][d]}
```
[Try it online!](https://tio.run/##BcFLCsIwEADQq4S60ebDJIIbnVwkzEJtSwMylKI4kuTs8b398/j1BbuNYhihsEb/XfNrVhAn5JE13zCGUezlmsB4czaBklCtSTQbsZ7SRK0fwbkAJzffn6sqNVe17ZnfajiUJWVqamj9Dw "Ruby – Try It Online")
0-indexed. Can probably be golfed down.
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 52 bytes
```
(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)
```
[Try it online!](https://tio.run/##K0gtyjH7n1upoFKcWmj7X8NAp1pDIy43sULBIV7zUcc0IKmXm5mnZ5@dWqmvr2Go7RAfraVrGKutoq2tWaunp6el@d@aqzgRYkB0nJFB7H8A "Perl 6 – Try It Online")
This is a generator expression using the `...` operator. It looks for gaps in the prior sequence `@_` via `((^max @_)∖@_).min.?key`:
```
      @_  # prior sequence values         [0,1,3]
  max @_  # largest prior sequence value       3
 ^        # the Range 0..max @_            0,1,2
(       )∖@_  # set subtract prior seq     -0,1  -> (2=>True)
            .min  # smallest unseen value  2=>True
                .?key  # set yields pairs  2
```
The `?` is necessary for the initial value which doesn't have a `.key`. If no gaps are found, then it adds n (here in the `$` variable) to the last value in the list, plus one for off by 0 errors.
[Answer]
# [Python 3](https://docs.python.org/3/), 104 bytes
```
def f(x):
 n=a=0
 l=list(range(x*x))
 while n<x:print(l[a+n],*l[a+2-(n<3):a+n],end=' ');a=a+n-(a>0);n+=1
```
[Try it online!](https://tio.run/##HchBCoMwEEDRfU4xO2e0gqm76PQixcWASQ2EqdhA09OntavP@/snb08da119gICFnAFl4cFA4hRfGQ/Rh8fSFiID7y0mDzoXtx9RM6a7dLpc2rPXHnUeyf2P15UbaGgS/rlHuQ00ace2BrSW6hc "Python 3 – Try It Online")
Given input x, output the first x "sequences" 
]