' Puzzlet #021.
' Find a 10-pandigital (that is, an integer which
' contains all the digits 0123456789 once and once
' only, in any order) which is also a perfect square,
' and whose square root has the odd property of
' looking the same upside down as the right way up!
' (Assuming only the digits 0, 1, 6, 8, and 9 have this
' property).
' By Dave Ellis.
declare prodStrings(mult1$: string, mult2$: string)
declare panDigital_10(p$: string)
declare invertPal(p$: string)
def n: int
def n$, product$: string
openconsole
print "Searching ..."
for n = 60009 to 99166
n$ = ltrim$(str$(n))
if invertPal(n$)
product$ = prodStrings(n$, n$)
if PanDigital_10(product$)
print: print product$, " = ",n$, "^2"
endif
endif
next n
print: print "No more found."
print: print "Press any key to exit ..."
do: until inkey$ <> ""
closeconsole
end
sub prodStrings(mult1$, mult2$)
' Multiplies the numeric values of two integer
' strings and returns the product as a string.
def it1, it2, Lmult1, Lmult2: int
def i, L1, L2: int
def topMult, bottMult: int
def topSum, bottSum: int
def prodTopBott, carryProd: int
def SumTopBott, carrySum: int
def temp$, temp1$, temp2$, temp3$, temp4$: string
' intitialise product loop
Lmult1 = len(mult1$): Lmult2 = len(mult2$)
temp$ = ""
' main prod loop
for it1 = 1 to LMult1
temp$ = string$(Lmult1 - it1, "0")
bottMult = val(mid$(mult1$,it1,1))
carryProd = 0
for it2 = Lmult2 to 1 # -1
topMult = val(mid$(mult2$,it2,1))
prodTopBott = carryProd + topMult * bottMult
if prodTopBott > 9
carryProd = int(prodTopBott/10)
prodTopBott = prodTopBott % 10
else
carryProd = 0
endif
temp$ = ltrim$(str$(prodTopBott)) + temp$
next it2
if carryProd > 0
temp$ = ltrim$(str$(carryProd)) + temp$
endif
' add intermediate products
' initialise add variables
temp1$ = temp$: temp2$ = temp4$
L1 = len(temp1$): L2 = len(temp2$)
' pad out shorter string with leading 0's
if L1 <> L2
if L1 > L2
temp2$ = string$(L1 - L2, "0") + temp2$
else
temp1$ = string$(L2 - L1, "0") + temp1$
endif
endif
' set iterator to max string length
if L2 > L1
i = L2
else
i = L1
endif
' intialise add loop
temp3$ = ""
carrySum = 0
' main add loop, adds two digits at a time
do
topSum = val(mid$(temp1$, i, 1))
bottSum = val(mid$(temp2$, i, 1))
sumTopBott = topSum + bottSum + carrySum
if sumTopBott > 9
carrySum = 1
sumTopBott = sumTopBott % 10
else
carrySum = 0
endif
sum$ = ltrim$(str$(sumTopBott))
temp3$ = sum$ + temp3$
i = i - 1
until i < 1
if carrySum = 1
temp3$ = "1" + temp3$
endif
temp4$ = temp3$
next it1
return temp4$
sub PanDigital_10(p$)
' checks that p$ contains every digit 0123456789
' once and once only, in any order.
def psn, flag, i, L: int
L = len(p$)
i = 1
flag = 1
' is p$ the right length (10 digits)?
if L <> 10
flag = 0
' if right length, does it have the right digits?
else
test$ = "1234567890"
i = 1
do
i$ = mid$(p$, i, 1)
if i$ = "0"
j$ = "0"
psn = 10
else
j$ = mid$(test$, val(i$), 1)
psn = val(j$)
endif
if j$ = i$
replace$(test$, psn, 1, "X")
endif
i = i + 1
until flag = 0 | i > 10
if test$ <> "XXXXXXXXXX"
flag = 0
endif
endif
return flag
sub InvertPal(p$)
' if p$ looks the same upside down as it does
' the right way up, returns 1, else returns 0.
def a, flag, L: int
def a$, q$, r$: string
L = len(p$)
a = 1
' Check for presence of illegal digits.
do
select mid$(p$, a, 1)
case "2"
case "3"
case "4"
case "5"
case "7"
flag = 0
default
flag = 1
endselect
a = a + 1
until flag = 0 | a > L
' if no illegal digits, check each digit is
' palindromic with its upside-down version.
if flag
a = 1
do
a$ = mid$(p$, a, 1)
select a$
case "1"
case "8"
case "0"
if mid$(p$, L + 1 - a, 1) <> a$
flag = 0
endif
case "6"
if mid$(p$, L + 1 - a, 1) <> "9"
flag = 0
endif
case "9"
if mid$(p$, L + 1 - a, 1) <> "6"
flag = 0
endif
endselect
a = a + 1
until flag = 0 | a > L/2
endif
return flag
PROGRAM NOTES
We commence by thinking about the best way to set up a search. You could generate every possible pandigital and then check to see if it's a perfect square. Or you could generate all the ingegers whose squares are ten digits long.
The former course gives a range of 9876543210 - 1234567890 = 8.6 billion. The latter gives root(9876543210) - root(1234567890) = 64,244. This would reduce the search range from something so large even a modern computer would be very slow to complete to something that can be run in a few seconds. Needless to say, the program follows the shorter method!
Root (1234567890) = 35136 and root(9876543210) = 99380. But we're limited to using only digits 0, 1, 6, 8, and 9, and the answer must look the same both ways up. Therefore, the range must begin at the next integer larger than 35136 fitting these rules, that is, 60009, and end with 99166.
Now we have a search range established which is only 39,158 integers long inclusive. This will run very quickly.
To make it simpler to explain how the program works, I'm going to number the important lines from the main routine, like this:
Line 1: Sets up a FOR loop to conduct the search over the range derived in the notes above, using iterator n.
- for n = 60009 to 99166
- n$ = ltrim$(str$(n))
- if invertPal(n$)
- product$ = prodStrings(n$, n$)
- if PanDigital_10(product$)
- print: print product$, " = ",n$, "^2"
Line 2: For every integer to be investigated by n, a string version of it is created in variable n$.
Line 3: Submits n$ to function InvertPal(), whose job is to examine the argument for "upside-down-ness" - that is, does it look the same both ways up? See below for comments on how the function works.
Line 4: If InvertPal() returns TRUE (1) then line 4 is executed. n$ is submitted to ProdString(), whose function is to take two strings and multiply their absolute values together, returning the result in string form which is saved in variable product$. See below for comments on how the function works.
Line 5: Submits the returned value of product$ to the function PanDigital_10(), which returns TRUE if product$ contains all the digits 0 to 9 inclusive once and once only, FALSE otherwise. This has been used recently, in Puzzlet #020. Check there for a description of how the funtion works.
Line 6: If PanDigital_10() returns TRUE, we have a valid solution and it's printed out by line 6.
The program goes on to apply this process to every integer in the search range before finally quitting.
Two of the functions here are of interest to the programmer. Let's look at InvertPal() first.
InvertPal() begins by checking for the presence of illegal charcters, that is, 2, 3, 4, 5, or 7. If any of these characters are found, local variable flag is set to 0 (FALSE) and the function is quit, returning flag's value.
Assuming no illegal characters are found, each character has now to be examined in turn for a match with its corresponding character at the other end of the string being tested. For example, the first character must equal the upside-down version of the last, the second character must equal the upside-down version of the last but one, etc.
This is fairly easy to do. If a character is equal to 0, 1, or 8, its match has to be exactly equal, since these three all appear the same upside down. If a character is equal to a 6 or 9, its match must be a 9 or 6, the upside-down versions respectively.
ProdString() is a weighty subroutine. The maximum possible number generated by the program is 99166² = 9833895556. At the time this program was written, IBasic couldn't handle any integers larger than 2^31 - 1, which equates to 2147483647. So the program would crash if it relied on IBasic to do the multiplication here.
ProdString() was written to overcome the problem. Current levels of IBasic can handle much larger numbers - up to 2^63 - 1, which comes out to the rather large integer 9223372036854775808, so the special function is no longer necessary, but it was in those days.
The great advantage of ProdString() is that it can still handle bigger integers than even modern basic. It is limited only by string lengths. Ibasic allows strings up to 254 characters, so the ProdString() can handle answers up to 254 digits long. If I dug around, I could probably find a way to use IBasic's IString, which holds up to 65,536 characters!
I don't propose to give a detailed explanation of how this function works here, since we're bound to come across it later in the Puzzlet series when some seriously huge numbers make their appearance and IBasic wouldn't be able to cope on its own. When that happens, I'll give a comprehensive breakdown of it.
There is only one solution to this Puzzlet. In spite of the large integers involved, it only takes a few seconds to run.
Searching ...
9814072356 = 99066^2
No more found.
Press any key to exit ...
MAIN MENU
DOWNLOAD CODE
ARCHIVES
Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 22nd, 2004.