1
$\begingroup$

For problem 4 in the euler project part of the assignment is to generate a list of products of 3-digit numbers.

The easy way is to just do a cartesian product (I think it's called), and after that find the largest value that is a palindrome.

My question is, is it possible to generate a list of pairs of which the product is ordered?

For example with 2-digits:

99,99 99,98 98,98 99,97 98,97 etc.. 

My attempt is (in haskell):

productsOf2Digits = productsOf2Digits' 99 99 productsOf2Digits' 90 90 = (90,90, 90*90) : [] productsOf2Digits' a b | a == b = (a,b,a*b) : productsOf2Digits' 99 (b-1)                         | otherwise = (a,b,a*b) : productsOf2Digits' (a-1) b 

Which yields:

(99,99,9801) (99,98,9702) (98,98,9604) (99,97,9603) (98,97,9506) (97,97,9409) (99,96,9504) (98,96,9408) (97,96,9312) (96,96,9216) 

The pair 99 96 breaks the ordering.

I think maybe I can exploit that the differences should be increasing?

Also, might it have to do with? http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/rationals.pdf

  • 0
    It might be worthwile to think of this on a log scale. I imagine a piece of log-log graph paper, with integer points corresponding to the line intersections. In that setup you want to enumerate crossings ordered by manhatten distance. Not sure how best to do that either, but it feels remotely related to scan conversion.2012-07-12

1 Answers 1

1

Here's a piece of C++ code for you.

#include  #include   class Itm { public:   int p, x, y;   Itm(int x, int y) : x(x), y(y), p(x*y) {}   Itm() : x(0), y(0), p(0) {}   bool operator<(const Itm& that) const {     return p < that.p || (p == that.p && x < that.x);   } };  int main() {   std::priority_queue q;   for (int i = 1; i < 100; ++i)     q.push(Itm(i, 99));   while (!q.empty()) {     Itm t = q.top();     std::cout << t.y << " * " << t.x << " = " << t.p << std::endl;     q.pop();     if (t.y > t.x)       q.push(Itm(t.x, t.y - 1));   } } 

The idea is to have a queue containing one item for each column (thing with same x value). Initially they all start of at the y=99 row. In each iteration, the maximal item is taken from the queue, and the item one below that added instead, unless doing so would leave the range of pairs we're interested in. In this case the range is 1 ≤ xy ≤ 99 but I'm printing y first to match your lists.