How can I generate the products of two three-digit numbers in descending order?

Question

While experimenting with different solutions to a little programming exercise, I generated an array with the products of all two three-digit numbers (i.e. 100 to 999). Since I wanted to process those products in descending order, I then sorted the array and then looked for the first element matching a certain predicate.

However, since the first matching element is usually near the beginning of the array, generating all numbers and then sorting all of them is quite wasteful. Instead, I wonder: is it maybe possible to generate the products incrementally? The ten largest products of two three-digit numbers are

998001 = 999 * 999
997002 = 998 * 999
996004 = 998 * 998
996003 = 997 * 999
995006 = 997 * 998
995004 = 996 * 999
994009 = 997 * 997
994008 = 996 * 998
994005 = 995 * 999
993012 = 996 * 997

I tried to find a pattern in the factor pairs, but couldn't spot anything. I suspect there is some algorithm for getting the products in descending order without having to compute all the products in advance though - or maybe there isn't?

Answer 1

For each of the 999 possible first factors, construct an object that will produce the multiples of that factor on demand starting with the highest one. Each object has a primitive to ask it what the next number to produce is (without updating it), and one to move to the next number.

Maintain a priority queue of these generator objects, arranged by which one has the largest "next product". Once you consume a result, remove the front of the queue, and reinsert it after you update it to move to the next number.

Naively (and abusing the notation horribly!), setting up all this takes $O(999)$ time once and for all, and afterwards each successive product can be retrieved in time $O(\log 999)$.

You can get rid of the initial set-up time by only creating the generator for multiples of $n-1$ after the first multiple of $n$ has been consumed (since it can't possibly be relevant until that happens anyway).

Answer 2

I found an approximation, but an exact pattern needs more work.

If you use a multiplication table, and then replace all the values with their ordinal numbers

Then you'll find this pattern here

There is a rough zig-zag pattern, the traversal is demonstrated in this SO answer.

The code here is only proof that a pattern exists (not optimized/pretty). It doesn't go through a matrix, but it's grounded in the same concept. Here I just generate whats needed, which is the differences between two numbers a,b both < n : (999 - 0,999 -0), (999 - 1,999 - 0), ... and then subtract those differences from our upper bound n.

Solution (javascript)

function* gen(n) {
    let diff = 0
    while (diff < n) {
        let ridge = Math.ceil(diff / 2)
        let [a, b] = [ridge, diff - ridge]
        yield [n - a, n - b]
        while (--b >= 0) {  
            ++a
            yield [n - a,n - b]
        }
        ++diff
    }
}

n = 999
sample = 10

let iter = gen(n)
let shortlist = [...Array(sample)].map(_ => iter.next().value)
let products = shortlist.map(([a, b]) => `${a * b} = ${a} * ${b}`)

console.log(products.join('\n'))

Output

998001 = 999 * 999
997002 = 998 * 999
996004 = 998 * 998
996003 = 997 * 999
995006 = 997 * 998
995004 = 996 * 999
994009 = 997 * 997
994008 = 996 * 998
994005 = 995 * 999
993012 = 996 * 997

Answer 3

My approach was to programatically set a limit to my for loops each time a palindrome was found, because I know that the product of any number less than that limit will not produce a palindrome larger than the one I just found.

pal = 10001;       %lowest possible palindrome
limit = 100;       %lowest 3-digit number
for i = 999:-1:100
    for j = i:-1:limit
        fwd = i*j;
        rev = int2str(fwd);
        if fwd == str2num(rev(end:-1:1))      %reverse number and compare
            if pal < fwd
                pal = fwd;
                limit = j;       %adjust end condition of loops
                break            %restart j-loop when a palindrome is found
            end
        end
    end
    if i == limit
        break           %end search when i-loop reaches set limit
    end
end
pal        %output

Of course, this doesn't search in the exact order you were looking for, but considering it only takes .8 seconds to run I don't think it makes much difference.

Answer 4

I came across this thread through the same Project Euler exercise.

I successfully solved the problem by implementing hmakholm's advice in Python:

class PGenerator:
    def __init__(self, n_min, n_max):
        self.min = n_min
        self.max = n_max

        self.queue = [PChild(n_max, n_min, n_max), ]
        self.yielded = []

    def __iter__(self):
        while len(self.queue) > 0:
            # get next child
            next_child: PChild = max(self.queue, key=lambda child: child.prod_next)

            if not next_child.active:
                self.activate(next_child)

                if next_child.prod_next in self.yielded:
                    self.update_children()
                    continue

            yield_val = next_child.prod_next
            self.yielded.append(yield_val)
            yield yield_val

            self.update_children()

    def update_children(self):
        to_remove = []

        for e, child in enumerate(self.queue):
            if not child.active:
                continue

            child.update_next(self)

            if child.mul_next < self.min:
                to_remove.append(e)

        for i in to_remove:
            del self.queue[i]

    def add_child(self, n):
        new_child = PChild(n, self.min, self.max)
        self.queue.append(new_child)

    def activate(self, child: "PChild"):
        child.active = True

        new_n = child.n - 1
        if new_n >= self.min:
            self.add_child(new_n)


class PChild:
    def __init__(self, n, mul_min, mul_max):
        self.n = n
        self.mul_min = mul_min

        self.mul_next = mul_max
        self.prod_next = n * self.mul_next

        self.active = False

    def update_next(self, master: PGenerator):
        self.mul_next = self.get_next_multiplier(master)
        self.prod_next = self.mul_next * self.n

    def get_next_multiplier(self, master: PGenerator):
        m = self.mul_next
        while m >= self.mul_min:
            p = m * self.n

            if p not in master.yielded:
                return m

            m -= 1

        return m



from math import floor


def is_palindrome(n: int) -> bool:
    n = str(n)

    mid_point = floor(len(n) / 2)

    left = n[:mid_point]
    right = ''

    if len(n) % 2 == 0:
        right = n[mid_point:]
    else:
        right = n[mid_point + 1:]

    return left == right[::-1]


for i in PGenerator(100, 999):
    if is_palindrome(i):
        print(i)
        break

However, it took me ages to write; I feel that there must be a simpler solution.