how to gradually decrease a product of some numbers by the lowest rate possible

Question

This is actually more of a math question. I need to find the largest palindrome that's the product of two 3-digit numbers. For this my initial solution was a standard double loop with both i,j initialized to 999, where 'i' didn't decrement until 'j' hadn't decreased all the way down to 100. I quickly realized this method did not ensure I 'meet' the palindromes in a decreasing order like I wanted, and that instead I must decrement the indices alternately. My question is, why is that the case? I KNOW that for a product x = bc to decrease as slowly as possible, I need to decrement b,c alternately, but I don't understand WHY that is. I am looking for a theoretical explanation, be it a formal proof or something intuitive.

EDIT: after some of the comments, I feel I should re-write my question: I thought that by decrementing my indices alternatively, I would be decreasing my product by as little as possible every iteration, thus guaranteeing I meet the HIGHEST palindrome first, thus allowing for my code to finish as soon as I meet the first palindrome. Is this not the case? Thank you

Answer 1

If you alternately decrease b and c in x = bc then you will go through 2*900 = 1800 pairs rather than 900^2 = 810000 pairs. Not all of those 810000 pairs lead to distinct numbers (less than half do (227521 to be precise), both because b*c = c*bbut also because factorization into non-primes is not unique). Your alternating strategy misses the majority of products.

There is no simple way to enumerate products in decreasing order. For example, in the case of products of 1-digit numbers if you tried to enumerate pairs (b,c) with b <= c in order of decreasing product, this would be the iteration order:

No simple loop indexing will get you that. You would need to factor the numbers or enumerate all such products and then sort. In either case, this will be less efficient than a straightforward brute-force iteration using standard nested loops.

Note that the above picture will look different if you sorted slightly differently. I formed a 45x3 matrix where the last column was the product and sorted the rows according to that product in decreasing order. But, there are numerous ties in that column e.g. 24 = 3*8 = 4*6. When there are ties, different sorting algorithms might give different sorts. Resolving the ties differently might get you a nicer picture, but it will never give you a simple picture.