The Jumping Up Sequence

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 xth 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.
• 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 are forbidden.
• This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Answer 1

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!

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 2

Husk, 12 bytes

Θṁṙ_1C+ḣ2tNN

Try it online!

Outputs as an infinite list. Here 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 3

Haskell, 43 bytes

0:1:3:2:5!3
a!n=a:[a-n+2..a-1]++(a+n)!(n+1)

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 4

Jelly, 15 bytes

+‘ɼṪRṙ-œ|@
0Ç¡ḣ

This is a full program that, given n, prints the first n items of the sequence.

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 5

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!

Defines a function f that takes 0-indexed n and produces the nth 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 6

Jelly,  13  10 bytes

-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! Or see a test-suite

Answer 7

Perl 5 with -pl, 70 bytes

$"="|";push@f,$;=$f[-1]+$-++,grep!/^(@f|$;)$/,0..$;for 0..$_;$_=$f[$_]

Try it online!

Answer 8

MATL, 22 bytes

1y:"t0)@+h5M:yX-h]qw:)

Outputs the first n terms of the sequence.

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 9

Haskell, 51 bytes

0:1:do(a,b)<-zip=<<(1:)$scanl(+)3[2..];b:[a+1..b-1]

Try it online!

Quite a bit longer than Lynn's Haskell answer, but the different approach might be interesting non the less.

Answer 10

Ruby, 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!

Recursive function that returns the first x numbers of the list.

Answer 11

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 12

05AB1E, 14 bytes

0)sƒ¤N+LÁ«}Ùs£

Try it online!

Answer 13

R, 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!

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

Answer 14

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

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 15

Jelly, 16 bytes

RÄṬŻk²Ḋ$ṙ€-Ø.;Fḣ

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

RÄṬŻk²Ḋ$‘ṙ€1FŻŻỤ’ḣ

Longer but different.

Answer 16

Ruby, 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!

0-indexed. Can probably be golfed down.

Answer 17

Perl 6, 52 bytes

(0,{((^max @_)∖@_).min.?key//(1+@_[*-1]+$++)}...*)

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 18

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

Given input x, output the first x "sequences"