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
Dear Clive, Hi!
Sorry for slow reaction - the problem is live now! Thanks a lot - looks much enjoyable, as in good old times when there were certain colleagues with strong inclination to math puzzles at which I myself always was a bit weak :)
But I shall try too!
I feel a bit puzzled about the numbers Matilda do not like, but probably this may come self-explaining when I find solution :)
Rodion, Hi!
Thanks for putting the problem in place, and thanks to Mathias for demonstrating that it works before I even got to the site to see it in place!
Don't agonise over the numbers that Matilda does not like. I could have chosen any similar group of numbers. The reason for including such a group is that it is possible that some people may have solved a similar problem before. The extra numbers mean that they cannot just re-use their code without at least making some modifications to it first.
The 1.5 day advance warning plus a bank holiday yesterday mean that the solution was ready and waiting ... I am curious to see (at some point) how the 0.25 seconds Python solution works; my approach is nowhere near that.
Mathias Hi!
I would normally have waited for several solutions to appear before posting my own. However, in view of your request I can see no reason why I should not post my solution now.
I am not a programmer so must apologise for the very non-standard appearance of my code. I hope you can make some sense of it!
I can see no reason why I should not post my solution now.
I dare to add my meek opinion here - I already noticed you and Mathias are reluctant to post your solution for problems created by yourself - but as there is no logical solution to this small contradiction, I long wished to say "just do it" without much waiting - let it be "reference / author's" solution. I suspect among our gurus no one is much concerned with precise position in the "ranking table" :)
must apologise for the very non-standard appearance of my code
This is also very interesting point! From one side, when reading your code, I sometimes wish for more descriptive variable names - and sometimes for more splitting into named functions. On the other hand your style ensures that whoever reads, need to put some attention and labour, and it is more difficult to copy-modify such solution cleverly without working through it.
Reading through other's code is very important skill for programmers, so in that sense you need no apologies and even it may be proper to thank you for such bio-diversity among the top solvers :)
Hi Clive,
Many thanks for sharing. Interesting, a rather advanced mathematical formula and recursion. I had to google quite a bit, and importantly work out what actually to google for, to find a good explanation of the underlying idea. My approach is much more brute force. It's still sufficiently fast; about 2.5s for the given example using pypy.
And hi Rodion,
I'm not reluctant to post solutions for problems suggested by me, I've simply waited one or two weeks before doing so. Clive has much better self-control and waits longer. :)