# Who's next to me in the queue?

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 - 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]

• @game0ver It doesn't, it joined the queue behind n = 11, but then subsequent penguins whose numbers are multiples of 11 but not 33 pushed in front of it.
– Neil
Dec 8, 2019 at 22:17
• Ah, thanks, my mistake, I though that $m$ was supposed to be 1760. Dec 8, 2019 at 22:19

# Perl 6, 7976 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.

# 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:
Æ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]


# 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')
]                         //

• "straighforward" - Arnauld, 2019 :D I find this evil ^^ Dec 9, 2019 at 10:26
• @Kaddath Did you mean I find this eval? :p Dec 11, 2019 at 11:06
• Yeah but not only, the way loops are used to build and return q are really clever! Dec 11, 2019 at 12:00

# 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].

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.

• -1 using ûI¡€θ¨ (ûDIQÀÏ also works, for the same byte-count). Dec 9, 2019 at 17:38
• There's also ûʒQYsV, for a slightly weirder 15. Dec 9, 2019 at 17:48
• @Grimmy Thanks! Nice use of the palindromize builtin! And that third one is indeed weird. Took me a few looks to understand what was going on. But again pretty smart. :) Dec 9, 2019 at 18:11

# Python 2, 137133 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.

# C++ (clang), 288$$\\cdots\$$210 203 bytes

Saved a whopping 22 29 bytes thanks to ceilingcat!!!!
Saved a byte thanks to @AZTECCO!!!!

#import<bits/stdc++.h>
#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!

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;
}

• @ceilingcat Nice - thanks! :D Jul 25, 2020 at 14:14

# 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 }  # 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. # 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. # 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! # 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  # 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.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\32$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
^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\32$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.

^(.+¶)*(.+)¶(.+)(¶.+)(¶.+)*¶\32\$4


Extract the predecessor and successor of the original input.

# 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!