Blue Eyes On An Island

This is not written formally yet; I skip a lot of details to present mostly the main idea.

Yes, this is a variant of the well-known blue-eyed islander puzzle. The usual question is that the statement by the outsider is "there is a blue-eyed islander", and this variant is "there is a composite number of blue-eyed islanders". (I hope I didn't botch up the first paragraph, because it's very crucial to the puzzle, but I hope that if you already know the problem, you can take from it.)

First, you need to prove yourself that whatever nontrivial statement it is (a trivial statement is true for all numbers of blue-eyed islanders; a nontrivial statement is false for some number), the island will eventually get deserted. The proof is by induction, as usual. Or you can read the proof here .

If you also know how the proof goes, the induction step works as follows. If $n$ is the actual number of blue-eyed islanders, and $m$ is the closest number to $n$ where the statement is false if there are $m$ blue-eyed islanders, then:

• $n = m$ can't happen, because then the outsider is lying.
• if $n > m$ , then after the $(n-m)$ -th midnight, the blue-eyed islanders leave. If there are any brown-eyed islanders left, they leave on the next midnight.
• if $n < m$ , then after the $(m-n)$ -th midnight, the brown-eyed islanders leave. If there are any blue-eyed islanders left, they leave on the next midnight.
• if $n$ is equally close to two such forbidden numbers, all islanders leave on the same midnight.

Finally, it's just the task of finding the smallest $k$ such that all islanders will leave by the $k$ -th midnight, no matter what $n$ was initially. Since the forbidden numbers are the prime numbers (and 0 and 1), this is equivalent to finding the largest gap between two prime numbers; our $n$ will be precisely in the middle between these two prime numbers. (There is an additional complication near the edges; for example, with $n = 1000000$ , $m$ cannot be larger, so it will be eliminated by the case $n > m$ only. As it turns out, this one doesn't matter; $m = 999983$ , so $n = 1000000$ is eliminated by the 18th midnight.)

This is a simple task to program. Simply sieve the prime numbers up to 1000000 and find the largest gap. This occurs between 492113 and 492227, with a gap of 114; at $n = 492170$ , the last case will occur after 57 midnights, and this is our answer.

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

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

l = list(eratosthenes2(1000000))
m = 0
for i, j in zip(range(len(l)),range(1,len(l)-1)):
    if l[j] - l[i] > m:
        m = l[j] - l[i]

print("Max Gap: ")
print(m)