Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:

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.

share|improve this question
4  
My gut reaction is that for large $n$, there are hardly any primes, so you wouldn't even notice they were missing. –  Gerry Myerson Feb 14 '13 at 22:28
    
how was this image generated? –  diego898 Feb 24 at 21:03
    
@diego898. Generated in Powerpoint. For illustration purposes only and not in line with a real board! –  Agno Feb 27 at 19:41
add comment

2 Answers

up vote 8 down vote accepted

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).$

Observe that each column contains only even pegs or only odd pegs, which is already biased. The illustration shows missing pegs in column $x=-3$ (rows $y=-3$ and $y=-5$) corresponding to the primes $7,17.$ The pegs below these will be for $31,49,71,97,127$ which are all prime except for $49.$ Following this 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, if a column which does contain multiples of $q$ then it has 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 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.

alt text

share|improve this answer
    
@Aaron. Many thanks, this is really great. Nice approach with the Pascal Triangle. Is there anything to say about the ratio between the total number of permanently empty bins and the total number of bins $r+1$ (as function of $-y$). Will that ratio converge? –  Agno Feb 16 '13 at 11:10
    
I included a speculation that it grows half as fast as the primes. –  Aaron Meyerowitz Feb 17 '13 at 2:50
add comment

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.

share|improve this answer
1  
Except for the two extreme bins, there are more than one path leading to that bin. Clearly there are some other bins that will never get any balls (for example, the one second from left, as can be seen from the picture already). My gut feeling is that, for any fixed k, a bin that is at distance k from the edge will not get any balls for large n. It seems to me that there could still be some kind of limiting distribution in the middle, although I agree it's not obvious from the problem definition. –  verret Feb 15 '13 at 1:32
    
I agree, for any fixed $k$ there is (almost certainly) an $n$ such that the bins within $k$ of the edge will get no balls. I have no intuition for how $k$ would grow in $n$ and I guess I imagine that it would remain some kind of normal distribution between the limits. –  magfrump Feb 15 '13 at 21:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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