June 22, 2009

Maths Challenge #10 – Perfect Square

What is the largest perfect square number that uses each digit 123456789 exactly once?


- 7 comments by 3 or more people Not publicly viewable

[Skip to the latest comment]
  1. Sadiq

    923187456

    22 Jun 2009, 12:15

  2. Simon Whitehouse

    Nope, beaten me. A bit of Googling comes up with the same answer as Sadiq but I can’t come up with any neat and fancy way of getting to it by using any known properties of square numbers.

    I got as far as the first digit being ‘3’ (probably) – to give the 9 at the start of the square. Oh, and that it couldn’t end in ‘5’. After that I was just counting down from 31426 (first number whose square is less than 987654321)

    So, what’s the trick? Or were we supposed to be writing algorithms to work it out?

    22 Jun 2009, 19:40

  3. Eleanor Lovell

    Ok, so this week it was a toughy! Sadiq did get the answer right – 923187456 (what was your working Sadiq?)...and Si, you seemed to make the right assumptions but gave up at the long and tedious bit : )

    Here’s Prof Ian Stewart’s explanation…

    “Since we want the largest number of its type, it’s a fair bet that the answer starts with 9, so this really has to be tried first, even if it turns out to be false. Squares end in 0, 1, 4, 6, or 9, and those digits only. Since we’ve used 9, it’s likely that the number we want looks like 9***6, so it lies between 912345786 and 987543216, bearing in mind that all digits are different. The square roots of these are 30205.1 and 31425.2. So all we have to do is square the numbers between 30206 and 31424 and see which give all 9 nonzero digits. There are 1219 such numbers, but to get the square ending in 6 the number must end in 4 or 6, so only 2 out of every 10 need be considered. That gives just over 240 numbers. Work backwards from 31424, and a mere 208 attempts will lead you to 30384.

    “There are some short cuts that eliminate more possibilities and save work. Anything ending in 14 or 64, for instance, gives something ending 96 when squared, but we want the 9 at the front. The same goes for 36 and 86. This reduces the possibilities by 20%.”

    Can’t believe more of you didn’t get it! ; )

    23 Jun 2009, 15:28

  4. Steve Rumsby

    So it seems there was no real alternative to writing something program-ish to test all the possibilities. I was hoping for a trick to eliminate more possibilities. I say “program-ish” because I guess you could concoct something in Excel? I haven’t quite got around to that bit of the problem.

    I spot a bug in the explanation, though. “Squares end in 0, 1, 4, 6, or 9” should say “Squares end in 0, 1, 4, 5, 6, or 9” surely? So there are a few more possibilities to check…

    23 Jun 2009, 15:59

  5. Simon Whitehouse

    Prof Ian Stewart said “Squares end in 0, 1, 4, 6, or 9, and those digits only. Since we’ve used 9, it’s likely that the number we want looks like 9***6”

    That’s a bit of a leap. Why?

    I can rule out the 0 and the 9 as 0 doesn’t appear in the final number and we are using 9 at the start.

    Steve’s right that “Squares end in 0, 1, 4, 5, 6, or 9”, so that leaves the number ending in 1, 4, 5, or 6 But, “if the last digit of a number is 5, its square ends in 25 and the preceding digits must be 0, 2, 06, or 56”

    OK, so I’m quoting Wikipedia, and I haven’t got a proof for it, but it seems to be right. Making that rather large assumption, then note that squares ending in 5 must also have roots which end in 5 and so match the pattern above and

    025
    225
    0625
    5625

    either contain 0 or repeated digits. So, that’s 5 discounted as the last number. Which leaves us with 1, 4 or 6.

    But, I think that there is one other way of reducing the numbers that need to be checked. Any combination of the numbers 1 to 9 will add up to 45, which means that the answer is divisible by 9. In order for the square of a number to be divisible by 9 then its root must also be divisible by 9.

    So, if we combine that with Prof Ian’s assertion that the square ends in a 6, then for the root we only need check numbers ending with 4 or 6, which are also divisible by 9, counting down from 31374, which is the first number below 31424 which matches this. We don’t need to check any numbers ending in 14, 64, 36 or 86.

    30384 is the 19th number to be checked.

    Maths is just the application of laziness, isn’t it really?

    23 Jun 2009, 18:56

  6. Simon Whitehouse

    Ooops. If a square is divisible by 9 then its root must be divisible by 3. Which doesn’t reduce the numbers to be checked by nearly as much.

    23 Jun 2009, 19:15

  7. Maybe this is considered cheating, but for me the question begs to be solved through the use of programming. I propose the following solution in Python. It isn’t very elegant, but it does the job in less than a second. (NB: Comments in python are marked by ’#’)

    import string          # Don't worry about this
    i=1                      # An index we will need later
    
    # 31427^2 = 987656329 > 987654321
    #  so we only need to check all
    #  numbers between 1 and 31427
    
    for n in range(1,31427):
    
     n2=n**2        # n2 is n squared
     s=str(n2)       # s is n squared, but as a string
    
     # Check if all digits from 1 to 9 are in s
     if string.find(s,"1")>-1 and string.find(s,"2")>-1 and string.find(s,"3")>-1 and string.find(s,"4")>-1 and string.find(s,"5")>-1 and string.find(s,"6")>-1 and string.find(s,"7")>-1 and string.find(s,"8")>-1 and string.find(s,"9")>-1:
    
      print i             # Index
      print n2          # A square containing digits from 1 to 9
      print               # A blank space
      i +=1              # Increase index

    From this, we get 30 perfect squares that contain the digits from 1 to 9 exactly once, the smallest one being 139854276, and the largest one being Sadiq’s number.

    Alright, I’m not really using any actual maths, but in terms of laziness I think I get a pretty good score :p

    23 Jun 2009, 21:13


Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

About Warwick Challenges

Warwick Challenges are mini academic challenges from University of Warwick professors, set via the micro-blogging service Twitter (and also via this blog).
More
Follow us on Twitter

June 2009

Mo Tu We Th Fr Sa Su
May |  Today  | Jul
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30               

Search this blog

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXIX