Possible undergraduate research projects with Stephen Lucas:

• Bounded continued fractions for rationals. [computational number theory]
A continued fraction is a particularly elegant representation of rationals related to the Euclidean algorithm, of the form  , where each bi  is a positive integer. In the case of reals, the fraction continues indefinitely. A bounded continued fraction is one in which each of the bi's has some maximum value. It has been proven that any real can be represented as the sum of two bounded continued fractions, with maximum value four. Unfortunately, the method is not applicable to rationals, and we don’t know whether every rational can be represented as the sum of two finite bounded continued fractions. The aim of this project is to numerical investigate how hard it is to represent an arbitrary rational by bounded continued fractions.
• Improved bounds for the kissing problem. [numerical analysis]
The kissing problem asks how many spheres can touch a central sphere without overlapping in n-dimensions. The solution is known for dimensions two to four, and there are bounds on the solution in higher dimensions. The aim of this project is to try and improve upon these bounds using a numerical optimization algorithm I have developed to distribute spheres.
• An integer-valued logistic equation. [numerical analysis/chaos theory]
The logistic equation  is a classic example used to explain bifurcation and the onset of chaos. However, it is assumed that x is a real variable. The logistic equation was originally derived as an iteration on populations, and hence integer values. The aim of this project is to investigate the effect of assuming integer solutions only for the equivalent population model. Do we still see period doubling to chaos in the same way?
• Analysis of the game “Dreidel”. [probability theory]
Dreidel is a simple game played during Hannukah, which previous publications have proven to be unfair. Unfortunately, these results were flawed because they assumed winnings could be arbitrary reals. Using a Markov chain approach, we can work out probabilities exactly. So what are your chances of actually winning Dreidel?
• Circle pack algorithms. [numerical analysis]
A circle pack is a collection of circles with a given set of tangencies. The (unique) radius of each circle can be found given the radius of boundary circles, and leads to a variety of efficient algorithms. But what if the radii given are not for all the boundary circles? We will develop some new algorithms for the circle pack problem, and use them to try and find conditions on the initial radii that guarantee a circle pack is unique.
• Comparing convex hull algorithms. [computational geometry]
A convex hull is the smallest convex polygon that completely encloses a set of points. Previously, I have had an undergraduate research student do a project comparing the efficiency of various algorithms to find the convex hull of points in the plane. The aim of this project would be to extend the previous work by looking at more algorithms, and seeing how they compare.
• Sudoku uniqueness. [computational]
We all know about solving Sudoku's by now, but how hard is it to find an initial set-up with a unique solution? The aim of this project is to build an effficient Sudolu solver, then use it to investigate the distribution of how many solutions there are for initial set-ups with various conditions.
• Nontransitive dice. [game theory]
A transitive relationship says that if A betas B and B beats C, then A must beat C. In a non-transitive situation, C beats A. Several examples of non-transitive dice are known, where the aim is to get the larger score when rolling: the first set beats the second, which beats the third which beats the first. The aim of this project will be to examine whether other nontransitive dice sets are possible, and what conditions are required for nontransitive sets.
• Minimal Goldbach Sets. [computational]
The Goldbach conjecture is one of the more famous unsolved problems in number theory: can every even integer be represented as the sum of two primes. What is less known is that it appears that all but 33 even integers can be represented as the sum of two twin primes, primes that differ by two. The aim of this project will be to investigate the number of representations of even integers using twin primes, and see if there are smaller sets that appear to have the same properties.