Partitioning the maze

One of the unsolved problems was to determine whether Room 35759 connected to the main maze in some way? This question actually has two parts: can Room 35759 be accessed from Room 2, and can Room 2 be accessed from room 35759? This is the smallest prime for which both questions are interesting. If one started at Room 35759, one can wander though an infinite maze, reaching higher and higher primes. This "secondary maze" seems to increase geometrically, as the main maze does.

Michael I. Hartley has shown me a proof that in fact, 35759 is in a different partition as the main maze, so indeed there is no way to get to Room 35759. In fact, there are an infinite number of similar partitions, all of them apparently containing an infinite number of primes.

For each binary number, consider the alternating digit sum

A( d₀ + 2 d₁ + 4 d₂ + 8 d₃ + ... + 2ⁿ d_n ) = d₀ - d₁ + d₂ - d₃ + .... + (-1)ⁿ d_n,

where d_i is a digit 0 or 1. Thus, A(13) = A(1101₂) = 1 - 0 + 1 - 1 = 1. The alternating sum of the digits provides us with a way to test if a binary number is a multiple of 3. The number n is a multiple of 3 if, and only if, A(n) is a multiple of 3. (In base 10, the alternating sum tests to see if a number is divisible by 11.)

It is clear that A(n) changes by 1 in each step of the maze. Also, if p is prime, A(p) cannot be a multiple of 3, except for A(3) = 0. Since A(35759) = A(1000101110101111₂) = 1-1+1-1+0-1+0-1+1-1+0-1+0-0+0-1 = -4, there is no way of getting to Room 35759 in the original prime maze.

In fact, since A(n) cannot be a multiple of 3 for any prime p, we can partition the primes as follows: the k-partition consists of all primes p such that A(p) = 3k+1 or 3k+2. Thus, the main maze is the 0-partition, 11 is in the (-1)-partition, and 35759 is in the (-2)-partition.

Note that this proof also shows that 2 cannot be reached from room 35759, and so this argument is valid in both directions.