5
$\begingroup$

Here's a sequence I can't solve. It includes every number from 1-14, does not include 15 and 16, and then has a 17. I think there may be a pattern in natural number progression but can't find it.

What comes next?

2, 3, 1, 5, 7, 4, 11, 6, 8, 9, 13, 10, 17, 12, 14

Source: Crypto trading firm's interview problem from 2019

Improve this question
$\endgroup$
1
  • 8
    $\begingroup$ It's the lengths of the words at the start of my next unpublished novel: He was a quiet affable hero: essentially honest; likeable; basically self-motivated; ostensibly congregationalist, amateurishly transmogrified... $\endgroup$
    – Michael Kay
    Commented Oct 14, 2021 at 14:05

2 Answers 2

Reset to default
10
$\begingroup$

We can focus on prime numbers to solve this puzzle. We will recursively construct our sequence $(a_n)$. Let $a_1=2, a_2=3$. Having constructed $a_n$ for $n=1,...,i$ with $i>2$, let $m$ be the maximum prime number that appears among $a_1,...,a_i$ (i.e. if we let $P$ to be the set of all prime numbers, then $m=\max\{a_j\in P:1\leq j\leq i\}$). If all positive integers less than or equal to $m-2$ appears among $a_1,...,a_i$, then let $a_{i+1}=\text{smallest prime number strictly larger than } m$.

Otherwise, let $a_{i+1}=$smallest positive integer that doesn't appear among $a_1,...,a_i$. This completes our recursive construction for the sequence $(a_n)$ with $n$ being a positive integer.

We can manually check that our constructed sequence matches with your given sequence 2,3,1,... until the 15th term. Using the rule for our recursive construction we can get that 15 should come as the 16th term.

I computed upto 20th term for convenience.

$2,3,1,5,7,4,11,6,8,9,13,10,17,12,14,15,19,16,23,18$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Nice answer! I think you could make the explanation a bit more clear by showing the two distinct variants of the sequence, e.g. "2, 3, x, 5, 7, x, 11, x, x, x, 13, x, 17, x, x" and "x, x, 1, x, x, 4, x, 6, 8, 9, x, 10, x, 12, 14." This would demonstrate that both the prime and nonprime subsets of the sequence are, when taken individually, strictly increasing. $\endgroup$
    – Tim C
    Commented Oct 14, 2021 at 17:37
8
$\begingroup$

I've got an explanation that looks sensible, but doesn't quite work out at the beginning.

We can plot the sequence si:

          1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17   ► s[i]

     1       2
     2          3
     3    1
     4                5
     5                      7
     6             4
     7                                 11
     8                   6
     9                         8
    10                            9
    11                                       13
    12                              10
    13                                                   17
    14                                    12
    15                                          14

   i ▼

We can see that ...

... there are two intertwinded sequences. The first sequence has the prime numbers, the other sequence has the composite numbers. From s5 = 7, primes are picked on prime indices and composite numbers are picked on composite indices. I don't know what happens with the first four numbers, though.

Anyway, ...

... never mind the beginnings, we're interested in what comes next. The next number is s15 with the composite index 16 = 24. The next number is 15.

Improve this answer
$\endgroup$

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