Geek Challenge Results: Primetime Telephone Numbers

In last month's Geek Challenge, we asked what number contains 22 primes? 

This was a unique problem that needed to utilize at least a little bit of computation (to check if something is prime or not). Luckily, prime calculators are a dime a dozen across the interwebs and many computer languages have a “prime check” method built in.

Congrats to our winner, Alex Bruno! A few people commented on the problem being too constrained, giving the amount of included prime numbers made it simple. This was by design! Alex Bruno came up with a way to greatly minimize the amount of prime checks necessary by creating prime-rich building blocks to create a solid foundation. Although 0373373 was not the answer I had in mind, it followed all the rules and was created in a very interesting way.

No one submitted an answer for the 10-digit bonus, which was surprisingly different from the 7-digit case it many ways. Heavy optimization is necessary for that to ensure your number crunching doesn’t run for days.

Thanks for playing! The formal analysis for my solution and Alex’s solution are below.

Alex Bruno’s Solution

A. Overview:

My analysis split into two schools of thought:

1. Brute force it
2. Start with smaller numbers as "building blocks" and put them together until we get a big enough number with the correct number of primes.

Either way, I needed a good way to calculate the number of primes in any given number. I didn't want to sit and do them all by hand. I wanted to be able to type them into something and have it spit out how many. So, I fired up MATLAB, and banged out a script that would take a number of any size and analyze every possible sub-number and tell me how many primes there were. That script was useful in both approaches.

B. Approaches:

1. Brute Force it

What it says on the tin. I took the script and replaced the while with a for, and told it to run every single 7-digit number from 100000 to 9999999. Obviously, this took a while (I let it run in the background while I worked the other method). After about 30 minutes, it spit out:

3733797

This is one of my submissions, and, as I'll explain in a second, is probably the more accurate one.

2. Building blocks

There are a possible 28 sub-numbers in a 7-digit number (calculated using the nth triangle number formula, which is a sort of additive factorial function). If we need 22 primes, that means a scant six of them can be non-primes.
To that end, I needed to find building blocks that would have as many primes as possible. I decided to start with 3-digit building blocks (six possible sub-numbers), and came up with the following:

Five primes out of six (I started with a list of prime numbers less than 1000):

337
353
379
733
773
797

Six primes out of six:

373

Obviously, I needed to use 373 as a building block. In fact, I could use it twice, and only need to add one extra digit. This looked like this:

373 373 _   OR   373 _ 373     OR    _ 373 373

This left me with 30 options to run, which was very simple using my code. The only combination that gives me a full 22 primes is:

0373373

This is because the 0 in the front, while not being prime itself, makes several extra primes (since 37 is prime, so is 037, etc.). Even with losing that digit as a prime, it adds several others.

C. Conclusion:

So, I have two answers; two 7-digit numbers that have 22 prime sub-numbers. While it is absolutely the more inelegant of the approaches, I would submit the first answer (3733797) as the more correct answer because the prompt for this problem dealt with phone numbers, and I'm not sure they can start with a 0, as with my second answer.

I'll argue that I may have gotten to the first answer using building blocks if I had kept going with that method; the brute force answer does include two of the 3-digit building blocks I found (373 and 379).

Unfortunately, I didn't have time to grapple with the 10-digit optional problem. I can't imagine doing that either of the two ways I did, so I have to ask, what is the more elegant way to do this? I'm sure there's some sort of trick, and I would love to know what it is!

My Solution

Prime number calculation is a deeply researched and investigated field of study with many applications and approaches. Because of this, there are some highly efficient methods for calculating primes. We can leverage these approaches to create an efficient computational solution.

As described, this challenge involves finding primes within a number, with the added complexity of multiple possible sub-groupings and prime combinations. Any given n-digit number has (((n+1)*n))/2 possible groupings (one set of n consecutive digits, two sets of n-1 consecutive digits and so on down to n sets of one digit, so the total number of groupings is the sum from 1 to n). For any given number, all combinations must be investigated to obtain the number of primes it contains.

To avoid excessive calculation, two major computational savings can be applied:

1. Use a prime number sieve (such as the Sieve of Eratosthenes) to pre-calculate all prime numbers within the relevant range (all values less than 〖10〗^(n+1)-1).
2. Use memorization to store a record of previously determined number results.

The first optimization requires creating an array mask of prime/not-prime values. Then, whenever a number is encountered, rather than determining if a number is prime, the corresponding index in the array can be accessed rather than re-calculating the primality of the number. This approach requires greater memory but substantially less computation, especially when many prime computations need to be carried out in a small range. There are several further optimizations that can be applied to the prime number sieve which are not discussed here.

The second optimization leverages an observation on the nature of the result for any given number. Consider the graphic provided in the problem statement:

From these graphics, observe that it is possible to get the number of primes in the n-digit case by taking the sum of the n-1 groups, and subtracting the n-2 group shared by both n-1 groups. Alternatively stated, take the sum of the 6-digit number results and subtract the “middle” 5-digit number case (so 9=6+8-5).

Therefore, for any given number with more than two digits, it is not necessary to calculate the number of primes it contains directly from a sum of its groups, but instead can be found by taking a sum of these sub groupings. An important caveat to this approach is that each entry must be considered with leading zeros as a different value than without leading zeros (i.e. in the example given, 07 is unique from 7).

Applying these computational observations along with the additional unstated constraint that the n-digit number cannot start with a zero, the best answer was found to be 3733797 with 22 primes (with a total computation time of approximately five seconds). The graphic representation of this is shown as:

The Bonus Solution

Extending this approach to the 10-digit case requires some code refactoring, because the prime sieve array mask and memorized prior results require data structures with more indices than provided by a single unsigned 32-bit integer. This can be overcome several ways. One possible approach involves creating custom data-structures that act as wrappers on standard data structures and using a 64-bit integer to address locations. Implementing these structures comes at a significant computational and memory access cost, which substantially slows computation time. Consequently, the 10-digit case took approximately 24 hours to solve.

The best 10-digit number (with 38 primes out of a possible 55) was found to be 7000373379. A graphical representation of this number is shown below.

As an additional interesting note, the distribution of the number of primes in a given number of digits is shown below:

Submit your Geek Challenge questions and ideas at geekchallenge@dmcinfo.com.