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)