The distribution of balls in a Bean Machine that omits all the "prime pegs"?

Question

The Bean Machine, also known as a quincunx or the Galton box, is a well known triangular board that contains several rows ($n$) of staggered, but equally spaced pegs. Balls are dropped from the top one by one to avoid interference. They bounce off the pegs and stack up at the bottom of the triangle in bins. The resulting stacks of balls approach the characteristic Bell curve shape for large $n$.

Consider the following altered Bean Machine that now has all the 'prime numbered pegs' (counting top to bottom, left to right) removed:

(source)

Based on what is known about the primes, is there anything that could be predicted about the resulting distribution of balls for large $n$? Is it expected to be skewed to the left or the right? Or does it nicely balance out like the normal distribution?

Thanks.

Answer 1

There will be certain columns with a (much) higher than average number of missing pegs and that will cause irregularities. It turns out that quadratic residues are relevant.

Say that we locate pegs $1,2,3,4,5,6$ at $(0,0),(-1,-1),(1,-1),(-2,-2),(0,-2),(2,-2)$ etc. The location of the peg number $n$ will be

• $(x,y)=(2n-z^2-1,1-z)$

where $z=\lfloor\frac{(1+\sqrt{8n-7}}{2}\rfloor.$ This means that at location $(x,y)$ (with $x,y$ of equal parity, $y \le 0$ and $|x| \le |y|$) is

• $n=\frac{1+x+(y-1)^2}{2}.$

Imagine a ball poised just above the location of (a potential) peg $(x,y)$ If the number $n=\frac{1+x+(y-1)^2}{2}$ is prime then drop down two rows to (just above) peg $(x,y-2).$ If $n$ is not prime then the ball can go either left to $(x-1,y-1)$ or right to $(x+1,y-1).$

Here is a diagram showing what this setup does. A $+$ is a peg corresponding to a non-prime while a $|$ corresponds to a missing peg from a prime. Row $i$ adds to $2^i$ as in Pascal's triangle and shows the theoretical distribution for $2^i$ balls dropped from the top. However row $i$ has about twice as many possible locations for an entry. A more detailed description of the SETUP is below.

Observe that each column contains only even pegs or only odd pegs, which is already biased. The red oval encloses part of column $x=-3$ starting with rows rows $y=-3$ and $y=-5$ and non-pegs corresponding to the primes $7,17.$ The potential pegs below these will be for $31,49,71,97,127$ which are all prime except for $49.$ The red oval shows the drop past $71,97,107.$ the six doubling are from dropping past these three non-pegs and, after each one, slipping through the next row. Following these there is a mix of prime and composite. Starting with row $y=-81$ the next few pegs (for $x=-3$) are $3361,3527,3697,3871,4049,4231$ which are all prime except $3871=7^2\cdot 79.$ Below are plots I got for the first 100 stages, it reads left to right and top to bottom. The biggest spike which grows and shrinks corresponds to $x=-3.$ I'll discuss how I interpreted the setup but first let me explain the sparse columns phenomenon (which is relevant however the ambiguous details are interpreted.)

It turns out that the pegs with $x=-3$ (which we already know are odd) can have number a multiple of $q=7, 17, 23, 31, 41, 47$ but can not divide by any of $q= 3, 5, 11, 13, 19, 29, 37, 43.$ These lists are the primes $q$ which do and do not have $2$ as a quadratic residue. This explains why a large number of pegs in that column have a prime value. From $n=\frac{1+x+(y-1)^2}{2}$ we see that some pegs in column $x=c$ will be multiples of $q$ precisely when $-c-1 \mod q$ is a square. The smallest odd primes for which $-58$ is a quadratic residue are $29, 31, 37, 47, 59.$ This means that column $x=57$ (which is an odd column) will have no multiples of any smaller primes. Of the $46$ primes less than $199$, only $16$ are potential divisors. This explains why , of the first $100$ pegs in that column, $63$ get removed for being prime. These removed pegs include a run of $8$ consecutive removed pegs and two runs of $7.$ To be fair, a column which does contain multiples of $q$ has them at twice the usual frequency, so perhaps things do balance out on a larger scale.

So here is how I interpreted the SETUP, and I did not check too hard for a programming error. In the standard setup one has $r+1$ bins if the last row has $r$ pegs. I said that when a ball gets to a missing peg it drops straight down until it hits a peg in that column and goes right or left. However, if we want to know what the balls will look like if the bins are placed below row $r$ then I decree that a ball dropping straight down will hit a bin divider and go left or right. I did not actually run a simulation, I constructed a modified Pascal Triangle where a value in a certain position doubles and distributes equally to the two neighbors below. The modification is that a number "falling past" a missing peg doubles in size and sits in a space normally empty in the usual inverted triangle. It then lands on top of a potential peg two rows down from the missing peg (having doubled again) and possible combines with values arriving from the right and/or left and redoubles several more times if it happens to encounter several consecutive missing pegs. So the total value at each layer is a power of $2$ as with the standard setup. However some of those are quantities falling past and slipping between two "standard" entries. When we put the bins at a certain level, the intermediate irregular quantities get split equal with the two bins on either side.

The description above of the path of a ball allows us to ivnvestigate the empty bins question without generating the whole triangle. Imagine a ball which always goes right when it can. Since the triangular number $3$ at $(-1,-1)$ is prime, the ball drops down creating an eternal empty bin on the far right. There are no more prime triangular numbers but that is irrelevant because no ball will ever get to those pegs. What is relevant is that $\frac{m(m-1)}{2}-1= \frac{(m+2)(m-1)}{2}$ is never prime for $m \gt 3.$ So coming from the right is one empty bin and then one bin which will always get 4 balls (similar to the value $1$ down the edges of the usual Pascal triangle).

On the left the number of empty bins can grow. Just following the path of a ball which falls left when it can, I come up with $1043$ empty bins on the left of row $20842.$ The number of primes less than $20842$ is $2344$ so this does not clash too badly with my rash back of the envelope calculation that the number of empty bins on the right side of row $k$ grows a bit less than half as fast as the number of primes less than $k.$ This is based on little more than that a peg at level $k$ has size about $\frac{k^2}{2}$ so has "probability" $\frac{1}{2\ln(k)+ln(2)}$ to be prime and I don't know what to do with the $\ln{2}$ so I'll ignore it. However the growth is choppy. There is a jump of $5$ in the number of empty bins starting at row $4788$ and again at $5844$. These correspond to the "lefty" ball encountering a column with many prime divisors forbidden and dropping past 5 empty spaces in a row.

So here are the graphs.

Answer 2

Is it clear that the problem remains well defined?

If the idea is that each ball has a 50% chance of bouncing in each direction when encountering a peg, then what happens to the ball when it would normally fall through the peg? In the picture above it appears that it would not be possible to access the outermost paths, because the paths that stay on the outside would be incomplete early on.

My instinct here is that eventually, for every path leading anywhere but the center, there will be a prime numbered peg missing that prevents the ball from falling along that path, so for large $n$ the distribution would tend toward the discrete distribution with everything hitting the center.