Page 2 of 2 FirstFirst 12
Results 16 to 20 of 20

Math Help - Perfect Squares

  1. #16
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Perfect Squares

    Quote Originally Posted by Wilmer View Post
    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
    Follow Math Help Forum on Facebook and Google+

  2. #17
    MHF Contributor
    Joined
    Dec 2007
    From
    Ottawa, Canada
    Posts
    3,102
    Thanks
    68

    Re: Perfect Squares

    Quote Originally Posted by CaptainBlack View Post
    ...transmogrified...
    Oui
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Perfect Squares

    Quote Originally Posted by CaptainBlack View Post
    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
    100x + 5a where a is odd and in the range 0 through 19
    then its square is
    10000 x^2 + 1000 ax + 25 a^2
    so the last two digits are determined by
    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]
    Last edited by awkward; July 31st 2011 at 06:34 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Perfect Squares

    Quote Originally Posted by CaptainBlack View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    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
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. Perfect Squares
    Posted in the Math Puzzles Forum
    Replies: 1
    Last Post: July 19th 2010, 12:36 AM
  2. Perfect squares of n and n+99
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 7th 2010, 10:55 AM
  3. perfect squares
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 13th 2009, 03:20 AM
  4. perfect squares
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 11th 2009, 05:49 PM
  5. Perfect Squares
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: March 18th 2007, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum