I've been working through The Art and Craft of Problem Solving, and there's been a few problems in it based on Pascal's Triangle. After some hours of scribbling numbers on paper, I got lazy and wrote up a generator for it in Python. The book wants the reader to examine some of the properties of the triangle, so I had my triangle renderer (renderer? ha, it's text!) take a function that'd return a boolean to determine if something should be shown or not. While scribbling odd and even values of the triangle on paper, I noticed that it kind of resembled Sierpinski's triangle, so I started with that.

Now this looked pretty neat to me, so I was thinking of another easy pattern I could look for. Perfect squares came to mind; just check to see if the square root of a number is an integer and you're all setup, right? I tried passing that function into the triangle renderer and beheld an interesting result.

It appeared as if perfect squares formed a kind of parabola past 100 rows of the triangle! What a discovery! Of course, I'm really doubting my naive perfect square test at this point, so I googled up a better one and tried that out. A less interesting result awaited me:

Even though I hadn't made the amazing discovery that perfect squares existed, buried within Pascal's triangle in an almost perfect parabola, I had learned to distrust floating point tests on gigantic integers. So there's that.

Code Follows:

def pascal_generator():

last = []

while True:

next = [last[i]+last[i-1] if 0 < i < len(last)

else 1 for i in range(len(last)+1)]

yield next

last = next

def pascal_string(size, shade_function=lambda x:True):

result = "\n"

p = pascal_generator()

for i in range(size):

row = p.next()

strrow = " ".join(["#" if shade_function(x)

else " " for x in row ])

result += "%s #%d = %d\n" % (

strrow.center(size*2),

i+1,

sum([1 for x in row

if shade_function(x)]))

return result

def is_odd(x):

return x % 2 == 1

def is_fsquare(x):

return int(math.sqrt(x)) == math.sqrt(x)

def is_isquare(apositiveint):

x = apositiveint // 2

seen = set([x])

while x * x != apositiveint and x > 0:

x = (x + (apositiveint // x)) // 2

if x in seen: return False

seen.add(x)

return True

if __name__ == "__main__":

#print pascal_string(140, is_odd)

#print pascal_string(140, is_fsquare)

print pascal_string(140, is_isquare)