# Jam Coins

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 | base: 2 3 4 5 6 7 8 9 10 |

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 | for p = [2:5] |

, and for `N=32`

,

1 | nchoosek(32 - p - 2 , 32 - p*2) |

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 | base: 2 3 4 5 6 7 8 9 10 |

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 `1`

s 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 | (nchoosek((16 - 2)/2, 2))^2 => ans = 441 |

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.