Who's next to me in the queue?

Question

Problem 4 in the 2019 BMO, Round 1 describes the following setup:

There are \$2019\$ penguins waddling towards their favourite restaurant. As the penguins arrive, they are handed tickets numbered in ascending order from \$1\$ to \$2019\$, and told to join the queue. The first penguin starts the queue. For each \$n > 1\$ the penguin holding ticket number \$n\$ finds the greatest \$m < n\$ which divides \$n\$ and enters the queue directly behind the penguin holding ticket number \$m\$. This continues until all \$2019\$ penguins are in the queue.

The second part of the question asked candidates to determine the penguins standing directly in front of, and directly behind, penguin \$33\$. This could be done by examining the patterns in the queue, considering prime factors: see the online video solutions for more information.

---

The Challenge

Your task is to design a program or function which, given a positive integer \$k\$ representing the penguin with ticket number \$k\$, outputs the ticket numbers of the penguins directly before and after this penguin.

For example, penguin \$33\$, stands directly behind \$1760\$ and directly in front of \$99\$, so the program should output, in some reasonable format, \$[1760, 99]\$.

---

Rules

• The input will be an integer in the range \$1 < k \le 2019\$.
• Your program should output two integers, in any reasonable format, representing the ticket numbers of the penguins before and after.
• These can be output in any order, (front first or behind first) but this order must be consistent.
• The penguin will not be at the front or back of the queue: so you don't have to handle the edge cases of \$k = 1\$ or \$k = 1024\$.
• As penguins find it difficult to read human glyphs, your program should be as short as possible. This is a code-golf - so the shortest program (in bytes) wins!

---

Test Cases

These outputs are given in the format [front, behind].

33   -> [1760, 99]
512  -> [256, 1024]
7    -> [1408, 49]
56   -> [28, 112]
1387 -> [1679, 1241]
2019 -> [673, 1346]
2017 -> [1, 2011]
2    -> [1536, 4]

Answer 1

Perl 6, 79 76 71 bytes

{($!=sort {[R,] -$_,{first $_%%*,$_^..1}...1},^2020)[+(@$!...$_)X-2,0]}

Try it online!

Sorts numbers 1 to 2019 lexicographically by the reversed, negated sequence of largest divisors, then finds the neighbors. Example mappings:

1760 => (-1 -11 -55 -110 -220 -440 -880 -1760)
  33 => (-1 -11 -33)
  99 => (-1 -11 -33 -99)

In other words, the negated cumulative product of prime factors in descending order.

Answer 2

JavaScript (ES6),  105 ... 101  100 bytes

A straightforward implementation that builds the full queue and looks for the penguin with the input ticket within it.

Returns [front, behind].

k=>[eval("for(n=q=[];m=++n%2020;q.splice(q.indexOf(m),0,n))while(n%--m)q")[i=q.indexOf(k)+1],q[i-2]]

Try it online!

Commented

The code in eval() builds and returns the queue in reverse order:

for(                      // outer loop:
  n = q = [];             //   q[] = queue, n = counter (initially zero'ish)
  m = ++n % 2020;         //   increment n; set m to n mod 2020, so that we
                          //   stop when n = 2020
  q.splice(               //   after each iteration:
    q.indexOf(m), 0, n    //     insert n before m in q[] (should be *after* m to build
  )                       //     the queue from first to last, but it's shorter this way)
) while(n % --m)          //   inner loop: decrement m until it divides n
    q                     //     dummy loop statement so that q[] is returned by eval()

which gives \$q[\:]=[1024,512,...,2017,1]\$.

Wrapper code:

k => [                    // k = input
  eval("...")             // build q[]
  [i = q.indexOf(k) + 1], // return the element after k ('in front of')
  q[i - 2]                // and the element before k ('behind')
]                         //

Answer 3

Jelly, 15 bytes

⁽¥ØÆfṚNƊÞṣị"@Ø.

A monadic Link accepting an integer between 1 and 2019 * which yields a list of two integers, [in-front, behind].

* If 1 or 1024 is input the missing ticket number will be shown as 0.

Try it online!

How?

⁽¥ØÆfṚNƊÞṣị"@Ø. - Link: n
⁽¥Ø             - literal 2019
        Þ       - sort (range [1..2019]) by: 
       Ɗ        -   last three links as a monad:
   Æf           -     prime factorisation (e.g. 1100 -> [2,2,5,5,11])
     Ṛ          -     reversed
      N         -     negated
         ṣ      - split at (n)
             Ø. - literal [0,1]
            @   - with swapped arguments:
           "    -   zip with:
          ị     -     index into (1-based & modular)
                      - i.e. [last of left list, first of right list]

Answer 4

Python 2, 137 133 121 bytes

q=[1]
for n in range(2,2020):j=q.index(max(m for m in q if n%m<1))+1;q=q[:j]+[n]+q[j:]
print q[q.index(input())-1::2][:2]

Try it online!

4 bytes thx to Arnauld; 11 bytes thx to FlipTack.

Another naive implementation.

Answer 5

05AB1E, 16 15 bytes

Ž7ëLΣÒR(}ûI¡€θ¨

Port of @JonathanAllan's Jelly answer, so make sure to upvote him!
-1 byte thanks to @Grimmy.

Outputs in the order [front, behind].

Try it online or verify all test cases.

Explanation:

Ž7ë              # Push compressed integer 2019
   L             # Pop and push a list in the range [1,2019]
    Σ            # Sort this list by:
     Ò           #  Get the prime factors (with duplicates)
      R          #  Reverse it
       (         #  Negate each inner value
        }û       # After the sort: palindromize this list ([a,b,c] → [a,b,c,b,a])
          I¡     # Split this pallindromized list by the input-integer
            €θ   # For each inner list: only leave the last value
              ¨  # And remove the last value, so the pair remains
                 # (after which this pair is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž7ë is 2019.

Answer 6

C++ (clang), 288 ... 211 210 bytes

#import<queue>
#import<regex>
#define l find(begin(q),end(q)
using v=std::vector<int>;v f(int p){v q{1};for(int n=1,d,i;d=i=++n<2020;q.insert(l,d),n))for(;++i<n&d<2;)d=n%i?d:n/i;auto t=l,p);return{*++t,t[-2]};}

Try it online!

Saved 22 bytes thanks to @ceilingcat!!!!
Saved 1 byte thanks to @AZTECCO!!!!

Ungolfed:

#include <vector>
#include <algorithm>

auto f(int p)
{
    std::vector<int> q{1};
    for (int n = 2; n <= 2019; ++n)
    {
        int d = 1;
        for (int i = 2; i < n; ++i)
        {
            if (n % i == 0)
            {
                d = n / i;
                break;
            }
        }
        auto it = find(begin(q), end(q), d);
        q.insert(it, n);
    }
    auto it = find(begin(q), end(q), p);
    std::vector<int> r = {*(it + 1), *(it - 1)};
    return r;
}

Answer 7

Perl 5, 88 bytes

sub f{$_=1;for$n(2..2019){map{$n%$_ or$m=$_}1..$n/2;s/\b$m\b/$&,$n/}/(\d+),$_[0],(\d+)/}

Try it online!

Same ungolfed:

sub f {
  $_=1;                             # $_ is the comma separated queue "array string"
                                    # ...with 1 as the first penguin
  for $n (2..2019){                 # process the rest of the penguins 2-2019
    map { $n%$_ or $m=$_ } 1..$n/2; # find max $m divisible by current $n
    s/\b$m\b/$&,$n/                 # search-replace to place current $n behind $m
  }
  /(\d+),$_[0],(\d+)/               # find and return the two numbers:
                                    # the one before and the one after the input
                                    # parameter $_[0] in the $_ array string
}

Answer 8

R, 90 89 bytes

for(i in 2:2019)T=append(T,i,match(max(which(!i%%1:(i-1))),T));T[match(scan(),T)+c(-1,1)]

Try it online!

Builds up the list into T and extracts the relevant values.

As a bonus, it works for 1 and almost works for 1024, as R's 1-based indexing returns nothing for index 0 and NA for index 2020.

Answer 9

Jelly, 23 21 bytes

ḍƇṀ=⁸k⁸j
⁽¥ØRç/ṣ⁸ṪḢƭ€

Try it online!

Naïve answer that simply generates the list of penguins and finds the relevant place. A pair of links which, when called as a monad, takes an integer as its argument and returns a pair of integers indicating the penguins before and after in the list of penguins.

Answer 10

Ruby, 104 101 95 bytes

->n{*w=1;(2..2019).map{|z|w.insert(1+w.index(w.select{|x|z%x<1}.max),z)};w[w.index(n)-1,3]-[n]}

Try it online!

Answer 11

Retina 0.8.2, 109 bytes

^
2019$*_
_
$`_¶
(_+)\1+¶
$1 $&
+m`^(_+)¶((_+¶)*)\1 (_+¶)
$1¶$4$2
_+
$.&
^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Try it online! Note: Link only goes to 201 as 2019 is too slow for TIO. Explanation:

^
2019$*_

Prepend 2019 in unary.

_
$`_¶

Count from 1 to 2019.

(_+)\1+¶
$1 $&

Precede each number with its highest proper factor (except 1, which remains unchanged).

+m`^(_+)¶((_+¶)*)\1 (_+¶)
$1¶$4$2

Insert in turn each number after its highest proper factor.

_+
$.&

Convert to decimal.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Extract the predecessor and successor of the original input.

118 byte version that's fast enough to handle 2019 on TIO:

^
2019$*_
_
$`_¶
(_+)\1+\b
$.1;$.&
_
1
m{`^(\d+)¶\1;
$1¶
}`^(\d+¶)(\d+;\d+¶)
$2$1
^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Try it online! Explanation:

^
2019$*_
_
$`_¶

Prepend all of the unary numbers from 1 to 2019.

(_+)\1+\b
$.1;$.&

Convert to decimal and prepend the largest factor.

_
1

Except 1, which just becomes the first entry in the list.

m{`^(\d+)¶\1;
$1¶
}`^(\d+¶)(\d+;\d+¶)
$2$1

Bubble up each line until it finds its insertion point.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\3$
$2$4

Extract the predecessor and successor of the original input.

Answer 12

Japt, 36 bytes

1k
#É9ò2@iUaXâ n- gJÑ)ÄX
g[J1]c+UaNg

Try it

1k               assign [1] to U

#É9ò2            pass range 2...2019 to function:
     @i ...  X   insert each value in U at index:
 Ua               find max divisor of X in U:
   Xâ              divisors
      n-           sorted
         gJÑ)Ä     2nd to last

g                get elements at
 [J1]             [-1,1]
     c+UaNg       add index of 1st input in U

Answer 13

Scala, 163 bytes

n=>{val a=(2 to 2019).map(x=>(x,((1 to x/2).filter(x%_==0)).max)).foldLeft(Seq(1))((l,e)=>l.patch(l.indexOf(e._2)+1,Seq(e._1),0));val i=a indexOf n;(a(i-1),a(i+1))

Try it online!