# Finding the number of even numbers in Pascal's triangle (code gives memory error)

I have the following code:

α = 10^6;
L = Total@*Map[Length];
\[DoubleStruckCapitalT][i_, j_] := Binomial[i, j - 1];
L[ParallelTable[
If[TrueQ[
EvenQ[\[DoubleStruckCapitalT][n, k]] && \[DoubleStruckCapitalT][
n, k] != 0], {n, k}, Nothing], {n, 0, α - 1}, {k,
1, α}] //. {} -> Nothing]


But this code gives an error memory message, how can I edit my code such that I want to compute this code for large values of \[Alpha]?

• The table size grows as O(alpha^2). So don't compute a Table, use a loop and counter or similar instead. Oct 17 '20 at 16:30
• @DanielLichtblau can you help me how to program that?
– Jan
Oct 17 '20 at 16:31
• Set some counter to zero. Change ParallelTable to Do. Every time you get an EvenQ, increment the counter. Experiment with (much) smaller values of alpha. Oct 17 '20 at 16:34
• @DanielLichtblau How do I setup the counter?
– Jan
Oct 17 '20 at 16:36
• The code-review tag is for improving working code, not to fix non-working code, or to add new features to an existing program. Please only use it when appropriate. Oct 18 '20 at 11:16

Apparently, you want to count the number of zeroes in Pascal's triangle mod 2 with $$\alpha \in \mathbb{N}$$ rows. This can be done by counting the ones and subtract this number from the number of all entries of that triangle, which is $$\alpha(\alpha+1)/2$$.

The code that you posted has complexity $$O(\alpha^2)$$ and with your choice of $$\alpha$$, that will take forever. The key to a more efficient way of counting is to observe that Pascal's triangle mod 2 has a self-similar structure. The first $$2^j$$, $$j\geq 1$$ rows form a triangle $$T_j$$. The triangle $$T_{j+1}$$ can be obtained by gluing three copies of $$T_j$$ together (in the fashion of the Triforce from Zelda). So $$T_{j+1}$$ has 3 times as many ones than $$T_j$$. $$T_0$$ consists of a single one. By induction, the first $$2^j$$ rows contain $$3^j$$ ones. So, in fact, the number of ones can be computed from the binary represenation of the number $$\alpha$$. After some trial and error, I came up with this formula for the number of ones:

onecount[α_] := With[{digits = IntegerDigits[α, 2]},
Total[
Times[
digits,
3^Range[Length[digits] - 1, 0, -1],
2^(Accumulate[digits] - 1)
]
]
]


I hope it is correct. A quick test:

triangle[α_] := Table[Mod[Binomial[n, k], 2], {n, 0, α - 1}, {k, 0, n}]
a = Table[Total[triangle[α], 2], {α, 1, 100}];
b = onecount /@ Range[100];
a == b


True

Also, in case $$α = 10^3$$, this reproduces Bob's result, which is $$448363$$.

So the number of zeroes in the triangle with number $$\alpha = 10^6$$ should be

α = 10^6;
Quotient[α (α + 1), 2] - onecount[α]


Note that this takes only $$O(\log_2(\alpha))$$ time and memory.

• This is brilliant!
– Jan
Oct 18 '20 at 12:29
• Thank you! That is kind of you. =D Oct 18 '20 at 12:49

The basic approach

Clear["Global*"]

α = 10^3; (* Reduced value *)
\[DoubleStruckCapitalT][i_, j_] := Binomial[i, j - 1];

count = 0;

Do[
If[
\[DoubleStruckCapitalT][n, k] != 0 &&
Mod[\[DoubleStruckCapitalT][n, k], 2] == 0,
count += 1],
{n, 0, α - 1}, {k, 1, α}];

count

(* 448363 *)
`
• First of all, thank you for your answer. Is there a way to make it even faster? Because bigger values of Alpha take so so long
– Jan
Oct 18 '20 at 7:03