I am looking for an efficient algorithm to find collisions in the pascal triangle with repeats $\ge 4$.
Definition of a collision: let (n, k, m, l) with 2<=k<= (1/2)*n and 2<=l<=(1/2)*m. A binomial collision is when k<l and Cr(n, k) = Cr(m, l).
Example of collision is Cr(78, 2) = Cr(15, 5) = Cr(14, 6) = 3003. Other numbers are 120, 210, 1540, 7140 ... They are numbers that is repeated for 4 times or more in a Pascal triangle.
In the paper "Binomial collisions and near collisions" by Benne de Weger et al., they have an algorithm using Priority Queue which I do not quite understand. Link here: https://www.researchgate.net/publication/318652587_Binomial_collisions_and_near_collisions
It says,
Have a table and a priority queue, both of size $N$. Both contain the same elements. Initially both contain the numbers $Cr(n+2, 2)$ for $n < N$. The priority queue is kept sorted. At each step the top two elements are compared for equality. Afterwards the top element is discarded. When $Cr(n+k, k)$ is discarded, the new value $Cr(n+k+1, k+1)$ is added, unless $k\ge n$. The new value needed is computed from the old one via $Cr(n+k+1, k+1) = Cr(n+k, k) + Cr(n+k, k+1)$. Note that the value $Cr(n+k, k+1)$ is present in the table at index $n-1$ at the moment it is needed.
I do not understand this part, “At each step the top two elements are compared for equality. Afterwards the top element is discarded.” So we compare the top 2 elements of the priority queue for equality, if equal, discard both and add the number into collision list, if not equal, then discard the top element only?
“When $Cr(n+k, k)$ is discarded, the new value $Cr(n+k+1, k+1)$ is added, unless $k\ge n$.” OK
“The new value needed is computed from the old one via $Cr(n+k+1, k+1) = Cr(n+k, k) + Cr(n+k, k+1)$. Note that the value $Cr(n+k, k+1)$ is present in the table at index n-1 at the moment it is needed.” I don’t get this part, because “Initially the table contains the numbers $Cr(n+2, 2)$ for $n < N$”. As far as I can see, the content of the table has not changed throughout, so the table does not contain any other number than $Cr(n+k, k+1)$ where $k = 2$?
Can someone enlighten me please or perhaps provide with source code in C or Python?
Thank you very much!