# A Polyomino Tiling Algorithm

2018-08-18

UPDATE: Thanks to David MacIver for pointing out that the problem being reduced to here is the Exact Cover problem, and the reduction was described by Donald Knuth in his Dancing Links paper.

Over eight years ago I created the Polyomino Tiler (a browser application that attempts to tile arbitrary grids with sets of polyominoes), but I haven't ever written about the algorithm it uses.

If any aspects of what follows are confusing, it may help to play with the polyomino tiler a bit to get a better idea for what it's doing.

There are a couple aspects of the problem that combine to make it challenging:

• the set of available polyominos is fully customizable up to the heptominoes; each polyomino can be restricted to specific flips/rotations
• the grid can be any subset of a rectangular grid (or a cylinder/torus)

So the algorithm needs to be generic enough to not get bogged down in all the edge cases resulting from these two facts.

The two key components of the algorithm are:

• abstract away the geometric details by constructing a graph that describes all the possibilities
• apply certain heuristics to a generic backtracking search algorithm on that graph

## Placements

The main preprocessing step is to calculate all possible placements of all available pieces. When hundreds of piece variants are available this step can be lengthy, and the result can require a lot of memory. But the result is essentially a bipartite graph (or, in database terms, a many-to-many relationship) between placements and grid points.

For example, given this 2x3 grid:

and restricting ourselves to the L-shaped trominoes to keep the visuals tractable, the placement graph looks like this:

Notice that all of the geometric details have been abstracted away; this means that the rest of the algorithm could just as easily be applied to grids of triangles, or hexagons, or hyperbolic grids, or higher dimensions.

## Search

Given the bipartite graph, the problem of tiling the grid can be reformulated as the problem of finding a subset of the placements that, as a whole, is connected to every one of the grid points exactly one time.

The search algorithm is a backtracking algorithm that at each step chooses an untiled grid point and a random placement associated with that grid point; it adds that placement to the solution set and then tries to tile the remainder of the grid (taking note of which placements are invalidated by the one selected). If it fails to tile the rest of the grid, then it tries the next placement. If it runs out of placements, then the grid must be untileable.

For example, if we decide to start tiling the above grid from grid point A, the search tree might look like this:

Depending on the order that we search the children, we could either end up with the ABC-DEF tiling or the ABD-CEF tiling; if we visit the ACD branch first, we'll have to backtrack since there's no solution in that direction.

The reason the tree is so sparse is that each time we descend we remove placements from the graph that conflict with the one chosen. E.g., when we descend to ABC, the graph is updated to look like this:

This basic search algorithm is specialized with several heuristics/optimizations.

### Untileability from Zero Placements

Since every placement we select makes several other placements impossible, it's easy to get to a point where there is some grid point that no longer has any possible placements. This is the most common sign of untileability, and it means we need to backtrack and try something different.

For example, if we descended down the ACD branch of the search tree, the graph would look like this, and the existence of grid points with no placements indicates that there's no solution.

### Untileability with Number Theory

A given set of polyominoes places restrictions on what grids can be tiled purely based on their size. This is solely a function of the set of distinct sizes of the polyominoes.

For example, with the tetrominoes, only grids whose size is a multiple of four can be tiled. If the polyominoes have sizes 4 and 6, then only grids whose size is an even number greater than two can be tiled. This kind of analysis is closely related to the coin problem.

Further, if a grid consists of disconnected subcomponents, then we can analyze the tileability of each one separately, and conclude that the whole grid can't be tileable if any of the subcomponents is not tileable.

For example, this grid has been disconnected, and even though the size of both pieces together is a multiple of three and so could theoretically be tiled by trominoes, the individual subcomponents do not have a multiple of three grid points, and so neither of them are tileable.

### Smallest Subcomponents First

If the grid at any point becomes disconnected, we immediately restrict the algorithm to the smallest subcomponent and try to tile that completely before moving on to the next one. The logic here is that if the disconnected grid as a whole can't be tiled, there's a decent chance that the smallest subcomponent can't be tiled. The smallest subcomponent is also likely the one that we can finish searching the fastest, and so this hopefully leads to a more aggressive pruning of the search space.

For example, this grid has a small component and a large component, and the small component can't be tiled with trominoes (can you figure out why?); tiling the smaller one first means we find out about this problem quickly, rather than waiting until the whole large subcomponent has been tiled.

### Tile the most restricted grid points first

Within a subcomponent, we select the next grid point to tile based on the number of remaining placements it has. It is not uncommon for there to be a grid tile with only a single option, and in those cases it's important to place that piece immediately, since it likely decreases the size of the search space by eliminating other placements (and potentially causing more grid points to have only one option).

When there's not a grid point with a single placement, we still prioritize grid points with the fewest number of placements, since these are intuitively the most "difficult" parts of the grid to tile, which makes them more likely to be rendered untileable by other placements.

For example, in this grid the untiled grid point in the bottom left corner has only one possible placement with trominoes; tiling it lets us eliminate seven other placements that conflict with the forced placement.

### Split the grid whenever possible

The last heuristic is a little crude but still useful. The motivation is that being able to split the grid into subcomponents is useful (since they can be analyzed independently), and so if we have the opportunity to split it by placing a piece, we should do so. So the precise rule is that, when there aren't any single-placement grid points (which are higher priority), and there is a single grid point that splits the grid (in graph theory terms, a vertex whose removal disconnects the graph), then we search placements for that grid point next.

For example, there are a couple grid points that disconnect the bottom right portion of this grid from the rest of it; either of these could be chosen for the next search step.

This approach could probably be generalized to something that tends to select grid points that make the grid easier to split, rather than only acting on this principle when it can be achieved in a single step. However, this would likely be somewhat in tension with the prioritization of the most restricted grid points, so I'm not sure how it would work out.

## Getting Stuck

Since the polyomino tiling problem is NP-complete, it's not surprising that there's a variety of scenarios where the algorithm gets stuck. Some of these are artifacts of the particular algorithm, and it could conceivably be tweaked to handle those special cases. But I think the algorithm as it is is a decent balance of broad efficacy and simplicity.

The randomness in the algorithm (the ordering of placements for a particular grid point, and to a limited extent the prioritization of grid points) means that sometimes more progress can be made simply by restarting the search.

## Possibilities

There are a variety of directions the algorithm could be tweaked; I mentioned one earlier about working more aggressively to split the grid.

Another idea is to optimize the order that placements for a particular grid point are tried. Perhaps placements could be prioritized based on the number of options available for the other grid points involved.

## Summary

So to tile an arbitrary grid with an arbitrary set of polyominoes, we:

• calculate all possible placements to obtain a bipartite graph between grid points and placements
• use a backtracking algorithm to search for a subset of placements that exactly tiles the grid
• optimize the algorithm by using various heuristics to prioritize its choices

In hindsight, I believe the initial step of transforming to a graph could be retargeted to transforming to an instance of the SAT problem, in which case a generic SAT solver could be used for the rest of the algorithm. It would be interesting to learn which of the heuristics in my algorithm have analogs in general SAT solvers, and which are particular to tiling problems.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# Visualizing Hash Functions

2013-06-03

I've been working on some static visualizations of hash functions, starting with SHA1 and MD5 (images here and here, respectively). The two sample images show the process of computing the respective hash functions on the input "denny" (with ASCII encoding -- i.e., the input in hex is "64656E6E79"). A portion of the MD5 image is included below:

Notes about these two particular algorithms and their visualizations:

• Both algorithms are mostly defined in terms of operations on 32-bit "words", which essentially means 32-bit integers. They define the input/output conversion from sequences of bits/bytes to words, but this step is not covered in the diagrams.
• Probably the most confusing thing if you examine them in detail is that SHA1 uses a big-endian conversion from 4 bytes to 1 word while MD5 uses little-endian. See Appendix A for more. (tl;dr: the words in MD5 have their bytes printed in the opposite order you would expect.)
• MD5 and SHA1 have a lot of similarities, and in particular they both include a function of 3 words that varies slightly throughout the computation; so I've highlighted this function with a yellow box.
• The way that MD5 evolves its state is very similar to SHA1, but it is described differently in the spec. I decided to deviate from the spec and structure the diagram the same way as SHA1, which both highlights the similarity and is also (I think) a bit simpler to follow.

If you're curious about any other details of MD5 or SHA1, the specs are fairly readable, hopefully even more so with the diagrams to follow along with.

I'm hoping this sort of diagram can

• give an appreciation for
• how complex hash functions are, both absolutely and relative to each other
• the difficulty of trying to invert a cryptographic hash function
• be a useful aid to anyone trying to understand the details of a particular algorithm
• be fun to look at. I love things that give a sense for how crazy-complicated computers look from certain angles.

Several things I think are worth exploring:

• How well can this approach be adapted to hairier algorithms?
• Whirlpool uses a 64-byte state rather than a 5-word state (like SHA1)
• A more esoteric algorithm could operate on individual bits
• I'd like to branch out into other sorts of computations
• Other cryptographic primitives
• Numerical algorithms (e.g., big-integer arithmetic implementations)

General feedback and suggestions welcome.

## Appendix A

Big-endian looks more natural to me, so I display the hex value for words with the higher-order bytes first -- e.g., the word corresponding to the integer 100 is shown as "00000064". This means that internally both algorithms look the same (in particular the bit-rotations and addition-mod-32 operate the same way), but for MD5 the input and output words will have their bytes ordered the opposite of what you would expect. For the input "denny" where the first word comes from the substring "denn", the first word in SHA1 is "64656E6E" while the first word in MD5 is "6E6E6564". You'll also notice this if you try to compare the MD5 output shown with the value given by any normal MD5 utility.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# Uninteresting Numbers

2013-04-04

There's a quasi-paradox about interesting numbers which says that all the natural numbers must be interesting. If they weren't, then there would be a smallest uninteresting number, which is a very interesting thing to be. So that's immediately a contradiction and we're forced to conclude that all the natural numbers are interesting. This is just a bit of fun with self-referential definitions, but it suggests an interesting exercise with trying to formally define "interesting".

We can start with some reasonable attributes that qualify a number as interesting, and use them to find the first handful of uninteresting numbers. For example, we might start by saying that 0 and 1 are interesting for being the additive and multiplicative identities (respectively), and that all primes are interesting. By this definition the first ten uninteresting numbers are:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...

Then we can look at the first few and try to find something interesting about them that we can add to our list of attributes. For example 4 is a square, or more generally it is nk where k > 1. Removing those sorts of numbers gives us:

6, 10, 12, 14, 15, 18, 20, 21, 22, 24, ...

6 is 2×3, which makes it a semiprime. We may as well say semiprimes are interesting, which also takes out 10 and 14 and 15 and 21 and 22, leaving us with:

12, 18, 20, 24, 28, 30, 40, 42, 44, 45, ...

12 is 3×4, which makes it the product of at least two consecutive numbers, so that's mildly interesting as well. This also captures 20 and 24 and 30 and 42, so now we have:

18, 28, 40, 44, 45, 48, 50, 52, 54, 63, ...

18 is right between a pair of twin primes, and 28 is a perfect number, so let's grab both of those:

40, 44, 45, 48, 50, 52, 54, 63, 66, 68, ...

These numbers are getting rather boring, so let's stop there. But conceivably you could take this arbitrarily far. As long as the set of numbers with any given attribute have an asymptotic density of 0 (i.e., become arbitrarily rare as you go up), there will always be more uninteresting numbers to handle. And as long as the attributes you pick are efficiently computable, the computer should always be able to find them for you.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# Interactive Quantum Circuits

2013-04-02

The Quantum Circuit model of computation is the primary model used by theoretical computer scientists to study quantum computers (in the same way that the Turing Machine is used to study classical computers). It's definitely important if you're studying computation, but can also be useful for understanding aspects of quantum mechanics more generally.

My experience was that quantum circuits were mostly dealt with algebraically. I had a hard time visualizing the quantum states I was dealing with, partly because they exist in a high-dimensional space and partly because they involve complex numbers. I've attempted to tame them a little bit by building a quantum circuit simulator, using a circular display for the complex amplitudes. For example, these are the representations for the numbers 1, 0, and (i-1)/2:

Combine that with the ability to move time forward and backward through the circuit, and the result is something that for me goes a lot further toward conveying the effects of the various quantum gates than the standard algebraic approach.

I've posted it here. It includes a circuit editor, permalinks for created circuits, and transition diagrams for individual gates. Unfortunately I don't have time at the moment for a full explanation of quantum computation, but hopefully for those unfamiliar with it the simulator can be a helpful supplement to other explanations.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# Top-Heavy Towers and Borromean Rings

2013-02-25

Considering the strong correlation between my 20-month blog silence and the amount of time I've spent playing with baby toys in the interim, it seems appropriate to start back with a post about those baby toys.

## Borromean rings

To start with there are a whole slew of these broken colored rings lying around, presumably intended to be linked together in a chain.

I noticed that the oblong shape allows them to be assembled into Borromean rings.

## Top-Heavy Towers

Then there are all of these stereotypical wooden cubes.

It's probably pretty common to probe the limits of top-heavy structures. It occurred to me to try a single block with two blocks atop it, three blocks on the next layer, and so on as high as possible.

Each successive step seemed equally dubious.

After eight layers I ran out of the standard style of blocks and had to fall back on the alternate.

I tried adding an eleventh layer but everything started falling over at that point.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# A Googol Hundred

2011-06-08

An unsuspecting friend recently reported that her five-year-old son is a fan of big numbers in general, and one number in particular. His favorite number is One Googol and One Hundred (or 10100 + 100), which I will here on out refer to as the number “Samuel” to keep my sentences to a reasonable length. He wanted to be able to count to Samuel in the same way that you might count to other numbers by skipping a regular amount, such as counting to 1000 by tens.

As I started thinking through the various options, I realized that the answer depended on the prime factorization of Samuel, since any number by which you could count to Samuel would have to be a divisor of Samuel. One obvious divisor of Samuel is 100. Counting to Samuel by 100’s is certainly not feasible, but counting to Samuel by “Samuel divided by one hundred”s (or 1098 + 1 or one hundred untrigintillion and one) is, and that was my first suggestion. But then I wondered if the full factorization of Samuel would give other options. Factoring 100-digit numbers isn’t something that I know how to get my computer to do, but fortunately Wolfram Alpha was up to the task.

The result revealed that there are actually quite a handful of options for counting to Samuel in a reasonable amount of time, so I thought I would present them here, just for the joy of looking at really big numbers written out in words. These are all the numbers you can count to Samuel by in fewer than a thousand steps, sorted by and labeled by number of steps:

• 2: five duotrigintillion and fifty
• 4: two duotrigintillion five hundred untrigintillion and twenty-five
• 5: two duotrigintillion and twenty
• 10: one duotrigintillion and ten
• 20: five hundred untrigintillion and five
• 25: four hundred untrigintillion and four
• 29: three hundred and forty-four untrigintillion eight hundred and twenty-seven trigintillion five hundred and eighty-six novemvigintillion two hundred and six octovigintillion eight hundred and ninety-six septemvigintillion five hundred and fifty-one sesvigintillion seven hundred and twenty-four quinquavigintillion one hundred and thirty-seven quattuorvigintillion nine hundred and thirty-one tresvigintillion thirty-four duovigintillion four hundred and eighty-two unvigintillion seven hundred and fifty-eight vigintillion six hundred and twenty novemdecillion six hundred and eighty-nine octodecillion six hundred and fifty-five septendecillion one hundred and seventy-two sexdecillion four hundred and thirteen quindecillion seven hundred and ninety-three quattuordecillion one hundred and three tredecillion four hundred and forty-eight duodecillion two hundred and seventy-five undecillion eight hundred and sixty-two decillion sixty-eight nonillion nine hundred and sixty-five octillion five hundred and seventeen septillion two hundred and forty-one sextillion three hundred and seventy-nine quintillion three hundred and ten quadrillion three hundred and forty-four trillion eight hundred and twenty-seven billion five hundred and eighty-six million two hundred and six thousand nine hundred
• 50: two hundred untrigintillion and two
• 58: one hundred and seventy-two untrigintillion four hundred and thirteen trigintillion seven hundred and ninety-three novemvigintillion one hundred and three octovigintillion four hundred and forty-eight septemvigintillion two hundred and seventy-five sesvigintillion eight hundred and sixty-two quinquavigintillion sixty-eight quattuorvigintillion nine hundred and sixty-five tresvigintillion five hundred and seventeen duovigintillion two hundred and forty-one unvigintillion three hundred and seventy-nine vigintillion three hundred and ten novemdecillion three hundred and forty-four octodecillion eight hundred and twenty-seven septendecillion five hundred and eighty-six sexdecillion two hundred and six quindecillion eight hundred and ninety-six quattuordecillion five hundred and fifty-one tredecillion seven hundred and twenty-four duodecillion one hundred and thirty-seven undecillion nine hundred and thirty-one decillion thirty-four nonillion four hundred and eighty-two octillion seven hundred and fifty-eight septillion six hundred and twenty sextillion six hundred and eighty-nine quintillion six hundred and fifty-five quadrillion one hundred and seventy-two trillion four hundred and thirteen billion seven hundred and ninety-three million one hundred and three thousand four hundred and fifty
• 100: one hundred untrigintillion and one
• 101: ninety-nine untrigintillion nine trigintillion nine hundred novemvigintillion nine hundred and ninety octovigintillion ninety-nine septemvigintillion nine sesvigintillion nine hundred quinquavigintillion nine hundred and ninety quattuorvigintillion ninety-nine tresvigintillion nine duovigintillion nine hundred unvigintillion nine hundred and ninety vigintillion ninety-nine novemdecillion nine octodecillion nine hundred septendecillion nine hundred and ninety sexdecillion ninety-nine quindecillion nine quattuordecillion nine hundred tredecillion nine hundred and ninety duodecillion ninety-nine undecillion nine decillion nine hundred nonillion nine hundred and ninety octillion ninety-nine septillion nine sextillion nine hundred quintillion nine hundred and ninety quadrillion ninety-nine trillion nine billion nine hundred million nine hundred and ninety thousand one hundred
• 116: eighty-six untrigintillion two hundred and six trigintillion eight hundred and ninety-six novemvigintillion five hundred and fifty-one octovigintillion seven hundred and twenty-four septemvigintillion one hundred and thirty-seven sesvigintillion nine hundred and thirty-one quinquavigintillion thirty-four quattuorvigintillion four hundred and eighty-two tresvigintillion seven hundred and fifty-eight duovigintillion six hundred and twenty unvigintillion six hundred and eighty-nine vigintillion six hundred and fifty-five novemdecillion one hundred and seventy-two octodecillion four hundred and thirteen septendecillion seven hundred and ninety-three sexdecillion one hundred and three quindecillion four hundred and forty-eight quattuordecillion two hundred and seventy-five tredecillion eight hundred and sixty-two duodecillion sixty-eight undecillion nine hundred and sixty-five decillion five hundred and seventeen nonillion two hundred and forty-one octillion three hundred and seventy-nine septillion three hundred and ten sextillion three hundred and forty-four quintillion eight hundred and twenty-seven quadrillion five hundred and eighty-six trillion two hundred and six billion eight hundred and ninety-six million five hundred and fifty-one thousand seven hundred and twenty-five
• 145: sixty-eight untrigintillion nine hundred and sixty-five trigintillion five hundred and seventeen novemvigintillion two hundred and forty-one octovigintillion three hundred and seventy-nine septemvigintillion three hundred and ten sesvigintillion three hundred and forty-four quinquavigintillion eight hundred and twenty-seven quattuorvigintillion five hundred and eighty-six tresvigintillion two hundred and six duovigintillion eight hundred and ninety-six unvigintillion five hundred and fifty-one vigintillion seven hundred and twenty-four novemdecillion one hundred and thirty-seven octodecillion nine hundred and thirty-one septendecillion thirty-four sexdecillion four hundred and eighty-two quindecillion seven hundred and fifty-eight quattuordecillion six hundred and twenty tredecillion six hundred and eighty-nine duodecillion six hundred and fifty-five undecillion one hundred and seventy-two decillion four hundred and thirteen nonillion seven hundred and ninety-three octillion one hundred and three septillion four hundred and forty-eight sextillion two hundred and seventy-five quintillion eight hundred and sixty-two quadrillion sixty-eight trillion nine hundred and sixty-five billion five hundred and seventeen million two hundred and forty-one thousand three hundred and eighty
• 202: forty-nine untrigintillion five hundred and four trigintillion nine hundred and fifty novemvigintillion four hundred and ninety-five octovigintillion forty-nine septemvigintillion five hundred and four sesvigintillion nine hundred and fifty quinquavigintillion four hundred and ninety-five quattuorvigintillion forty-nine tresvigintillion five hundred and four duovigintillion nine hundred and fifty unvigintillion four hundred and ninety-five vigintillion forty-nine novemdecillion five hundred and four octodecillion nine hundred and fifty septendecillion four hundred and ninety-five sexdecillion forty-nine quindecillion five hundred and four quattuordecillion nine hundred and fifty tredecillion four hundred and ninety-five duodecillion forty-nine undecillion five hundred and four decillion nine hundred and fifty nonillion four hundred and ninety-five octillion forty-nine septillion five hundred and four sextillion nine hundred and fifty quintillion four hundred and ninety-five quadrillion forty-nine trillion five hundred and four billion nine hundred and fifty million four hundred and ninety-five thousand and fifty
• 281: thirty-five untrigintillion five hundred and eighty-seven trigintillion one hundred and eighty-eight novemvigintillion six hundred and twelve octovigintillion ninety-nine septemvigintillion six hundred and forty-four sesvigintillion one hundred and twenty-eight quinquavigintillion one hundred and thirteen quattuorvigintillion eight hundred and seventy-nine tresvigintillion three duovigintillion five hundred and fifty-eight unvigintillion seven hundred and eighteen vigintillion eight hundred and sixty-one novemdecillion two hundred and nine octodecillion nine hundred and sixty-four septendecillion four hundred and twelve sexdecillion eight hundred and eleven quindecillion three hundred and eighty-seven quattuordecillion nine hundred tredecillion three hundred and fifty-five duodecillion eight hundred and seventy-one undecillion eight hundred and eighty-six decillion one hundred and twenty nonillion nine hundred and ninety-six octillion four hundred and forty-one septillion two hundred and eighty-one sextillion one hundred and thirty-eight quintillion seven hundred and ninety quadrillion thirty-five trillion five hundred and eighty-seven billion one hundred and eighty-eight million six hundred and twelve thousand and one hundred
• 290: thirty-four untrigintillion four hundred and eighty-two trigintillion seven hundred and fifty-eight novemvigintillion six hundred and twenty octovigintillion six hundred and eighty-nine septemvigintillion six hundred and fifty-five sesvigintillion one hundred and seventy-two quinquavigintillion four hundred and thirteen quattuorvigintillion seven hundred and ninety-three tresvigintillion one hundred and three duovigintillion four hundred and forty-eight unvigintillion two hundred and seventy-five vigintillion eight hundred and sixty-two novemdecillion sixty-eight octodecillion nine hundred and sixty-five septendecillion five hundred and seventeen sexdecillion two hundred and forty-one quindecillion three hundred and seventy-nine quattuordecillion three hundred and ten tredecillion three hundred and forty-four duodecillion eight hundred and twenty-seven undecillion five hundred and eighty-six decillion two hundred and six nonillion eight hundred and ninety-six octillion five hundred and fifty-one septillion seven hundred and twenty-four sextillion one hundred and thirty-seven quintillion nine hundred and thirty-one quadrillion thirty-four trillion four hundred and eighty-two billion seven hundred and fifty-eight million six hundred and twenty thousand six hundred and ninety
• 404: twenty-four untrigintillion seven hundred and fifty-two trigintillion four hundred and seventy-five novemvigintillion two hundred and forty-seven octovigintillion five hundred and twenty-four septemvigintillion seven hundred and fifty-two sesvigintillion four hundred and seventy-five quinquavigintillion two hundred and forty-seven quattuorvigintillion five hundred and twenty-four tresvigintillion seven hundred and fifty-two duovigintillion four hundred and seventy-five unvigintillion two hundred and forty-seven vigintillion five hundred and twenty-four novemdecillion seven hundred and fifty-two octodecillion four hundred and seventy-five septendecillion two hundred and forty-seven sexdecillion five hundred and twenty-four quindecillion seven hundred and fifty-two quattuordecillion four hundred and seventy-five tredecillion two hundred and forty-seven duodecillion five hundred and twenty-four undecillion seven hundred and fifty-two decillion four hundred and seventy-five nonillion two hundred and forty-seven octillion five hundred and twenty-four septillion seven hundred and fifty-two sextillion four hundred and seventy-five quintillion two hundred and forty-seven quadrillion five hundred and twenty-four trillion seven hundred and fifty-two billion four hundred and seventy-five million two hundred and forty-seven thousand five hundred and twenty-five
• 505: nineteen untrigintillion eight hundred and one trigintillion nine hundred and eighty novemvigintillion one hundred and ninety-eight octovigintillion nineteen septemvigintillion eight hundred and one sesvigintillion nine hundred and eighty quinquavigintillion one hundred and ninety-eight quattuorvigintillion nineteen tresvigintillion eight hundred and one duovigintillion nine hundred and eighty unvigintillion one hundred and ninety-eight vigintillion nineteen novemdecillion eight hundred and one octodecillion nine hundred and eighty septendecillion one hundred and ninety-eight sexdecillion nineteen quindecillion eight hundred and one quattuordecillion nine hundred and eighty tredecillion one hundred and ninety-eight duodecillion nineteen undecillion eight hundred and one decillion nine hundred and eighty nonillion one hundred and ninety-eight octillion nineteen septillion eight hundred and one sextillion nine hundred and eighty quintillion one hundred and ninety-eight quadrillion nineteen trillion eight hundred and one billion nine hundred and eighty million one hundred and ninety-eight thousand and twenty
• 562: seventeen untrigintillion seven hundred and ninety-three trigintillion five hundred and ninety-four novemvigintillion three hundred and six octovigintillion forty-nine septemvigintillion eight hundred and twenty-two sesvigintillion sixty-four quinquavigintillion fifty-six quattuorvigintillion nine hundred and thirty-nine tresvigintillion five hundred and one duovigintillion seven hundred and seventy-nine unvigintillion three hundred and fifty-nine vigintillion four hundred and thirty novemdecillion six hundred and four octodecillion nine hundred and eighty-two septendecillion two hundred and six sexdecillion four hundred and five quindecillion six hundred and ninety-three quattuordecillion nine hundred and fifty tredecillion one hundred and seventy-seven duodecillion nine hundred and thirty-five undecillion nine hundred and forty-three decillion sixty nonillion four hundred and ninety-eight octillion two hundred and twenty septillion six hundred and forty sextillion five hundred and sixty-nine quintillion three hundred and ninety-five quadrillion seventeen trillion seven hundred and ninety-three billion five hundred and ninety-four million three hundred and six thousand and fifty
• 580: seventeen untrigintillion two hundred and forty-one trigintillion three hundred and seventy-nine novemvigintillion three hundred and ten octovigintillion three hundred and forty-four septemvigintillion eight hundred and twenty-seven sesvigintillion five hundred and eighty-six quinquavigintillion two hundred and six quattuorvigintillion eight hundred and ninety-six tresvigintillion five hundred and fifty-one duovigintillion seven hundred and twenty-four unvigintillion one hundred and thirty-seven vigintillion nine hundred and thirty-one novemdecillion thirty-four octodecillion four hundred and eighty-two septendecillion seven hundred and fifty-eight sexdecillion six hundred and twenty quindecillion six hundred and eighty-nine quattuordecillion six hundred and fifty-five tredecillion one hundred and seventy-two duodecillion four hundred and thirteen undecillion seven hundred and ninety-three decillion one hundred and three nonillion four hundred and forty-eight octillion two hundred and seventy-five septillion eight hundred and sixty-two sextillion sixty-eight quintillion nine hundred and sixty-five quadrillion five hundred and seventeen trillion two hundred and forty-one billion three hundred and seventy-nine million three hundred and ten thousand three hundred and forty-five
• 725: thirteen untrigintillion seven hundred and ninety-three trigintillion one hundred and three novemvigintillion four hundred and forty-eight octovigintillion two hundred and seventy-five septemvigintillion eight hundred and sixty-two sesvigintillion sixty-eight quinquavigintillion nine hundred and sixty-five quattuorvigintillion five hundred and seventeen tresvigintillion two hundred and forty-one duovigintillion three hundred and seventy-nine unvigintillion three hundred and ten vigintillion three hundred and forty-four novemdecillion eight hundred and twenty-seven octodecillion five hundred and eighty-six septendecillion two hundred and six sexdecillion eight hundred and ninety-six quindecillion five hundred and fifty-one quattuordecillion seven hundred and twenty-four tredecillion one hundred and thirty-seven duodecillion nine hundred and thirty-one undecillion thirty-four decillion four hundred and eighty-two nonillion seven hundred and fifty-eight octillion six hundred and twenty septillion six hundred and eighty-nine sextillion six hundred and fifty-five quintillion one hundred and seventy-two quadrillion four hundred and thirteen trillion seven hundred and ninety-three billion one hundred and three million four hundred and forty-eight thousand two hundred and seventy-six

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# The Ham Sandwich Theorem

2011-06-07

Once again Algebraic Topology compelled me to write code. This time it was the Ham Sandwich Theorem, when I realized that it wouldn’t be too hard to demonstrate the two dimensional version of the theorem with another interactive doohickey.

The interpretation from which the Ham Sandwich Theorem gets its name says that if you have two slices of bread and a slice of ham between them, then no matter what their respective shapes or volumes or how they are positioned relative to each other, it’s always possible to make a single straight slice through the sandwich resulting in all three pieces being exactly bisected.

The Ham Sandwich Theorem applies to any N solids in N-dimensional space, so the 2D version says that any two sets of geometric shapes can be simultaneously bisected by a line. I said “two sets” rather than “two shapes” because the theorem actually doesn’t rely on the shapes even being connected. So we can talk about a collection of red and blue circles, as in the image below:

No matter how the circles are arranged, and no matter how many of them there are, there will always be at least one line that bisects both sets by area simultaneously. The interactive version lets you add, remove, and rearrange the circles.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# Primitive Triangles

2011-05-28

I’ve been spending some of my free time the last week and a half watching Norman Wildberger’s Lectures on Algebraic Topology. One of the things I’ve learned is that an m-by-n rectangle with integer dimensions can be partitioned into 2×m×n triangles with area ½ and corners at integral points. This fact by itself is rather obvious, given the most regular partitioning shown below:

The part that surprised me is that the sides of the triangles can be arbitrarily long, allowing a variety of different shapes, and the whole thing still works out. Here’s another way to partition the 5-by-5 rectangle:

The fact that they all have the same area is a consequence of Pick’s Theorem. I wanted to see what sorts of partitionings you get by starting with a bare rectangle and adding lines at random. And that’s exactly where the image above came from.

Here are a couple more, just for fun.

There's some javascript trying to load some comments, and if you're reading this, it's probably not working.

# These Two Graphs Do This

2011-05-17

I’ve been doing some academic research lately that involves computing the probability that a network that grows by adding links in a particular way will end up with certain properties. I went about this by generating all graphs up to a particular order, and so I used unlabeled graphs, which seemed good enough and meant I had far fewer graphs to deal with.

Eventually I decided that it would be more realistic to at least pretend that the computation was being done on labeled graphs (by making sure that I got the same answer either way). This led me to a discovery that wasn’t too surprising by itself, but I was surprised that I hadn’t thought of it earlier: there are (unlabeled) graphs for which adding two completely different edges will produce the same graph. For illustration I found the smallest example:

The first thing to notice about this graph is that it’s completely asymmetric: The pink and orange vertices have the distinction of being the only degree-4 and degree-2 vertices respectively. The blue vertex is distinguished as being the only vertex adjacent to both the pink and orange. The green vertex is the only degree-1 vertex adjacent to the pink, and the yellow and blue vertices are clearly distinct from each other as they have different degrees. So there is no symmetry in this graph whatsoever, which means that any edge we could conceivably add to it would be “different” from any other edge we could add.

So there are two different edges we can add to this graph and end up with graphs that are isomorphic to each other. Specifically, by adding either edge we will end up with this graph:

Another way to say it is that our original colored graph is a subgraph of this graph in two different ways. This can be easily illustrated by repositioning the vertices so they match the supergraph in two different ways:

You should be able to confirm visually that these two are the same as the original graph, and that they can each be transformed into the supergraph by adding a single edge, which is drawn dashed.

So this is the smallest pair of graphs that has this property, and in fact the only example on six vertices. I’m not sure how common they are. It is not a straightforward thing to google.

Another cool thing is that, apparently just by coincidence, the smaller graph and the larger graph are complements of each other. So if we take the original graph and reverse all the links like so:

we end up with the same graph that we got by adding an edge:

Kinda weird.