`0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, …`

This is the Van Eck’s Sequence.

Let’s go through it step by step.

Term 1: The first term is 0. Term 2: Since we haven’t seen 0 before, the second term is 0. Term 3: Since we had seen a 0 before, one step back, the third term is 1 Term 4: Since we haven’t seen a 1 before, the fourth term is 0 Term 5: Since we had seen a 0 before, two steps back, the fifth term is 2. And so on…

Your task is to find the n_th number in Van Eck’s Sequence. (1-based)

## The Solution in Python

### Option 1

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````from collections import Counter c=Counter() SEQ =  for i in range(1000): n = SEQ[-1] if not c[n]: c[n]=i SEQ.append(i-c[n]) c[n]=i seq=SEQ.__getitem__ ``````

### Option 2

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````def dist(arr): for i in range (1, len(arr)): if arr[-1-i] == arr[-1]: return i return 0 def seq(n): s = [0, 0] for _ in range (n): s.append(dist(s)) return s[n-1] ``````

# Option 3

 ``````1 2 3 4 5 `````` ``````def seq(n): van, eck = , 0 while n := n - 1: van.insert(0, eck := van.index(eck, 1) if eck in van[1:] else 0) return eck ``````

## Test cases to validate the solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 `````` ``````from solution import seq import test from random import randint @test.describe("Sample tests:") def tests(): @test.it("Small numbers") def _(): s = [0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6] for i in range (len(s)): test.assert_equals(seq(i+1), s[i]) @test.it('Larger numbers') def __(): s = [3, 1, 42, 0, 5, 15, 20, 0, 4, 32, 0, 3, 11, 18, 0, 4, 7, 0, 3, 7, 3, 2, 31, 0, 6, 31, 3, 6, 3, 2, 8, 33, 0, 9, 56, 0, 3, 8, 7, 19, 0, 5, 37, 0, 3, 8, 8, 1, 46, 0, 6, 23, 0] for i in range (len(s)): test.assert_equals(seq(i+50), s[i]) @test.describe('Random tests:') def r(): def dist(arr): for i in range (1, len(arr)): if arr[-1-i] == arr[-1]: return i return 0 def ref_sol(n): s = [0, 0] for _ in range (n): s.append(dist(s)) return s[n-1] @test.it('200 random tests:') def _(): for _ in range (200): a = randint(100, 1000) exp = ref_sol(a) test.assert_equals(seq(a), exp) ``````