LinkBack URL
About LinkBacksWhich are the lowest and highest nine digit perfect squares that include all the numbers from one to nine without the repetition of any number?
Every nine digit number composed of all the digits from 1 through 9, is divisible by 9, so that's not much help. -- except that the square root of the number must be divisible by 3.
Look at the result of squaring each of the digits 1 through 9, -- particularly look at the one's digit of the result. -- the ten's digit may be handy as well.
What is the range of the numbers whose squares have nine digits? Narrow that down a bit, to numbers between the square root of 123456789 ≈ 11112, and the square root of 987654321 ≈ 31428 .
This is one of my favorite problems, and you have already been given some excellent advice. I have written computer programs to find all 30 solutions (in many languages-- as I said, the problem is a favorite of mine).Originally Posted by PASCALfan
The problem dates back at least to "Amusements in Mathematics" by H.D. Dudeney, first published in 1917. Like you, Dudeney asked for the largest and smallest squares, and he gives the answers in the book. Obviously he did not use a computer in 1917. I wish I knew how he got the answers, but I don't. The solution in the book simply gives the two numbers with no hint of how they were derived. I think Dudeney knew at least the "casting out nines" property, which is enough to conclude that each square is divisible by 9, but my impression of him is that he did not know much more in the way of number theory. I could be wrong about that, of course.
In my first brief introduction to number theory, many years ago, my instructor mentioned this problem and pointed out the nines business. He said that he had solved the problem completely, finding all 30 solutions "by hand", and that his method involved just a little more number theory than we knew at the time. I have often wondered since then just what bit of number theory he had in mind, but I have never figured that out. If anyone has any ideas along those lines, I wish they would post them.
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
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).
  |
