The jam coin problem, the third one in google code jam 2016 qualification round, is more interesting than it appears to be.

For most people, the most intuitive way to solve this problem would be enumerate all potential jam coin numbers, and filter out those that matches the predicates related to various bases. In fact, that’s exactly what I did, and that’s only enough for the small input cases. For large input cases, the prime testing for large numbers could be rather expensive.

Later on I realized that it’s not necessary to find all valid jam coin numbers; 50 for small input and 500 for large input would be enough. In other words, the solution don’t need to be complete (it’s OK to have false negative), but it has to be sound (it’s NOT OK to have false positive). Therefore, I could do the prime testing a bit leniently; pessimistically stating a number is prime once the test factor goes above 1000. This way, I may skipped some valid jam coin numbers, but I can still find enough to pass the test.

On reflection, I assumed that the message from this problem is to be aware the high cost of prime testing for large numbers, and probability programming could be useful if the result don’t need to be 100% correct.

However, after reading the analysis from google, I discover that there’s a whole new level beside the aforementioned, and that’s why this post is written down. Readers are recommended to read the original analysis from google, but I would paraphrase the gist so that readers can keep the flow of reading this post.

One expected way of solving the large input case is to study the jam coin numbers we found in the small input case, and find the pattern(s).

Among 50 jam coin numbers, 11 of them have the following factors:

1
2
base:   2 3 4 5 6 7 8 9 10
factor: 3 2 5 2 7 2 3 2 11

Hinted by 5 7 11, one could conclude that those jam coin numbers have the smallest factor of b+1 for base b, and b+1 in base b is written as 11. Therefore, those numbers could be divided by 11 for any base, and numbers matching 11(0|11)*11 is divisible by 11 for any base. In order to make the matching easier, we could predetermine how many pairs of 11 we would like to put into the number. The lower bound needs to be 2, because of the first and last digit constraint. Then, given N = 16 or 32, what’s the number of jam coin numbers matching 11(0|11)*11 with p pairs of 11?

Take 11 {} 11 {} 11 with N=16 as an example, and we need to place 10 zeros into 2 slots. This is actually classical putting-N-unlabelled-balls-into-M-labelled-boxes combinational problem in mathematics, and it’s often solved using Stars and bars. The total number of choices is 11.

More generally, for N=16,

1
2
3
4
5
6
7
for p = [2:5]
    nchoosek(16 - p - 2 , 16 - p*2)
end
ans =  1
ans =  11
ans =  45
ans =  84

, and for N=32,

p 
1
2
3
4
5
6
    nchoosek(32 - p - 2 , 32 - p*2)
end
ans =  1
ans =  27
ans =  325
ans =  2300

Therefore, 5 is the smallest pairs of 11 we need to have in jam coin number in order to pass both small and large input case, which is why 11 {} 11 {} 11 {} 11 {} 11 is used in the python sample code from google.

In the analysis, the other factors sequence is left as an exercise, and here’s my attempt:

1
2
base:   2 3 4 5 6 7 8 9 10
factor: 3 2 3 2 7 2 3 2 3

I need to use those two theorems from https://teresamccullough.wordpress.com/2011/05/25/divisibility-rules-for-numbers-in-bases-other-than-ten/

In base N, if the sum of the digits is divisible by a factor of N — 1, the number is divisible by that factor.

In base N, if alternate digits are added and subtracted, the divisibility of the result is the same as the divisibility of factors of N + 1.

For base 4 and 10, I apply the first theorem, and the rest digits are applied with the latter theorem. Then, the number of 1s is divisible by 3, and it’s even number. Therefore, the jam coin number following this pattern should have six or multiple of six of 1, and half of them on odd index and half on even index.

Let’s calculate how many jam coin numbers there are following this pattern:

1
2
(nchoosek((16 - 2)/2, 2))^2 => ans =  441
(nchoosek((32 - 2)/2, 2))^2 => ans =  11025

Good, it means that having six of 1 in our jam coin numbers is enough for both cases; otherwise, we need to try twelve of 1.

The complete code, implementing lenient prime testing, the first pattern, and the second pattern, is available here.