While driving along the highway, I noticed that the license plate ahead of me was 183184. "Curious," I thought, "the left-most three digits and the right-most three digits form numbers that differ by 1. Furthermore, the license plate number is a perfect square!"
Is there any other number that has these same properties, namely, a six-digit square number with left and right halves that differ by 1? What are all the six-digit squares whose difference between the left and right halves is 4? Is 9? Is 2? What's the largest such difference?
What are all the four-digit squares with a difference of 1 between the left-most and right-most pairs of digits?
Download the A3 Zip file containing this page plus QBASIC files for you to try.
Go back to the Case Study page.
This problem is a good candidate for solving through the use of the computer. A simple problem, yet if you try finding the numbers using just pen and paper, it's possible that you'd spend the better part of the night doing sums and products. With a computer, you just type in several lines, run the program, and presto! You have solved one of life's greatest mysteries!
Separating the left and right digits. One of the first things we have to program is a way of extracting the left three digits and the right three digits of a given six-digit number. The program code used by the person who wrote this puzzle (who used GW-BASIC) is one of the simplest methods albeit it is very obtuse.
The logic is that the left-most three digits are the number of thousands in the number and the right-most digits are what's left over. Following is a more "modern" and clearer way. The INT function is replaced by integer division and the right-hand digits are obtained using the MOD operand. This way, both groups are obtained in just one step each. Plus the calculations are pure integer mathsomething which you should know is very fast.
Getting their difference is the next step. We do this by subtracting one from the other and taking the absolute value. (If you haven't figured this out, then you have no right to call yourself a programmer!)
Now, we have almost everything we need to code in the program!
Six-digit squares. By this time, you probably figured out that we could test every six-digit number, see if it's a square, and use the code above to find out if the difference is 1. The problem with that approach is that you still have to devise a test to see if a number is a square.
It would be vastly better to just generate all the six-digit squares. Initial planning tells us that the squares of the integers, 317 to 999, have six digits:
So in our program, we should have a FOR-NEXT loop going through the range 317 to 999 and an inner variable that is assigned the square of those numbers. Take note that the squared variable has to be in long integer format or you'll get overflow errors.
Final program. Listing A3.1 contains the final program. Here, we print both the six-digit square and its root.
The output of this program is the following, and these numbers are the correct answers:
The largest difference. To answer the question of what is the largest such difference possible, we have to revise the program a bit. We now introduce the concept of the Current Maximum/Minimum variable (at least that's how I refer to it). Anyway it works like this: As you scan each and every data (that is not sorted in the desired order), the Current Max/Min variable will keep track of the last piece of data that matched your specifications. The only problem many programmers have with this technique is that they forget to initialize the variable first.
For instance, if you're searching for the smallest number in a list of integers and you leave the minimum variable uninitialized at zero, you might end up with zero as the smallest number!
Going back to our problem, let's designate MaxDiffer to be our special variable. As we compute the difference of each six-digit square, we compare it to MaxDiffer. If the difference proves to be the greater, then we replace MaxDiffer with it, otherwise, we ignore it. We don't have to initialize the variable since we know the difference is greater than zero.
Listing A3.2 shows the program that will solve our puzzle. It also displays all the values MaxDiffer had in its quest for the greatest difference.
Curious for the answer? Well, below is the program's output. Hey! the largest difference, 997, came from the largest square! Hmmm...
If you run the program in Listing A3.3, you'll find out that there's only one such square: 8281.
While we are in the process of solving problems left and right, here are some more teasers for you to try (they're a bit harder, mind you).
Six-digit cubes and powers of two. What are all the six-digit cubes whose difference between the left and right halves is a cube? What about those whose difference is a square?
Two six-digit squares whose groups of two digits are each powers of 2 are 160,801 and 161,604. (From the first number, 16, 8, 1, are powers of two as are 16 and 4 from the second.) Find all six-digit squares with this property. Note that 0 is not a power of 2 (i.e., There's no n that satisfies 2n = 0; 20 = 1 not 0).
Tips and code for solving these problems. Generating six-digit cubes is easy and I'll leave it to you to find the proper loop values. However, testing whether the difference is a cube is much, much harder. There are many ways of doing this. First, you can test a proper range of integers and see if their cubes equal the difference. Or you can create a 1000-dimensioned integer array and turn it into a precalculated table of cubes, and search it for the difference. Or you can obtain the cube root of the difference and see if it's an integer. Since there's no built-in function for cube roots, just use exponentiation:
Testing if the difference is a square is a bit simpler.
To solve the second problem, we need to refine our digit-extracting methods and we need a way to test if a number is a power of 2. Extracting the left-most and right-most pairs is trivial, but the middle pair is more complicated. Yet think of it this way: the middle pair of digits is how many hundreds there are in the remainder when you divide the number by 10000. Below are two code examples of extracting the middle digits. I hope that you will understand it.
To test if a number is a power of two, you can successively divide the number by two and see if it reaches 1. If at any stage the number becomes odd (except when it's 1), then the number is not a power of 2. Alternatively, you can get the logarithm of the number to the base 2 and see if it's an integer. I leave it to you to implement these ideas.
Answers to the two problems. Here are the answers. Use them to check if your program is working correctly.
The six-digit cubes having cubic differences are 125000, 148877, 185193, 216000, 343000, 373248, 512000, 571787, and 729000. The cubes with square differences are 148877, 175616, and 729000. The six-digit squares having powers-of-2 pairs of digits are 160801, 161604, 163216, 166464, 641601, 643204, and 646416.