Unfortunately the problem has transmogrified into finding the smallest and largest number with the required propertiesby handas Dudeney must have done.

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

CB

Printable View

- Jul 30th 2011, 06:38 AMCaptainBlackRe: Perfect Squares
- Jul 30th 2011, 09:14 AMWilmerRe: Perfect Squares
- Jul 31st 2011, 06:13 AMawkwardRe: Perfect Squares
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

$\displaystyle 100x + 5a$ where a is odd and in the range 0 through 19

then its square is

$\displaystyle 10000 x^2 + 1000 ax + 25 a^2$

so the last two digits are determined by

$\displaystyle 25 a^2$

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] - Jul 31st 2011, 06:57 AMCaptainBlackRe: Perfect Squares
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 - Jul 31st 2011, 10:43 AMawkwardRe: Perfect Squares
I just found that the 30 solutions to the problem are sequence A071519 in the Sloan On-Line Encyclopedia of Integer Sequences:

A071519 - OEIS