Prime Number Verification

I had been working on ProjectEuler Problem 41 for a while. What happened is that I thought this problem might easily be solved if I could calculate a large number of primes in memory. The idea was to enumerate a pandigital number and then check a prime number verification array to see if the enumeration was prime.

Problem 41 – Pandigital Prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime. What is the largest n-digit pandigital prime that exists?

Prime Number Verification the Hard Way

My initial idea was to generate all the primes up to the largest pandigital prime. The question was, where to stop? Would I have enough memory to generate the target prime? I also thought I would need to start with the following sequence:

  • 9876543210

and then enumerate the permutations in descending order since I was looking for the largest pandigital prime. A ten digit number requires checking all the primes up to ten billion. I then tried to generate a few primes and the algorithm seemed to work. I then started adding more digits to my seed enumeration and eventually used all ten digits. I tried calculating all the primes up to about one billion and ran out of memory. I had hit the wall.

BitSet to the Rescue?

Undaunted, I thought, let me try using my BitSet implementation to generate primes. That worked for two billion but I hit another wall because BitSet only handles set with up to the limit of the capacity of an Integer which is a little more than two billion. Also, the run time was over five minutes so I knew I was on the wrong path. I had to make this work to do the prime number verification. Possible solutions included segmenting the prime number generation and writing the numbers to disk. Neither solution looked appealing so I was stuck.

Prime Number Verification the Easy Way

I then thought, is there a way to perform prime number verification? That looked promising since I could eliminate the prime number generation step. After searching the web for thirty minutes, had my answer. If a number is prime, one of the following is true.

  1. 6n + 1 = prime
  2. 6n – 1 = prime

When I first saw this, I doubted the solution. It was just too simple. Actually it is too simple.  The theorem states that if a number is prime, then one of the two conditions is true. The theorem does not say that if a number satisfies one of the two conditions then the number is prime. The theorem says nothing about composite numbers. For instance, 25 satisfies condition one but 25 is not prime. Nevertheless, this theorem invented by Euler was crucial to finding the solution.

At this point, I re-read the questions and realized that zero was not part of the pandigital number so I was making the required set of primes ten times bigger than required. Generating up to a billion primes was possible, so things became easier.

The next task was to disable the prime number generator and just run the pandigital enumerations through Euler’s theorem. This step showed that there are no pandigital primes that contain nine digits (e.g. 987654321) because all the permutations failed both conditions of Euler’s theorem! Since this sequence contains no primes, I used this as a domain restriction in my final solution. Then I tested with eight digits and got the same result! This was surprising because composite numbers can satisfy Euler’s theorem.

I tested with seven digits and generated a possible prime that I tested on ProjectEuler but the answer was incorrect.  I now knew that there might be a seven digit pandigital prime. I adjusted my code to actually calculate all the primes up to ten million. This problem demonstrates a few things:

  1. If you cannot find the algorithm you need, try writing one.  In this, I just assumed I code modify the lexicographical permutation algorithm and in about an hour, I had the algorithm and a diagram.
  2. When stuck, keep going, persistence pays off.
  3. Do not hesitate to through out a non-working solution. Consider the time spent on the solution as training.
  4. Incorporate other algorithms in your solution as needed. I found Euler’s therorm but I still did the work and felt like I solved the problem even though Euler’s theorm helped a lot.
  5. Review the problem to make sure you understand it correctly.

After running my program, I got another prime that did not match the prime candidate I found using Euler’s theorem. I tested the pandigital prime on ProjectEuler and got the big green check mark.

Down the Rabbit Hole

Finally after chasing after billions of primes that I did not need to calculate and going down several rabbit holes, I had the solution. This turned out to be a really interesting problem involving Euler’s theorem, prime number generation with BitSets, and Domain Restrictions.

If you have a comment, please leave a message below. For computer science videos, please subscribe to my Translation Data YouTube channel.  You can follow me on twitter @HaroldAlmon or @TranslationData.