Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BinomialOddQ

Source Notebook

Determine the parity of a binomial coefficient

Contributed by: Shenghui Yang

ResourceFunction["BinomialOddQ"][n,k]

gives True if the binomial coefficient Binomial[n,k] is odd integer, and False otherwise.

Details

ResourceFunction["BinomialOddQ"][n,k] is effectively equivalent to OddQ[Binomial[n,k]] for nonnegative integer inputs with n>=k.
ResourceFunction["BinomialOddQ"][n,k] determines the parity of the corresponding binomial coefficient using bitwise operation. Thus the complexity is O(log(N)) or grows linearly with respect to the number of binary digits of the input values.
Extended domain of binomial coefficient is not supported.

Examples

Basic Examples (2) 

Determine the parity of Binomial[50,3]:

In[1]:=
ResourceFunction["BinomialOddQ"][50, 3]
Out[1]=

Effectively the same as:

In[2]:=
OddQ[Binomial[50, 3]]
Out[2]=

Scope (2) 

Binomial coefficient grows rapidly:

In[3]:=
TimeConstrained[OddQ@Binomial[10^30, 10^5], 5]
Out[3]=

BinomialOddQ instantaneously determines the parity without computing the large binomial value:

In[4]:=
ResourceFunction["BinomialOddQ"][10^30, 10^5] // AbsoluteTiming
Out[4]=

Possible Issues (1) 

Extended domain for Binomial is not supported. The function returns unevaluated:

In[5]:=
{OddQ[Binomial[-5, 2]], ResourceFunction["BinomialOddQ"][-5, 2]}
Out[5]=

Neat Examples (2) 

Plot Sierpinski triangle:

In[6]:=
ArrayPlot[ Table[Boole@ResourceFunction["BinomialOddQ"][i, j], {i, 0, 2^6 - 1}, {j, 0, i}], ColorRules -> {1 -> RGBColor["#0A174E"], 0 -> RGBColor["#F5D042"]}]
Out[6]=

The run of zeros in sequence formed by Binomial[2k+1,k] for k from 1 to 1+2(2n-1) is exactly {1,3,7,…,2n-1}:

In[7]:=
data = Boole[ Table[ResourceFunction["BinomialOddQ"][2*k + 1, k], {k, 64 - 1}]];
In[8]:=
SequenceReplace[data, {p : Repeated[0]} :> Labeled[Highlighted[Row[Riffle[{p}, ","]]], Length[{p}], Top ]]
Out[8]=

Find the positions of the zero sequences using brute force:

In[9]:=
SequenceCases[ Boole[Table[ ResourceFunction["BinomialOddQ"][2*k + 1, k], {k, 2 (-1 + 2^8)}]], {p : Repeated[0]} :> Length[{p}]]
Out[9]=

These are one less than the powers of two:

In[10]:=
2^{1, 2, 3, 4, 5, 6, 7, 8} - 1
Out[10]=

Publisher

Shenghui Yang

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 30 January 2025

Source Metadata

  • Citation:

Related Resources

License Information