#A029948 Smallest prime containing n-th square as substring. #Take square, then add digits around it and check for primality. from math import sqrt prlist = [2,3,5,7] ptop = 0 def fillprlist(n): for i in xrange(9,n,2): top = int(sqrt(i)) + 1 addit = True for j in xrange(3,top,2): if i % j == 0: addit = False break if addit: prlist.append(i) ptop = prlist[-1]**2 def isprime(n): if n < 2: return False if n == 2: return True sn = int(sqrt(n))+1 for p in prlist: if p > sn: return True if n % p == 0: return False raise "Need more primes" def sminp(sm,a): if isprime(a): if sm == -1: return a return min(sm,a) return sm fillprlist(1000000) n = 1 print "0 101" while n < 10001: n2s = str(n*n) small = -1 for i in range(1,10): ip = int(n2s + str(i)) small = sminp(small,ip) ip = int(str(i) + n2s) small = sminp(small,ip) if small == -1: for i in range(0,100): if i < 10: ip = int(n2s + "0" + str(i)) else: ip = int(n2s + str(i)) small = sminp(small,ip) ip = int(str(i) + n2s) small = sminp(small,ip) for i in range(1,10): for j in range(1,10): ip = int(str(j) + n2s + str(i)) small = sminp(small,ip) if small == -1: print "n = " + str(n) + " n2s=" + n2s raise("try more!") print str(n) + " " + str(small) n += 1