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

New contributor
Andrew Deluca is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ Which crypto trading firm? $\endgroup$
    – bobble
    Oct 13 at 16:37
  • 6
    $\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$ 2 days ago
9
$\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$

New contributor
mathlearner98 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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
    2 days ago
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.

$\endgroup$

Your Answer

Andrew Deluca is a new contributor. Be nice, and check out our Code of Conduct.

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.