I logged in to the site to propose a new problem, only to find that 3 more problems have appeared since I last logged in! My suggestion is not as imaginative as those but hopefully will provide a good challenge. It is only of medium difficulty so should attract a good number of solutions.

The motivation for this problem is to take a fairly routine calculation and to change the parameters in such a way that we introduce a kind of puzzle element into the solution. More specifically, what we have here is a problem where the "obvious" solution is soon found to be impractical. We then have to think about the problem, answering such questions as "What is going on here?" and "What is actually needed in order to find the solution to the problem?". A good analysis of the problem should soon lead to a method for solving it. There is another twist here. The most likely method that presents itself at this point is not the best. Further thought based on this solution should reveal how it can be made much better. I made a decision that the routine used for creating the problem (4 sets of data), together with the solutions, should not take more than 1 second. Because of this, the less efficient method should still execute in around 1 minute or less.

The following is a draft of a possible problem description:

The Least Common Multiple or LCM of a set of numbers is a well-known concept. It can be defined as follows: The LCM of a set of numbers is the smallest positive integer which is exactly divisible by each of the numbers in the set. For example, LCM(14,20) = 140 and LCM(3,6,10) = 30. We can also define the LCM of a range of numbers e.g. LCM(2...5) = LCM(2,3,4,5) = 60 and LCM(10...15) = 60060. As the range of numbers increases the value of the LCM tends to increase rapidly. For example LCM(40...60) = 4224373219170545641200. Since we will be dealing with very big numbers we will give all of the results modulo 1000000007 (i.e. 10^9 + 7). So LCM(40...60) mod 1000000007 = 933314007.

In this problem you will be asked to find the LCM for each of about 4 different ranges of numbers. The numbers at the start and end of the range are both included in the LCM calculation. The range is likely to contain many numbers. Specifically, for a range from N1 to N2, N1 will not be larger than 2*N2/3. No number in any of the ranges will exceed 10 million and no range will contain more than 4 million numbers.

If your computer does not crash from the demands made on its resources and you get a correct solution after half a day of program execution time, then you deserve to claim the solution for sheer persistence! However, that defeats the object of the problem. You should look for an efficient solution. My experiments in Python (usually significantly slower than other languages) give times of just under 1 minute for what I think will be the most likely method. However, there is a better one, which executes about 100 times faster and has a significantly shorter and simpler program. My tests gave an average of 0.5 seconds for solving all 4 typical problems i.e. those generated by the problem setter routine. For those of you who are inclined to look for this fast solution, I will give one hint... (hint stolen by nasty admin)

Input data: The first line gives the number of ranges (typically 4). Each of the following lines contains two numbers separated by a space. These are the first and last numbers in the range.

Answer: This is a series of space-separated integers, giving the LCM values for each of the ranges, all calculated modulo 1000000007.

Example:

input:
4
10 15
40 60
5728 9708
6119950 9666068

60060 933314007 587266328 562476460