[SEAV Softwares Logo]



Home Page
Program Nook
Instructional
Open Forum
Portfolio
Visitor's Area
Connections
About the Site

Case Study Problem A3
The License Plate Curiosity
Number Theory / Intermediate level

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.



The Solution


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.
Left = INT(Number / 1000)
Right = Number - Left * 1000

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 math—something which you should know is very fast.
Left = Number \ 1000
Right = Number MOD 1000

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!)
Difference = ABS(Left - Right)

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:
100,000 <= N2 <= 999,999
316.228 <= N   <= 999.999

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.
Listing A3.1


DEFINT A-Z
CLS
PRINT "SQUARE", "ROOT"

FOR Num = 317 to 999

  ' Get the six-digit square
  Square& = 1& * Num * Num

  ' Compute the difference
  Left = Square& \ 1000
  Right = Square& MOD 1000
  Difference = ABS(Left - Right)

  IF Difference = 1 THEN PRINT Square&, Num

NEXT

The output of this program is the following, and these numbers are the correct answers:
SQUARE        ROOT
 183184        428
 328329        573
 528529        727
 715716        846
Difference of 4, 9, and 2. Answering the other three questions of whether there are six-digit numbers having left- and right-hand differences of 4, 9, and 2 is very simple. Simply replace the 1 found in the conditional expression with 4, then 9, then 2. For a difference of 4, the squares are 205209, 300304, 477481, and 732736. For 9, the answers are 216225, 287296, 515524, and 675684. There are no six-digit squares which have a difference of 2 between the left-most and right-most three digits.

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.
Listing A3.2


DEFINT A-Z
CLS
PRINT "SQUARE", "ROOT", "DIFFERENCE"

FOR Num = 317 TO 999

  ' Get the square
  Square& = 1& * Num * Num

  ' Compute the difference
  Left = Square& \ 1000
  Right = Square& MOD 1000
  Difference = ABS(Left - Right)

  ' Compare the difference
  IF Difference > MaxDiffer THEN
    PRINT Square&, Num, Difference

    ' Replace the difference
    MaxDiffer = Difference
  END IF

NEXT

Curious for the answer? Well, below is the program's output. Hey! the largest difference, 997, came from the largest square! Hmmm...
SQUARE        ROOT          DIFFERENCE
 100489        317           389
 101761        319           660
 104976        324           872
 912025        955           887
 937024        968           913
 984064        992           920
 986049        993           937
 988036        994           952
 990025        995           965
 992016        996           976
 994009        997           985
 996004        998           992
 998001        999           997
Four-digit squares with a difference of one. Adapting our original program to test four-digit squares require that we change how we extract the left- and right-hand digits as well as changing the domain of the loop from 32 to 99 (so that the squares would have four digits).
Listing A3.3


DEFINT A-Z
CLS
PRINT "SQUARE", "NUM"

FOR Num = 32 TO 99

  ' Compute the four-digit square
  Square = Num * Num

  ' Obtain the difference
  Left = Square \ 100
  Right = Square MOD 100
  Difference = ABS(Left - Right)

  IF Difference = 1 THEN
    PRINT Square, Num
  END IF

NEXT

If you run the program in Listing A3.3, you'll find out that there's only one such square: 8281.

Additional Problems


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:
CubeRoot! = Number ^ (1/3)
IF INT(CubeRoot!) = CubeRoot! THEN
  ItsACube = True
END IF

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.
Middle = (Number \ 100) MOD 100
Middle = (Number MOD 10000) \ 100

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.

Reference: Snover, Stephen L. and Spikell, Mark A. "The License Plate Curiosity." Readings from the Mathematics Teacher. Volume 1 No. 1. From the Math Department of the Ateneo de Manila University, Philippines.



Go back to the Case Study page.

Home Page | Program Nook | Instructional | Open Forum
Portfolio | Visitor's Area | Connections | About the Site

Copyright © 1997-1999, SEAV Softwares. All rights reserved.
Webmaster: Eugene Villar (SEAV); e-mail: [email protected]