Lucky Pairs - A possible new problem

Back to General discussions forum

The generator for this problem typically generates a series of 7 sets of input data, of increasing difficulty. The time to set the problem and to find all of the corresponding solutions is about 0.25 seconds in Python. A typical set of data is provided in the example below.

The following is a draft problem description:

Matilda is a girl who likes numbers. She especially likes pairs of numbers with a special property. She refers to these as lucky pairs. Each number in the pair is an integer greater than 1 and not greater than some given maximum number. The two integers in the pair must have no common divisors (other than one). For reasons which we won't go into here, Matilda does not like the numbers 6, 7, 11 and 15. Consequently none of these numbers can appear in a lucky pair.

Matilda is particularly interested in knowing how many lucky pairs exist for a given maximum number. She can easily work this out for small values of the maximum. For a maximum of 13 she was soon able to discover that there are 22 lucky pairs. These are:

(2, 3), (2, 5), (2, 9), (2, 13), (3, 4), (3, 5), (3, 8), (3, 10), (3, 13), (4, 5), (4, 9), (4, 13), (5, 8), (5, 9), (5, 12), (5, 13), (8, 9), (8, 13), (9, 10), (9, 13), (10, 13), (12, 13)

Note that the pair (2, 9) is the same as the pair (9, 2) so these are counted as one pair.

The first line of the problem contains a single integer N. N lines follow. Each of these contains an integer (not larger than 50 million) which is the maximum value to be used for a count of lucky pairs. For each of these maximum values you must find the corresponding number of lucky pairs. Give these answers, separated by spaces, as a single string.

Example:

input:
7
13
423
4353
18316
407615
2433520
33309521

answer:
22 53033 5745583 101909594 50502234580 1800069470763 337254803668175