WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
The task of the problem is extraordinarily easy to state. We need to find , the cardinality of the set of all possible products of numbers between and .
The key insight for solving the problem was to regard this set as the set of lattice points in a particular convex polyhedron. At the time of writing this post, I have, however, still troubles rigorously justifying that this works, so the “guidance experience” is going to be somehow incomplete.
Anyway; any number in the set can be written in the prime decomposition form with primes less than or equal to . We may thus identify with the set of vectors of exponents in the prime decompositions.
Dually, we may also represent any product in by the vector , where denotes the number of times that the number appears in the product. Between the two representations, we have quite obvious relationship:
where with is just the matrix that counts the exponents of primes in the numbers . We are also subject to additional constraints:
This tells us nothing else that the set of all possible vectors (where ’s are regarded as vectors over , rather than ) is, by definition, a convex polyhedron. Moreover, the result of applying the linear transformation on , which is precisely our scrutinized set of all possible vectors , must be again a convex polyhedron (again regarded as vectors over )!
We also have a ready way to obtain the vertices of the convex polyhedron – we just need to map the vertices of under . The vertices of are simply:
The vertices of are then . Finally, we only need the convex hull vertices to define the polyhedron . Let thus . To finish off, we need the following conjecture:
Conjecture: The lattice points of surject to the lattice points of .
In other words, this equivalently says: “Any lattice point (vector with all integer components) can be written as for some lattice point ”. The only thing we can say for sure, however, is: “Any lattice point can be written as for some (not necessarily lattice point) ”.
From what I can see, this conjecture holds in this setting (and definitely doesn’t hold for arbitrary matrix ), perhaps due to the structure of matrix . If you can prove the conjecture or have any other ideas, please contribute to the Project Euler problem discussion, or at least comment below.
Provided that the conjecture holds, we simply have:
To find the number of lattice points in a convex polyhedron, I will only refer to the »Ehrhart polynomial«. The problem is at this point solvable without actually understanding the theory of Ehrhart polynomials, but I recommend looking into them - it is an interesting read.
The following piece of Sage code gives answer instantaneously.