Monday, January 17, 2011

Pascal's triangle: yet another mindblowing fact

I knew (and at some point understood) the link between Pascal's triangle mod 2 and Sierpinski's triangle, but this is a new discovery:
Project Euler Problem 148
def row(n):
    Cnk = 1
    for k in range(n+1):
        yield Cnk
        Cnk = Cnk * (n-k) / (k+1)

#for i in range(10):
#    print list(row(i))

def div7(x):
    return x % 7 == 0

for i in range(200):
    if i and div7(i): print 
    print sum(div7(x) for x in row(i)),
Output:
0 0 0 0 0 0 0
6 5 4 3 2 1 0
12 10 8 6 4 2 0
18 15 12 9 6 3 0
24 20 16 12 8 4 0
30 25 20 15 10 5 0
36 30 24 18 12 6 0
48 47 46 45 44 43 42
53 50 47 44 41 38 35
58 53 48 43 38 33 28
63 56 49 42 35 28 21
68 59 50 41 32 23 14
73 62 51 40 29 18 7
78 65 52 39 26 13 0
96 94 92 90 88 86 84
100 95 90 85 80 75 70
104 96 88 80 72 64 56
108 97 86 75 64 53 42
112 98 84 70 56 42 28
116 99 82 65 48 31 14
120 100 80 60 40 20 0
144 141 138 135 132 129 126
147 140 133 126 119 112 105
150 139 128 117 106 95 84
153 138 123 108 93 78 63
156 137 118 99 80 61 42
159 136 113 90 67 44 21
162 135 108 81 54 27 0
192 188 184 180 ...
This is... insane!!!

No comments:

Post a Comment