No Common Factors

Problem #510  

Tags: unlabeled

Who solved this?

No translations... yet

Many thanks to our colleague Clive Fraser for creating this puzzle!

You are given a list of positive integers. No two integers in the list are the same and all of the integers are greater than 1. If we choose two integers at random from this list it is quite likely that they will have a common factor (greater than 1). In this problem we want to put the integers into a number of separate containers such that any pair of integers chosen from DIFFERENT containers will have NO COMMON FACTOR GREATER THAN 1.

This can clearly be achieved by putting all of the integers into a single container. However, the problem requires you to find the maximum number of containers which can be used. Every integer must go into one of these containers and every container must hold at least one integer. The problem requires a large amount of data so we will use a random number generator to create this.

The Linear Congruential Generator has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem.

The random numbers generated need a small modification before they can be added to our list. Instead of using the value of X(n) directly, we will use the value X(n) + 2. In other words we are adding 2 to each randomly generated value. This ensures that all of the integers in the list will be greater than 1.

Consider the following small example, where N = 10 and the random seed is 30. We use the generator to create the list shown below, which contains 10 random values. Note that each of these is 2 more than the randomly generated X(n) value.

713353, 1468679, 2041709, 1185441, 1830939, 1765396, 1959127, 88324, 157082, 1394026

We can put these integers into 6 different containers as shown below.

[713353]    [1468679]   [2041709]   [1185441, 1830939]  [1765396, 88324, 157082, 1394026]   [1959127]

There are 38 ways of choosing a pair of numbers from two different containers. It is easy to verify that none of these pairs has a common factor greater than one. With this small example it is also easy to verify that it is not possible to distribute the integers among more than 6 containers while still being able to avoid common factors between pairs chosen from different containers. So with this example, the maximum number of containers is 6.

Input/Output description: The first and only line of the input data will consist of 2 space-separated integers R and N, corresponding to the random seed and the number of integers in the list. Your answer is a single integer, the maximum number of containers, as described above.

Example 1:

input:
30 10

answer:
6

Example 2:

input:
176022 100000

answer:
6487
You need to login to get test data and submit solution.