Thread: Perfect Squares

Originally Posted by Wilmer

I prefer sticking digits together to taking a number apart (even if it takes a little longer);
keeping last digit at 1,4,5,6,9 and looping others such that none of the 9 are the same:
201600 "examinations" required (5 * 8!), taking 4 seconds (using UBasic).

Unfortunately the problem has transmogrified into finding the smallest and largest number with the required properties by hand as Dudeney must have done.

(sorry I may not have mentioned the change in the problem)

CB

Originally Posted by CaptainBlack

...transmogrified...

Oui

Originally Posted by CaptainBlack

The ideas that reduce the size of search space are:

You are searching the squares of the numbers in the range ceiling(sqrt(123456789) to floor((sqrt(987654321)) also these roots should be divisible by 3, these reduce the number of possibilities to ~6800.

Maybe someone can suggest other means of reducing the search space size.

CB

Here are some observations that reduce the search space somewhat.

There are only 22 possibilities for the last 2 digits of a perfect square:

00 01 04 09 16
21 24 25 29 36
41 44 49 56 61
64 69 76 81 84
89 96

These can be obtained by scanning a table of the squares of the numbers 0-99. Each of the 2-digit endings has 4 "square roots" in 0-99 except for 00 and 25, which have 10 each. We can reject 00, 01, 04, 09 and 44 as not meeting the constraints of the problem. And if we look a little deeper into the 10 "square roots" of 25, we find that only 25^2 and 75^2 will work for us because the squares of all the other "square roots" end in 025 or 225.

Let's say we are working on the first part of the problem,finding the smallest square consisting of the digits 1-9. We may tentatively assume that the first digit will be 1. With this assumption we can rule out the squares ending in 1, leaving us with

16 24 25 29 36
49 56 64 69 76
84 89 96

-- 13 possibilities in all, with 50 "square roots" in 0-99 (taking into account the observation about "square roots" of 25 above). So we have reduced the search space by 1/2.

[edit]I didn't express that part about the square roots of 25 clearly. What I mean is that if you have a number of the form
where a is odd and in the range 0 through 19
then its square is

so the last two digits are determined by

and we only have to check a few possibilities to find out that only a = 5 and a = 15 will work, so 5a = 25 or 75.
[/edit]

Originally Posted by CaptainBlack

Unfortunately the problem has transmogrified into finding the smallest and largest number with the required properties by hand as Dudeney must have done.

(sorry I may not have mentioned the change in the problem)

CB

The fact that Dudeney asks for the largest and smallest suggest that his search space was not quite as small as he might have liked. Searching from the top downwards until one finds a solution and then from the bottom upwards requires far less work than finding the 10th largest (which project Euler might have asked for if mechanised search were not so easy).

CB

I just found that the 30 solutions to the problem are sequence A071519 in the Sloan On-Line Encyclopedia of Integer Sequences:

A071519 - OEIS