24
\$\begingroup\$

The non-negative integers are bored of always having the same two* neighbours, so they decide to mix things up a little. However, they are also lazy and want to stay as close as possible to their original position.

They come up with the following algorithm:

  • The first element is 0.
  • The \$n^{th}\$ element is the smallest number which is not yet present in the sequence and which is not a neighbour of the \$(n-1)^{th}\$ element.

This generates the following infinite sequence:

0,2,4,1,3,5,7,9,6,8,10,12,14,11,13,15,17,19,16,18,20,22,24,21,23,25,27,29,26,28 ...

0 is the first element. 1 is the smallest number not yet in the sequence, but it is a neighbour of 0. The next smallest number is 2, so it is the second element of the sequence. Now the remaining numbers are 1,3,4,5,6,..., but as both 1 and 3 are neighbours of 2, 4 is the third member of the sequence. As 1 is not a neighbour of 4, it can finally take its place as fourth element.

The Task

Write a function or program in as few bytes as possible which generates the above sequence.

You may

  • output the sequence infinitely,
  • take an input \$n\$ and return the \$n^{th}\$ element of the sequence, or
  • take an input \$n\$ and return the first \$n\$ elements of the sequence.

Both zero- or one-indexing is fine in case you choose one of the two latter options.

You don't need to follow the algorithm given above, any method which produces the same sequence is fine.


Inspired by Code golf the best permutation. Turns out this is A277618.
* Zero has literally only one neighbour and doesn't really care.

\$\endgroup\$

25 Answers 25

18
\$\begingroup\$

JavaScript (ES6), 13 bytes

Returns the \$n\$th term of the sequence.

n=>n-2-~++n%5

Try it online!

How?

This computes:

$$n-2+((n+2) \bmod 5)$$

           n |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 ...
-------------+--------------------------------------------------
       n - 2 | -2 -1  0  1  2  3  4  5  6  7  8  9 10 11 12 ...
 (n+2) mod 5 |  2  3  4  0  1  2  3  4  0  1  2  3  4  0  1 ...
-------------+--------------------------------------------------
         sum |  0  2  4  1  3  5  7  9  6  8 10 12 14 11 13 ...
\$\endgroup\$
8
\$\begingroup\$

Python 2, 20 bytes

lambda n:2*n%5+n/5*5

Try it online!

\$\endgroup\$
8
\$\begingroup\$

MathGolf, 5 bytes

⌠5%+⌡

Try it online!

Some nice symmetry here. Returns the nth element of the sequence.

Explanation:

⌠      Increment input by 2
 5%    Modulo by 5
   +   Add to copy of input
    ⌡  Decrement by 2
\$\endgroup\$
6
\$\begingroup\$

Jelly, 5 bytes

æ%2.+

Try it online!

Go go gadget obscure built-in!

æ%2.      Symmetric modulo 5: map [0,1,2,3,4,5,6,7,8,9] to [0,1,2,-2,-1,0,1,2,-2,-1]
    +     Add to input
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 14 bytes

#+Mod[#,5,-2]&

Try it online!

Prints the n-th, zero-indexed, integer in the sequence.

\$\endgroup\$
4
\$\begingroup\$

R, 25 23 21 bytes

-2 bytes thanks to Jo King

n=scan();n-2+(n+2)%%5

Try it online!

Outputs nth element in sequence.

\$\endgroup\$
3
\$\begingroup\$

dzaima/APL, 9 bytes

2-⍨⊢+5|2+

Port of Arnauld's answer.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pip, 14 bytes

02413@a+a//5*5

Takes \$n\$ (0-based) as a command-line argument and outputs \$a_n\$. Try it online!

Observe that \$a_{n+5} = a_n+5\$. We hard-code the first five values and offset from there.


Or, the formula everyone's using, for 12 bytes:

a-2+(a+2)%5
\$\endgroup\$
2
\$\begingroup\$

Common Lisp, 67 bytes

(defun x(n)(loop for a from 0 to n collect(+(mod(+ a 2)5)(- a 2))))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think just (defun x(n)(+(mod(+ n 2)5)(- n 2))), or (lambda(n)(+(mod(+ n 2)5)(- n 2))) is enough: returning the n-th term, rather than a sequence of terms. \$\endgroup\$ – Misha Lavrov Oct 25 '18 at 20:59
2
\$\begingroup\$

Japt, 8 bytes

U-2Ò°U%5

Japt Interpreter

A straight port of Arnauld's Javascript answer. The linked version runs through the first n elements, but if the -m flag is removed it is still valid and prints the nth element instead.

For comparison's sake, here is the naive version which implements the algorithm provided in the question:

@_aX É«NøZ}a}gNhT

I'll give an explanation for this one:

              NhT    Set N to [0]
@           }g       Get the nth element of N by filling each index with:
 _        }a          The first integer that satisfies:
  aX É                 It is not a neighbor to the previous element
      «NøZ             And it is not already in N
\$\endgroup\$
  • \$\begingroup\$ -3 bytes on your second solution, and can probably be improved further. \$\endgroup\$ – Shaggy Oct 25 '18 at 23:02
2
\$\begingroup\$

05AB1E, 5 bytes

Ì5%+Í

Port of @JoKing's MathGolf answer.

Try it online or verify the first 100 numbers.

Explanation:

Ì        # Increase the (implicit) input by 2
 5%      # Take modulo-5
   +     # Add the (implicit) input to it
    Í    # Decrease by 2 (and output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Clean, 31 bytes

The formula everyone's using.

import StdEnv
?n=n-2+(n+2)rem 5

Try it online!

Clean, 80 bytes

My initial approach, returning the first n items.

import StdEnv
$n=iter n(\l=l++[hd[i\\i<-[0..]|all((<>)i)l&&abs(i-last l)>1]])[0]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 14 bytes

n->2*n%5+n\5*5

Try it online!


Pari/GP, 14 bytes

n->n-2+(n+2)%5

Try it online!

\$\endgroup\$
2
\$\begingroup\$

J, 30 bytes

{.2}.[:,_5,./\2(i.-4 0$~])@,~]

Try it online!

Returns a list of first n numbers

This solution is obviously non-competitve, but I wanted to try an array-based method.

Explanation:

The argument is n

2 ,] - append 2 to the input

   (2,~]) 10
10 2

()@ - and use this list to:

i. - create a matrix n x 2 with the numbers in the range 0..2n-1:

   i.10 2
 0  1
 2  3
 4  5
 6  7
 8  9
10 11
12 13
14 15
16 17
18 19

4 0$~] - ~ reverses the arguments, so it is ]$4 0 - creates matrix n x 2 repeating 4 0

   4 0$~10 2
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0
4 0

- subtract the second matrix from the first one, so that the first column is "delayed" with 2 positions

   2(i.-4 0$~])@,~] 10
_4  1
_2  3
 0  5
 2  7
 4  9
 6 11
 8 13
10 15
12 17
14 19

_5,./\ traverse the matrix in non-overlapping groups of 5 rows and stitch the columns

   _5,./\2(i.-4 0$~])@,~] 10
_4 _2  0  2  4
 1  3  5  7  9

 6  8 10 12 14
11 13 15 17 19

[:, ravel the entire array

   ,_5,./\2(i.-4 0$~])@,~] 10
_4 _2 0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19

2}. - drop the first 2 numbers

   2}.,_5,./\2(i.-4 0$~])@,~] 10
0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19

{. take the first n numbers

   ({.2}.[:,_5,./\2(i.-4 0$~])@,~]) 10
0 2 4 1 3 5 7 9 6 8

J, 9 bytes

+_2+5|2+]

Try it online!

Returns the nth element.

Port of Arnauld's answer

\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 12 bytes

{-2+x+5!x+2}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ -2+x+ -> x-2- \$\endgroup\$ – ngn Nov 3 '18 at 14:01
2
\$\begingroup\$

Pepe, 65 bytes

REeeeeeeEerEeERRrEEEEEERREeeeeeEeErEEeEeErRrEEEEEEEErRrEEEEEereEE

Try it online!

Port of Jo King's answer.

\$\endgroup\$
1
\$\begingroup\$

x86 machine code, 16 bytes

00000000: 31d2 89c8 4949 4040 b305 f7f3 9201 c8c3 1...II@@........

Assembly:

section .text
	global func
func:	;function uses fastcall conventions, 1st arg in ecx, returns in eax
	;reset edx to 0 so division works
	xor edx, edx

	mov eax, ecx
	;calculate ecx (1st func arg) - 2
	dec ecx
	dec ecx

	;calculate (ecx+2) mod 5
	inc eax
	inc eax
	mov bl, 5
	div ebx
	xchg eax, edx
	
	;add (ecx-2) and ((ecx+2) mod 5), returning in eax
	add eax, ecx
	ret

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Red, 26 bytes

func[n][n + 2 % 5 + n - 2]

Try it online!

Port of Arnauld's answer

\$\endgroup\$
1
\$\begingroup\$

Excel, 17 bytes

=A1-2+MOD(A1+2,5)

Nothing smart. Implements the common formula.

\$\endgroup\$
1
\$\begingroup\$

C (gcc) POSIX, 20 bytes

f(n){n=n-2+(n+2)%5;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

QBasic, 30 bytes

INPUT x 
x=x+2 
?-4+x*2-(x\5)*5

Gives the 0-indexed entry of the list at pos x.

Try it online! (Note that ? was expanded to PRINT because the interpreter fails otherwise...)

\$\endgroup\$
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), 14 bytes

n=>2*n%5+n/5*5

Try it online!

Same logic than others answers: 1 2

\$\endgroup\$
1
\$\begingroup\$

R, 25 bytes

n=1:scan()-1;n-2+(n+2)%%5

Try it online!

Port of Robert S.'s answer (and only by adding just 4 bytes) thanks to R being excellent at handling vectors.

Outputs the first n values.

\$\endgroup\$
1
\$\begingroup\$

dc, 9 bytes

d2+5%+2-p

Try it online!

Same method as most. Duplicate top-of-stack, add 2, mod 5, add to original (duplicated earlier), subtract 2, print.

\$\endgroup\$
0
\$\begingroup\$

TI-BASIC, 11 bytes

Ans-2+remainder(Ans+2,5

Input is in Ans.
Outputs \$a(n)\$.

A simple port of the other answers.


Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.