# Perfect Squares

Printable View

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• Jul 30th 2011, 06:38 AM
CaptainBlack
Re: Perfect Squares
Quote:

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(Devil))

CB
• Jul 30th 2011, 09:14 AM
Wilmer
Re: Perfect Squares
Quote:

Originally Posted by CaptainBlack
...transmogrified...

Oui (Thinking)
• Jul 31st 2011, 06:13 AM
awkward
Re: Perfect Squares
Quote:

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.

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 AM
CaptainBlack
Re: Perfect Squares
Quote:

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(Devil))

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
• Jul 31st 2011, 10:43 AM
awkward
Re: 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
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12