'''
Given a string of digits 0-9, this routine searches for them in the 
square roots of the integers.

---------------------------------------------------------------------------
Copyright (C) 2009 Don Peterson

This program is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later
version.

This program is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU General Public License for more
details.

You should have received a copy of the GNU General Public
License along with this program; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330,
Boston, MA 02111-1307  USA
'''

import decimal, re
from sys import argv

# How many digits to use in the decimal numbers
precision = 1000

# What's the largest integer we should search?
N = 10000

# Regular expression to check input numbers
proper = re.compile(r"^\d+$")

def Usage():
    print '''Usage:  %s num1 [num2...]
Given strings of the digits 0-9, searches the square roots of the numbers 
from 2 to %d (square roots are calculated to a precision of %d digits)
for these strings.  If they are found, the number and locations are
printed.''' % (argv[0], N, precision)
    exit(1)

def CheckNumber(n, want):
    '''Look for the string of digits in want in the number n.  If found,
    print out the square root with a space before the location of the
    number.  Return True if it is found.
    '''
    num = decimal.Decimal(n).sqrt()
    s = str(num)
    pos = s.find(want)
    if pos != -1:
        print "Square root of", n
        print "Found '%s' at location %d" % (want, pos)
        print s[:pos] + " " + s[pos:]
        print
        return True
    return False

def main():
    if len(argv) == 1:
        Usage()
    print "Precision =", precision
    decimal.getcontext().prec = precision
    print "Searching numbers up to", N
    print
    for want in argv[1:]:
        if not proper.match(want):
            print "'%s' is not a proper integer\n" % want
            continue
        for i in xrange(2, N+1):
            if CheckNumber(i, want):
                break

main()