4
$\begingroup$

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]?

$\endgroup$
10
  • 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$ Oct 17 '20 at 16:30
  • $\begingroup$ @DanielLichtblau can you help me how to program that? $\endgroup$
    – Jan
    Oct 17 '20 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$ Oct 17 '20 at 16:34
  • $\begingroup$ @DanielLichtblau How do I setup the counter? $\endgroup$
    – Jan
    Oct 17 '20 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
    Oct 18 '20 at 11:16
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ This is brilliant! $\endgroup$
    – Jan
    Oct 18 '20 at 12:29
  • 1
    $\begingroup$ Thank you! That is kind of you. =D $\endgroup$ Oct 18 '20 at 12:49
4
$\begingroup$

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 *)
$\endgroup$
1
  • $\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$
    – Jan
    Oct 18 '20 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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