Are some rooms totally isolated?

In roaming the maze, one notices plenty of "dead ends". There are even some rooms that, once you get in, you cannot back out. The simplest example is the goal of the basic maze: Room 127 = 11111112. Changing a 1 to a 0 yields rooms 126, 125, 123, 119, 111, 95, or 63, all of which are composite. Furthermore, adding a digit 1 to the left of this number produces 255 = 111111112, which is also composite. However, this room is not completely isolated from the maze because one can drop in from room 383 = 1011111112. This begs the question whether there are prime numbered rooms which are totally isolated. That is, not only does it not connect to any other rooms, but it cannot be reached by any other prime room either.

At first this might seem to be an almost impossible question to answer, for there would be an infinite number of rooms to check for primes. Yet it is possible to find a prime number p such that p + 2n is composite for all n. This problem is closely related to the Sierpinski problem.

Definition: A Sierpinski number is a number k for which k.2n + 1 is composite for all n>0. The only current way to show that a number k is Sierpinski is to find a finite set of prime numbers, called a covering set, for which every integer in the sequence k.2n + 1 is divisible by at least one of these primes. Probably the first two Sierpinski numbers are 78557 (covering set 3, 5, 7, 13, 19, 37, and 73) and 271129 (covering set 3, 5, 7, 13, 17, and 241). The Sierpinski problem is to show that these indeed are the first two Sierpinski numbers.

It so happens that if k is a Sierpinski number with a covering set of primes, then k + 2n will also be composite for all n. Hence we only need to look at prime Sierpinski numbers. 78557 isn't prime, but the next known Sierpinski number 271129 = 1000010001100011012 is. However, this room is not isolated because it connects to Room 262937 = 10000000011000110012. We not only need p + 2n to be composite, but also changing any digit 1 to a 0 must also be a composite number.

The smallest Sierpinski prime that satisfies this extra condition is 2131099 = 10000010000100100110112. Thus, this room is totally isolated from the rest of the maze. There in fact an infinite number of isolated rooms such as this one. The proof involves the existance of a number that is both a Sierpinski number and a Riesel number. (Such numbers are called Brier numbers.) Two more isolated rooms are 9208337, and 11788523. This last room even has the correct parity, hence proving that not all primes of the correct parity can be reached. (An explanation of parity is here.)

The covering set for 11788523 is {3,5,7,13,17,241}. For a detailed explanation as to why 11788523 + 2n is always composite, consider dividing n by 24, and finding the remainder. If the remainder is even, 11788523 + 2n will be divisible by 3. (Try it!) If the remainder is 1, 5, 9, 13, 17, or 21, 11788523 + 2n is divisible by 5. When the remainder is 3, 11, or 19, the number is divisible by 17. Finally, if the remainder is 7, 15, or 23, then 11788523 + 2n is divisible by 7, 13, or 241 respectively.

Back to the maze.