Problems & Puzzles: Problems

Problem 25.- The William Paulsen's Prime Numbers Maze

Usually we think the prime numbers as a list or sequence of numbers with certain properties. If we group the primes that follow certain particular properties we may think the prime numbers as sets of numbers. But have you ever thought the prime numbers as a Maze (or Network) of numbers?…

William Paulsen has created a very interesting and complex problem about a set of disjoint non-empty sets of primes that he calls "The Prime Numbers Maze".

Each and all the disjoint subsets (p1, p2, p3...) of primes of the maze, share a common property: They are composed of all the primes that can be recursively generated by, one at a time, of the following two generation rules:

Let p_i to be any prime expressed in binary notation belonging to the subset pj, . Then you are able to:

1)  Change any one binary digit of p_i, at a time, if you produce a new prime number, or

2)  Add the digit "1" to the left of p_i, if you produce a new prime number ("to the left" means exactly "immediately to the left").

One particular subset of primes numbers in the maze is the one that contains the prime number "2". Let's call this particular set p*. More properly, the "Prime Numbers Maze" of Paulsen is the study of the maze of the primes in p*

All the primes that belongs to p* have "correct parity". Paulsen has shown that a prime p>3 with a quantity of unitary digits UD in his binary representation has correct parity if UD is odd and p mod 3 =1 or if UD is even and p mod 3 = 2.

For example the prime 71 is "linked" in the maze immediately to his "contiguous" primes 7, 67, 79 & 103, by different applications of the permitted rules. BTW, all of them have "correct parity", then all of them belongs to p*

Very soon you will discover that in the maze there are "two ways links" (like between the primes 19 & 23) and "one way links" (like between 23 and 7)

Some weeks ago (August 23), Paulsen very courteously invited to me to take a look to his pages, ending with a "perhaps you could include this puzzle on your web page". After seeing that his creation is not properly one puzzle but certainly a maze-fountain of puzzles, I asked to him to write down a specific unsolved problem for my pages. The following corresponds to his answer:

1. Does the prime number 35759 belong to p*? In such a case, can you show the path that links "2" to 35759 (or vice versa)?

I strongly recommend to read all the Paulsen pages related with this puzzle, before tackling this question.

2.- In other personal communication William Paulsen has said "…there are likely to be an infinite number of totally isolated primes (which wouldn't be too hard to prove)…". Would you like to probe this statement?. (An "isolated" prime number is a prime that neither generates nor is generated by any other prime using the permitted rules)

By my side I would like to add only two more question:

3. Can you produce the first 20 'isolated primes'?

4.- Is 67607 the least 'isolated prime'?