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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is brilliant! $\endgroup$ – Jan Oct 18 at 12:29
  • 1
    $\begingroup$ Thank you! That is kind of you. =D $\endgroup$ – Henrik Schumacher Oct 18 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 *)
| improve this answer | |
$\endgroup$
  • $\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 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.