I have the following code:

α = 10^6;
L = Total@*Map[Length];
\[DoubleStruckCapitalT][i_, j_] := Binomial[i, j - 1];
     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]?

  • 1
    $\begingroup$ The table size grows as O(alpha^2). So don't compute a Table, use a loop and counter or similar instead. $\endgroup$ Commented Oct 17, 2020 at 16:30
  • $\begingroup$ @DanielLichtblau can you help me how to program that? $\endgroup$ Commented Oct 17, 2020 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Oct 17, 2020 at 16:34
  • $\begingroup$ @DanielLichtblau How do I setup the counter? $\endgroup$ Commented Oct 17, 2020 at 16:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Commented Oct 18, 2020 at 11:16

2 Answers 2


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]},
    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


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.

  • 1
    $\begingroup$ This is brilliant! $\endgroup$ Commented Oct 18, 2020 at 12:29
  • 1
    $\begingroup$ Thank you! That is kind of you. =D $\endgroup$ Commented Oct 18, 2020 at 12:49

The basic approach


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

count = 0;

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


(* 448363 *)
  • $\begingroup$ 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 $\endgroup$ Commented Oct 18, 2020 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.