## Visualizing Pascal’s triangle remainders

In a comment on my previous post, Juan Valera mentioned something about visualizing multiples of prime numbers in Pascal’s Triangle:

In college, there was a poster with different Pascal Triangles, each of them highlighting the multiples of different prime numbers. The patterns were beautiful.

It sounded like a cool idea, so I decided to try it out. Instead of just highlighting which numbers are a multiple of some prime, I decided to assign a different color to each remainder. So everything divisible by a particular prime will be one color (light gray); everything that leaves a remainder of one when divided by that prime will be another color (blue); and so on.

> {-# LANGUAGE NoMonomorphismRestriction #-}
>
> module Pascal where
>
> import Diagrams.Prelude
> import Diagrams.Backend.Cairo.CmdLine


First, some code to actually generate the numbers in Pascal’s Triangle, mod some divisor. The nextrow function takes a row and adds it with itself, shifted by one, to produce the next row; Pascal’s Triangle itself is generated by iterating nextrow starting from a row with a single 1.

> nextrow :: Integer -> [Integer] -> [Integer]
> nextrow d xs = zipWith (\x y -> (x + y) mod d) (0:xs) (xs ++ )
>
> pascal :: Integer -> [[Integer]]
> pascal d = iterate (nextrow d) 


Here are the colors we’ll use for displaying remainders.

> colors = [ blend 0.3 grey white
>          , blue, red, yellow
>          , green, purple, orange
>          , brown, black, pink
>          , lightblue, lightgreen
>          ]


To help lay out the triangle, we create a path at a 60 degree angle with vertices spaced every two units.

> diag :: Int -> Trail R2
> diag n = fromOffsets (replicate n (2 *^ unitX)) # rotateBy (-1/3) Now, to draw a certain number of rows of Pascal’s Triangle with colors for a given divisor, we turn each row into a horizontal line of colored circles, and then use our rotated path from above as a guide to place the start of each row.

> drawPascal :: Integer -> Int -> Diagram Cairo R2
> drawPascal d rows =
>   decorateTrail (diag (rows - 1))
>     ( map (hcat . map drawCell)
>     . take rows
>     \$ pascal d
>     )


Drawing a single entry of the triangle is just drawing a circle with the right color.

> drawCell :: Integer -> Diagram Cairo R2
> drawCell n = circle 1 # fc (colors !! fromIntegral n) # lw 0


So, let’s draw some triangles! It’s pretty well-known that drawPascal 2 64 gives us a classic Sierpinski gasket: And here’s drawPascal 3 81, which gives us the first 81 rows of Pascal’s Triangle, with each entry colored gray, blue, or red depending on whether it leaves a remainder of 0, 1, or 2 when divided by 3, respectively. The gray regions form a pattern very similar to the Sierpinski gasket, but based on 3 instead of 2. There’s also some interesting fractal structure to be noticed in the colored parts. This pattern: shows up at all scales, where there is a group of six things with the one in the middle on the bottom inverted in color. Here are the first nine rows of the triangle: Notice how that basic pattern of six dots shows up repeated here five times, with a sixth inverted-color copy on the bottom. (Can you prove this pattern continues?)

What about 4? Four isn’t prime, of course, but that doesn’t stop us. This is quite a bit more complicated! I’ll let you stare at it and look for patterns, but I’ll point out one: notice how small copies of the Sierpinski gasket show up all in red: red represents numbers that leave a remainder of two, and when two such numbers are added, we get a number that’s divisible by four.

Here are the first 125 rows of the triangle mod 5: It’s a little hard to see what’s going on there, so here are the first 25 rows only: There’s a similar fractal structure happening here as with 3—I’ll let you work it out.

Here are the first 81 rows mod 6: This is one of my favorites—it’s like there’s a yellow copy of the mod-2 Sierpinski gasket “hiding” behind a mod-3 pattern! Hmm, and $6 = 3 \times 2$… Can you explain why this happens?

Here’s 7—another prime: Eight is crazy! I really don’t understand what’s going on here. Nine gives us threes within threes: Ten, of course, features a five-pattern superimposed on a two-pattern: Finally, here’s the basic pattern for 11: And here are the first $11^2 = 121$ rows for 11: PS. I’ll be writing another post soon as a follow-up to my popular post on factorization diagrams, with some improved diagrams (incorporating many suggestions from commenters) as well as links to some related things.

PPS. Early on in the process of writing this post, I generated this: Can you guess what was wrong? Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in fractals, modular arithmetic, pascal's triangle, pattern, pictures and tagged , , . Bookmark the permalink.

### 15 Responses to Visualizing Pascal’s triangle remainders

1. Tom says:

I wrote some code that did this during the summer as I was working on some problems related to these triangles wih some undergraduates. My code was in Sage and not quite as elegant as yours. We did get some interesting related results though. One interesting question that seems to have some known partial answers is how many of each color will you see in any given row?

• Brent says:

Very interesting question! I will have to try giving it some thought.

2. Excitable Snowball says:

Regarding the PPS: The strangeness appears around the middle of row 68. At that point, you have C(68, 34), which is just over 2^64-1. You were using 64 bit integers.

• Brent says:

Yes indeed! Nice analysis. =)

3. hellman1 says:

> Can you guess what was wrong?
Maybe you used Int instead of Integer? 🙂

• Brent says:

Right you are! And it was subtle, too, because I actually gave no type signatures and it ended up being Int because I used (!!) (otherwise it would have defaulted to Integer).

4. Anil Das (@dasanil) says:

I solved a related problem recently. count of length n bit strings with popcount = 0,1 or 2 mod 3.
http://cs.stanford.edu/~das/mod3/mod3.html

Can’t yet figure out how to generalize to mod k, where k < 3.

• Anil Das (@dasanil) says:

Correction: k > 3.

5. Juan Valera (@juanvalera) says:

Great!!!!
Congratulations! They look better than I recalled them.

6. Tom says:

I put my code for Sage up on the Aleph Sage server so any of your readers can play around with these triangles if they like:

http://goo.gl/5sFuH

You should click evaluate, then you can change the modulus and the number of rows in Pascal’s Triangle. I wouldn’t recommend doing many more than 100 rows as the server gets fairly slow with the graphics.

7. Steven Taschuk says:

Nice diagrams. I wrote up a little something on the underlying combinatorial identity a few years back:

It seems likely you’re already familiar with this, but there it is, just in case.

• Brent says:

Cool, I wasn’t actually familiar with this. Thanks!

8. Jonathan says:

I enjoyed this post and got inspired to write up a little javascript code to dynamically generate such visualizations and allow for explorations (if desired) to the deeper reaches of the triangle. You can find it here: http://learningfrommistakes.org/visualizing-remainders-in-pascals-triangle/