[Tutor] project euler #4

[Oscar Benjamin]

On Mon, 11 May 2020 at 19:08, Mats Wichmann <mats at wichmann.us> wrote:
>
> On 5/11/20 5:17 AM, DL Neil via Tutor wrote:
> >
> > That said, this algorithm is attempting to solve the problem in a
> > mathematical fashion. It will only work with numbers.
<snip>
>
> The Euler problems are attempting to teach _mathematical_ concepts
> (encouraging the use of a computer to assist), while where here on the
> list tend to approach problems as ones of what are optimal Python
> approaches.

Optimal Python approaches should bear in mind the problem which in
this case *is* mathematical. The Euler problem is here:
https://projecteuler.net/problem=4

I think the intention behind the problem is not how to implement
is_palindromic efficiently but how to reduce the search space so that
you don't have to call is_palindromic for all of the 1000*1000
possibilities.

In the 2 digit example given in the Euler problem the question would
be to find the largest palindromic number that is a product of two 2
digit numbers. For that you might loop over the 10000 possible pairs
of two digit numbers or you could reason it through:

We want the largest Z = X*Y where Z is palindromic and X and Y are 2
digit numbers.

1. The largest possible product of two 2 digit numbers is 99*99 = 9801
which is not palindromic but it shows how high we can go. Let's make
the ansatz that Z is a 4 digit number with leading coefficient 9.

2. Our assumption implies that X and Y both have 1st digit 9 because
the largest possibility not satisfying that is too small: 89*99 <
90*100 == 9000.

3. Since the 1st digit of Z is 9 the last digit is 9 as well so Z is
like 9??9. Since the final digit is 9 we know that the last digits of
X and Y have to have a product with last digit 9 so they have to be
both odd and not 5 i.e. 1, 3, 7, or 9. There are only 3 possibilities
for the last digits: (1, 9), (3, 3), (7, 7).

4. That leaves 3 possibilities to test:

>>> 91*99
9009
>>> 93*93
8649
>>> 97*97
9409

So we see that 9009 is the largest palindromic number that is a
product of two 2 digit numbers. We assumed a leading digit 9 but
clearly anything else would be smaller so we don't have to consider
the other possibilities.

In this example we can reduce the search space from 10000 to 3 which
is enough to calculate by hand. In the 3 digit case the brute force
search space is 100x bigger but can still be reduced substantially.

--
Oscar