## The Problem

Here is a moderate problem of CodeJam’s qualification round of 2016. The Jam Coins. Here is the description of the problem. You need to generate jamcoins of either 16 digits for small dataset or 32 digits for large datasets. Jam Coins follow the given rules…

- A Jam Coin is only made up of 1’s & 0’s of the required number of digits.
- It begins and ends with 1.
- If that interpreted from base 2 to base 10, it should not be a prime number in any of them.

For Small dataset, you need to generate 50 jam coins of 16 digits and for large dataset, you need to generate 500 jam coins of 32 digits following above rules.

Output should be the list of Jam Coins where each is followed by a divisor of that number in each base.

Let us say that we want to test if `11001101`

is a jam coin or not.

If we assume that the number is in base 2, it’s decimal equivalent is 2^7+2^6+2^3+2^2+1 = 205 => Not a prime number => Divisible by 5

If we assume that the number is in base 3, it’s decimal equivalent is 3^7+3^6+3^3+3^2+1 = 2953 => Prime Number => Hence not a jam coin

Let us test `1010101`

Base | Decimal Equivalent | Divisior |
---|---|---|

2 | 85 | 5 |

3 | 820 | 2 |

4 | 4369 | 17 |

5 | 16276 | 2 |

6 | 47989 | 37 |

7 | 120100 | 2 |

8 | 266305 | 5 |

9 | 538084 | 2 |

10 | 1010101 | 73 |

It is divisible by some or number in all bases from 2 to 10. Hence it is a Jam Coin. We need to generate such coins with given number of digits.

Hence this can be included in output as below if the input is `7 10`

1 | Case #1: |

## My solution

Let us begin with breaking the problem into manageable chunks before we try to solve it.

1 | Generate a number with required number of digits |

There are several complex problems inside the deceptively simple pseudocode

- Handle large numbers. 16 digits are way too big for a long datatype.
- Generate a number of required digits of 1’s & 0’s
- Convert the number to decimal from given base
- Testing if it is prime number
- Finding a divisor

Let us solve them one by one

##### [1/5]Handling insanely large numbers

It depends on the programming language of your choice. For this solution, I have chosen Java, which has java.math.BigInteger class that can store numbers and provides a very useful methods for prime number calculations. Example usage is as below.

1 | BigInteger num = new BigInteger("101010110000011"); |

##### [2/5]Generating combination of 1s and 0s that begin and end with 1

Following is the algorithm I followed.

- Generate a string of zeroes of size n-2, assuming n is the length required
- Append 1 before and after the string of zeroes
- To Generate another number, imagine the number if in binary, adding two(10 in binary format) will give next odd number. Any number ending with 1 in binary number is an odd number.

1 | 100000000001 |

How do you add 10 in binary format? Just convert that base 2 number to base 10 and add 2 and convert it back to binary number, which leads us to the following question.

##### [3/5]Convert the number to decimal from given base

1 | BigInteger incrementInBinaryByTwo(BigInteger num) |

Converting from a decimal number to binary format is as simple as calling toString method with 2 as the parameter.

##### [4/5]Testing if it is a prime number

BigInteger class of Java provides a nice API to work with prime numbers

BigInteger.isProbablePrime() will return false if it is definately not a prime and returns true, if the probablity for this number to be a prime number is less than 2^-100. Hence for our purpose of finding it is not a prime number this would serve the purpose.

1 | static boolean isComposite(BigInteger num) { |

##### [5/5]Finding a divisor

BigInteger has nextProbablePrime method that returns a prime number after the given number. So, if we use it on a prime number, we can get the next prime number and so on. As we can now get all prime numbers one after the another, we can divide our number with each prime number and return the first divisor. However, going indefinately till all primes are verified is inefficient for this problem. There will be simpler jam coins to mine. So, we will test for first 10000 prime numbers. If it is not divisible by any of it, we ignore that number and continue with next number. Here is the code.

1 | static BigInteger findSmallestFactor(BigInteger n) { |

1 | package year2016; |