MPMP 16 - Odd Pascal

odd-pascal.md

This is the sixteenth puzzle in Matt Parker's Matt Parker's Maths Puzzles puzzle series

Odd Pascal

Pascal's triangle is a tower of integers. The first row contains a single 1 and subsequent rows are obtained by taking the sum of the two integers above a number. Here are the first 5 rows

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Question

What is the percentage of odd numbers in the first 128 rows or Pascal's triangle?

Solution

A naiive approach might be to construct pascals triangle, count up how many entries there are in the first 128 rows, how many odd numbers there are in the first 128 rows, and use those sums to calculate the percentage numOdd / numEntries.

We could use this code to build the triangle:

def pascalsTriangle():
    """
    Generates rows of pascal's triangle.
    """
    row = [1]

    while True:
      yield tuple(row)
      row = [1] + [a + b for a, b in zip(row, row[1:])] + [1]

An we could count it up like this

def countOddEntries(numRows):
    """
    Counts the number of odd entries in the rows of pascals trianlge.
    """
    result = 0
    for row in pascalsTriangle():
        result += sum(entry % 2 for entry in row)
        if numRows == 0:
            break

We could optimise this code right away with a simple observation: We are calculating the rows of Pascal's triangle, and then taking its entries modulo 2. What if we calculated the rows of the triangle modulo 2, where addition is just binary XOR?

def binaryTriangle():
    """
    Generates rows of pascal's triangle.
    """
    row = [1]

    while True:
      yield tuple(row)
      row = [1] + [a ^ b for a, b in zip(row, row[1:])] + [1]

This is much simpler, as we dont have to calculate large sums, but we can make this even better! Numbers in python are limited in size by the available memory, not some standard value as in some other languages, where the int type is only allocated a fixed number of bits. We can use this to our advantage and instead of calculating the row as a list, we can store the entire list in a single number:

def binaryTriangle():
    """
    Generates Pascal's triangle modulo 2. Yields n, the order of the row, and
    the row itself, represented as a single number.
    """
    n = 0
    row = 1
    while True:
        yield (n, row)
        n += 1
        row = row ^ (row << 1) | 1

Displaying the first 16 rows of this binary triangle gives:

1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011
10100000101
111100001111
1000100010001
11001100110011
101010101010101
1111111111111111

Perhaps not significant, but with a bit of formatting and replacement of ones with ● and zeros with empty space gives this familiar object:

                ●
               ● ●
              ●   ●
             ● ● ● ●
            ●       ●
           ● ●     ● ●
          ●   ●   ●   ●
         ● ● ● ● ● ● ● ●
        ●               ●
       ● ●             ● ●
      ●   ●           ●   ●
     ● ● ● ●         ● ● ● ●
    ●       ●       ●       ●
   ● ●     ● ●     ● ●     ● ●
  ●   ●   ●   ●   ●   ●   ●   ●
 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

I really wanted to write up a proof that this is definitely the Sierpinsky triangle but I couldnt put anything cohesive together myself. There is a proof here though if you need one.

From here we will assume that the triangle up to the 2ⁿth row is just three copies of the triangle up to the 2^{n - 1}th row and an inverted triangle of zeros filling in the gap.

Therefore the number of odd numbers in the triangle up to the 2ⁿth row will be 3ⁿ. We know that the number of entries in the triangle up to the 2ⁿth row will be the sum of the first 2ⁿ integers. We can use this to find that the proportion of odd entries in pascals triangle up to the 2ⁿth row is:

We can implement this in python

def oddPascalPercentage(n):
    """
    Calculates the percentage of odd entries in pascal's triangle up to the nth
    row.
    """
    if n & n - 1 != 0:
        raise ValueError("Only works on powers of 2")

    k = log2(n)

    return 100 * (2 * 3 ** k) / (2 ** k * (2 ** k + 1))

Plugging in 128 (= 2⁷) gives ≈ 0.26489 or 26.4%.

What about other values of n?

Currently we can only calculate the percentage of odd entries for the triangle up to row numbers that are powers of 2. It isnt too hard to generalise to the rest though. We can calculate the number of odds in the triangle up to row k, the largest power of two less than n, divide n by k, and the recurse down, making sure that we multiply the recursive value by two, as there will be two copies of the smaller triangle remaining.

def oddPascal(n):
    """
    Calculates the number of odd entries in pascal's triangle up to the nth row.
    """
    if n == 0:
        return 0

    # The value k is the largest, such that 2^k <= n
    k = int(log2(n))
    # unset the most significant bit of n and recurse.
    return (3 ** k) + 2 * oddPascal(n ^ (1 << k))

We can then divide this by the sum of the first n integers () to calculate a percentage for any given n in O(B(n)) where B is the number of bits in the binary representation of n (strictly better than O(log n)).