' Puzzlet #029
' Find denary integers which, when squared
' and converted to binary, produce numerical
' palindromes. Limit the search to a maximum
' value of 20,000 (before squaring. Example:
' 3^2 = 9 (denary) = 1001 (binary), a
' palindrome.
' By Dave Ellis.
declare DecToBin(d: int)
declare Palindrome(p$: string)
declare PrintResults()
def denary, square: int
def binary$: string
openconsole
print "Calculating ...": print
print "Denary Squared Binary": print
denary = 1
do
square = denary * denary
binary$ = DecToBin(square)
if Palindrome(binary$)
PrintResults()
endif
denary = denary + 1
until denary > 20000
print: print "No more!"
print: print "Press a key to exit ... ",
do: until inkey$ <> ""
closeconsole
end
sub DecToBin(d)
' converts integer d into its binary
' equivalent and returns it as a string
def num: int
def bin$: string
num = d
bin$ = ""
do
if num % 2 > 0
bin$ = "1" + bin$
else
bin$ = "0" + bin$
endif
num = num/2
until num = 0
return bin$
sub Palindrome (p$)
' if p$ is a numerical palindrome,
' returns 1, else returns 0
def flag, i, j, L: int
L = len(p$)
j = int(L/2)
i = 1
flag = -1
do
q$ = mid$(p$, i, 1)
r$ = mid$(p$, L + 1 - i, 1)
if q$ <> r$
flag = 0
endif
i = i + 1
until flag = 0 | i > j
return flag
sub PrintResults
' pretty printer
print using ("######", denary),
print using ("###########", square),
print " ", binary$
return
PROGRAM NOTES
Variable denary holds the integer (in base 10) currently being investigated. The code initialises its value to 1, and the DO loop increments this one at a time to 20,000. Variable square holds the square of the current value of denary. Those two variables and the following lines of code (which I've numbered to make the explanation clearer) are all you need to understand the program:
Line 1 opens the iterative DO loop.
1
2
3
4
5
6
7
do
square = denary * denary
binary$ = DecToBin(square)
if Palindrome(binary$)
PrintResults()
endif
denary = denary + 1
until denary > 20000
Line 2 squares denary's current value and stores it in square.
Line 3 converts square's value to its equivalent binary form and stores the result as a string in binary$. The reason for using strings here is that the binary numbers can become very long. At the time of writing, Ibasic's integers could only cope with denary numbers up to 231 - 1 (2,147,483,647). Even a value as small as 20,0002 in denary is 10111110101111000010000000000 when converted to binary. If interpreted as denary this would cause an overflow.
Line 4 checks binary$ to determine if it's a numerical palindrome, using the function Palindrome. If the function call returns -1 (TRUE), we have a valid solution, and it's printed out by a call to the PrintIt subroutine on Line 5.
Line 6 increments denary's value ready for the next investigation.
Line 7 checks that denary's value isn't greater than 20,000. If it's not, the DO loop is executed again. If it is, the program ends.
There are thus 5 answers in all, including the example given and the trivial result for 1.
Calculating ...
Denary Squared Binary
1 1 1
3 9 1001
4523 20457529 1001110000010100000111001
11991 143784081 1000100100011111100010010001
18197 331130809 10011101111001010011110111001
No more!
Press a key to exit ...
MAIN MENU
DOWNLOAD CODE
ARCHIVES
Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 22nd, 2004.