BIO prime problem

Revision en3, by fmoeran, 2023-10-26 01:41:10

Hi guys,

Here's a problem from the 2016 BIO round 1. This post is not specifically about the problem but the restring on l.

A prime number is a whole number, greater than 1, that can only be divided by itself and the number 1.
Two prime numbers are connected if the difference between them is 2n for some whole number n ≥ 0;
e.g. possible differences are 1, 2, 4, 8, 16, 32, …
A path is a sequence of (at least two) prime numbers, without repetition, where adjacent numbers in the
sequence are connected. If the first number in the sequence is p and the last number is q then we say
the path is between p and q.
The length of a path is the total number of prime numbers used. There may be multiple paths between
two prime numbers; the lengths of these paths may be different.
For example:
• 13 is connected to 5 (13 — 5 = 8 = 23), 5 is connected to 3 (5 — 3 = 2 = 21) and 3 is connected to 2
(3 — 2 = 1 = 20);
• As 13 and 5 are connected there is a path between them (13—5) whose length is 2;
• There is a path from 13 to 2 (13—5—3—2) whose length is 4;
• There is a longer path from 13 to 2 (13—17—19—3—2) whose length is 5.
You will be given an upper limit on the primes you are allowed to use. For example, if the limit was 18
then the path 13—17—19—3—2 would not be permitted as it includes a prime above this limit.
Tags national olympiad, olympiads, primes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English fmoeran 2023-10-26 01:58:36 0 (published)
en7 English fmoeran 2023-10-26 01:57:22 25 Tiny change: 'the 2016 BIO round 1.\' -> 'the 2016 British Informatics Olympiad round 1.\' (saved to drafts)
en6 English fmoeran 2023-10-26 01:56:53 0 (published)
en5 English fmoeran 2023-10-26 01:55:43 585
en4 English fmoeran 2023-10-26 01:47:23 510 Tiny change: ' (4 ≤ l ≤ 2^24) indicati' -> ' (4 ≤ l ≤ $2^24$) indicati'
en3 English fmoeran 2023-10-26 01:41:10 14
en2 English fmoeran 2023-10-26 01:40:57 1245
en1 English fmoeran 2023-10-26 01:40:23 151 Initial revision (saved to drafts)