Investigating the Efficient Computation of Lottery Wheels

I can’t remember exactly how I got there (I suspect that Wikipedia was involved), but some weeks ago I ended up reading the UK National Lottery Wheeling Challenge website. The “challenge” involved is to generate a lottery wheel as small as possible for winning at least £10 in the United Kingdom’s national lottery. What exactly is a wheel, and why should it be small? To quote my own introduction:

A lottery wheel is a set of tickets for a lottery drawing which, if purchased in its entirety, guarantees a certain type of win, according to the rules of the lottery, no matter which ticket is actually drawn. […] The goal is straightforward. Each ticket we purchase costs money, so we want to generate a lottery wheel that is as small as possible while still guaranteeing a win of some minimum desired prize.

Now, obviously, such a thing no matter how good is not going to let you turn playing the lottery into a reliable money-maker, but in fact the reason that this is interesting has nothing to do with actually playing the lottery. I’ve only bought one lottery ticket in my entire life, and needless to say I lost.

The reason that this was initially interesting to me was that the site showcased a wheel of 163 tickets, which seems quite good for a 6-from-49 lottery, but went on to solicit for better wheels (indicating that the 163-ticket wheel was not known to be optimal) and to note that no wheel generation algorithm was known. The more I thought about how to create a generation algorithm, the more intriguing the problem became. The problem turns out to be a very special, highly symmetric form of minimum set covering. From what I was able to find, this problem has been studied academically, but with minimal results, and rarely on realistically-sized problems.

So, inspired by this, I set out to do two things: write a program that runs in a reasonable amount of time on a modern personal computer that can generate good lottery wheels for realistically-sized lotteries, and if possible prove whether this problem is NP-Hard or not.

I am documenting this project in a series of articles on the lottery problem. To start with, I have posted the first three articles which describe the problem, its relationship to set covering, and the challenges involved in implementing a generator algorithm for realistically-sized lotteries. Further articles will be posted later documenting my progress on the problem.

Reconstruction Complete

Nerdland has been “down for reconstruction” for almost a year now, since July 11, 2008, and had been almost completely stagnant for at least two years before that. Today, it has re-opened with a new purpose. To quote the About page:

Nerdland is my personal website. It has been many things since it was first brought online in 1999. Historically, it has been an my experimentation ground for web development. These days, it is a place where I put records of my thoughts and activities, mostly related to my dual career-hobby of computer programming, and my interests in theoretical computer science. Nerdland is not strictly a weblog. Shorter comments and time-relevant materials are posted in weblog format, but Nerdland also serves as a collection of standalone articles, which are permanently accessible through the links on the left.

The primary difference between this and previous incarnations of Nerdland is that I will be creating significant new content myself, rather than simply providing a framework for contributions and hoping for others to do so. Also, the content will generally have an overarching theme, albeit a theme that is wholly defined as “my personal interests”.

The new Nerdland is powered by the WordPress content management system. The design of the site is based on the design and the color scheme of the previous incarnation of Nerdland, but with a cleaner, more minimalist feel. I will probably be tweaking the design frequently over the next few weeks, but the site should remain functional throughout.

All pages and posts on Nerdland, with the exception of the About page and pages that are only indexes to other pages, allow comments. I encourage contributions and remarks from any and all readers. Comments will be moderated for spam and blatant offensiveness, but not much else.

Friends of mine who had “user” pages on the old Nerdland continue to have them under the same URLs as before, although from now on accesses to the user pages will be re-directed to the users.nerdland.net subdomain.