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
    Just create all the products in natural order and then sort them. There are only about half a million of them, after all. Alternatively, create 1000 lists, each decreasing, and merge them in a balanced merge tree. (And it's "cartesian" with no h).2012-07-10
  • 0
    We have been asked not to discuss Project Euler problems.2012-07-10
  • 0
    This is not really about the answer to the Euler problem, this is just an aspect of the solution that I find interesting, it's not at all necessary to order these pairs for the solution to the Euler problem.2012-07-10
  • 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