LCM of a range - problem 255

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

Mathias has clearly used the efficient method (I wouldn't expect anything less) and the 0.5 second time for normal Python corresponds exactly with mine. However, I expect that a lot of other people will not see the efficient method without some hint. As for using compiled languages to get a reasonable time, part of the problem with a poor solution is the need to hold numbers in their exact form. This will give rise to storage issues in any language.

Rodion, I hope the Christmas celebrations went well.

Rodion, I remember "The Apartment" with Jack Lemon very well and have seen it several times, but not for many years now.

I have no preference for the problem title so you should choose. Do you need anything else? It seems that you already have a checker.

Rodion, I have checked the problem with 3 separate runs and everything seems to be fine. The extra test cases don't add significantly to the solving time so they are a good idea.

Rodion, I didn't realise that anyone would be checking on the times when solutions are posted. When I returned to the site two days ago I noticed the 3 new problems immediately, because of the useful feature that lists them on the front page. Naturally I went straight to the problems and then wrote solutions for them. It was then necessary to log in so that the solutions could be posted. There was certainly no intention to give the impression that they had been solved in a ridiculously short time. The Turing problem and the line printer problem were both fairly simple and quick to code. The game took longer but not as long as I had expected because my first algorithm, which I wrote just to test the behaviour of the game, actually worked. I had expected it to fail and then to need to spend some time refining it.

I haven't seen the solution being referred to because I haven't got round to posting my own yet. However, I'm fairly sure that I know exactly what it must look like. All I can suggest is that the range should be kept close to 4 million (for the final set of data) and that the top end of the range should be close to 10 milllion. The size of the numbers involved is eye-watering so the solution time must be impressively long!