# 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. Commented Oct 17, 2020 at 16:30
• @DanielLichtblau can you help me how to program that? Commented Oct 17, 2020 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. Commented Oct 17, 2020 at 16:34
• @DanielLichtblau How do I setup the counter? Commented Oct 17, 2020 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. Commented Oct 18, 2020 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! Commented Oct 18, 2020 at 12:29
• Thank you! That is kind of you. =D Commented Oct 18, 2020 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 Commented Oct 18, 2020 at 7:03