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 10¹⁰⁰ + 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 10⁹⁸ + 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

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.

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.

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.

Last year at the first Clojure Conj, for some reason or another I started pondering ways to improve on the classic lazy-list-of-primes (which I took a quasi stab at in an old post). Most of the simpler examples use division to check primality, which performs terribly compared to addition-based algorithms like the Sieve of Eratosthenes.

However, sieve implementations usually compute huge chunks of primes at once, while I wanted to be able to compute one prime at a time, hopefully using Clojure’s iterate function. I wanted it to perform similarly to the classic sieve in terms of time, and to have space requirements proportional to the square root of the prime being computed (particularly not holding the entire preceding sequence of primes in memory when only a fraction of that is actually needed).

So after thinking about the structure of the sieve algorithm for a bit, I realized that it actually was amenable to computing primes iteratively. In the classic sieve algorithm, given a candidate range, for each relevant small prime you sweep through the range marking off the multiples of that prime. The prime numbers in the range are those that remain after all the small primes have swept through. The key to making this iterative is, given a prime, rather than sweeping through an array, you just keep track of its next multiple. When that multiple comes up as a candidate, you mark it as composite, and then update your “next multiple” value for that prime. Of course you have to juggle several small primes instead of just one, so this might be a good point to bring up the actual code.

We start with the following object:

(def initial
  {:p        3,
   :divisors {9 '(3)},
   :square   9,
   :primes   nil})

The value of :p is the current prime. We first create a lazy seq of objects like this one, and turning that into a seq of primes is simply mapping to the value of :p. The value of :divisors is the data structure partially described in the previous paragraph. It is a map whose keys are upcoming composite numbers, and whose values are the primes relevant to those composites. The first odd composite to be on the lookout for is 9, and the only prime corresponding to it is 3. The last two keys, :square and :primes, are used for adding primes to the :divisors map. The value of :square tells us when to add a new prime, and the value of :primes will tell us what that prime is.

Let’s see how the initial object is iterated. The initial object corresponds to the prime 3, so the next object corresponds to the prime 5:

{:p        5,
 :divisors {9 (3)},
 :square   9,
 :primes   nil} 

Not much changed. The only difference is that :p now maps to 5 instead of 3. This will also be the case for 7, so let’s skip that and go right to 11:

{:p        11,
 :divisors {15 (3), 25 (5)},
 :square   25,
 :primes   {:p 5, :divisors {9 (3)}, :square 9, :primes nil}}

There’s been a few changes here. When the 7 object was passed to the iterator function, it incremented 7 to 9 and checked if 9 was present in the :divisors map. Since it was, it knew that 9 was composite. First it updated the :divisors map from {9 (3)} to {15 (3)}, by computing that the next composite for three is 9 + 3 * 2 (we double the prime since we’re skipping even numbers). Then it checked if the current number under consideration (9) was equal to the value of :square. Since it was, it computed the next prime to add to the :divisors hash, which is of course 5. Computing the next prime, however, requires a bit of recursion, since computing primes is the actual task at hand. So the :primes key ends up pointing to a nested version of the exact object we’re looking at, and if you look at the :primes object above you can see it’s identical to the entire object given for p = 5.

This recursion is how we avoid keeping the entire list of primes in memory. Let’s see what the object looks like after computing the 10000th prime:

{:p 104729,
 :divisors
   {104737 (17 61 101),
    104833 (79),
    104993 (283),
    104835 (241),
    104867 (71 211),
    104931 (131),
    105187 (293),
    104741 (7 13),
    104805 (137),
    104775 (127),
    104807 (311),
    104777 (29),
    104809 (163),
    104873 (199),
    104937 (263),
    105001 (197),
    105033 (157 223),
    104747 (19 37 149),
    104843 (59),
    104749 (31 109),
    104781 (53),
    104813 (281),
    104877 (271),
    105101 (227),
    104751 (103 113),
    104753 (89 107),
    104945 (139 151),
    105073 (179),
    105169 (251),
    104755 (41 73),
    105011 (173),
    105043 (167),
    105301 (307),
    104791 (43),
    104855 (67 313),
    104983 (277),
    105111 (229),
    104857 (97),
    104921 (239),
    105113 (257),
    109561 (331),
    104731 (11),
    104763 (47),
    104859 (191),
    105083 (233),
    105179 (269),
    104733 (3),
    104765 (23),
    104829 (83),
    104735 (5),
    104799 (181 193),
    104927 (317)},
 :square 109561,
 :primes
   {:p 331,
    :divisors
      {343 (7), 333 (3), 351 (13), 335 (5), 357 (17), 341 (11), 361 (19)},
    :square 361,
    :primes
      {:p 19,
       :divisors {21 (3), 25 (5)},
       :square 25,
       :primes {:p 5, :divisors {9 (3)}, :square 9, :primes nil}}}}

As you can see there are several layers of nesting going on. This nesting does not create much performance overhead, since the nested versions don’t get very far relative to the main sequence, and I think it makes the algorithm simpler.

I did some minor googling to see if anybody else had done something like this, and I did find one that was quite similar. However, it looks like that programmer used explicit nested lazy seqs, while I wanted to keep the nested seqs implicit so the the objects iterated over remained finite.

Anyhow, here’s the full source code. I have a difficult time explaining algorithms like this clearly, so I will consider myself lucky if I’ve successfully communicated to a single person.

Was doodling in class recently:

And so of course this led to the discovery of Sloane A000081. For some reason I wasn’t expecting the rooted trees connection (I didn’t draw them until after I had read about it).

Given a sequence of integers, a common mathematical task is to try to find a short “closed” form for the sequence. For example, a closed form for (2,6,12,20,…) is n*(n+1), a closed form for (-1,1,-1,1,-1,…) is (-1)^n, and a closed form for (1,1,2,2,3,3,…) is floor((n+1)/2) (where the floor function rounds down).

The last two are interesting because they are not continuous. This means that if you interpreted the ‘closed form’ as a function of real numbers and plotted it on a graph, you would not see a smooth continuous line. In the case of floor((n+1)/2), you would see horizontal lines each two units long, and each one one unit higher than the previous:

In the case of (-1)^n, I don’t think there’s any kind of continuity whatsoever. You might be able to say that the function is defined when n is rational, but I think that’s as far as it goes.

For some reason that I can’t properly justify, I don’t like this. I like it when an integer sequence can be generated by a continuous smooth curve. Any finite sequence can be generated by a polynomial with a degree that is at most one less than the length of the sequence, which is exactly what my sequences-to-functions app does. For example, the sequence (1,2,3,4,1) can be generated by the polynomial (-1/6)x^4 + (5/3)x^3 – (35/6)x^2 + (28/3)x – 4:

Of course, the next value generated by the polynomial is not 2, as the sequence suggests, but -14. In general any polynomial generated by a sequence like this will rocket upward or downward at either end. So you can’t get any kind of periodic behavior out of polynomials. I started investigating using the sine function for periodic behavior back in high school when I first encountered the double-counting sequence (1,1,2,2,3,3,…).

The sine curve can help when we note that the double counting sequence can be written as the sum of two other simpler sequences:

   0.5,  1.0,  1.5,  2.0,  2.5,  3.0,  3.5,  4.0,  ...
 + 0.5,  0.0,  0.5,  0.0,  0.5,  0.0,  0.5,  0.0,  ...
-------------------------------------------------------
   1.0,  1.0,  2.0,  2.0,  3.0,  3.0,  4.0,  4.0,  ...

The first of these is simply f(x) = x/2, and the second is a simple alternation between 0 and 0.5. The sine curve is great at alternating, so all we need is to stretch and pull it to make everything line up correctly:

This was as far as I thought about the issue in high school, and aside from a brief resurfacing in college calculus, it didn’t come to mind again until recently when a friend of mine started taking calculus. Only then did I realize that there are glaring questions here: What other sequences can we produce with these tools? What periods can they have? Would anybody like a beer?

So I’ve thought about these questions some during my spare moments the last few weeks, and have a few answers so far. The first thing I noted was that, for a given period, there is a canonical sequence that we may as well call a “basis”, from which any periodic sequence can be constructed. The simplest for a period P is simply P-1 zeros followed by a single one. For example, with P = 5, the canonical sequence (call it ‘the 5-basis’) would be (0,0,0,0,1,0,0,0,0,1,0,…). This is sufficient to create any period-5 sequence by simply shifting back and forth and multiplying. If our canonical sequence is called f(n), and we want to create the sequence (1,9,6,2,5,1,9,6,2,5,1,…), we can do each of the five numbers individually and then add them together:

g(n) = f(n+4) + 9*f(n+3) + 6*f(n+2) + 2*f(n+1) + 5*f(n)

   1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, ...
   0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 0, ...
   0, 0, 6, 0, 0, 0, 0, 6, 0, 0, 0, ...
   0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, ...
 + 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, ...
----------------------------------------
   1, 9, 6, 2, 5, 1, 9, 6, 2, 5, 1, ...

So finding a basis function gives us a lot. It also gives us the repeated counting function for its period (for period P, start with f(x) = x/P and then subtract off appropriate amounts using P-1 fractional multiples of the basis). The next question then is what basis functions can we construct from the sine function? The basis for P=2 is not hard, since the most obvious characteristic of the sine function is that it alternates between two values. P=4 also turns out to be pretty easy, because the sine function also has a clean period-4 version, which isn’t a basis function but can easily produce a basis function when combined with the 2-basis:

The 4-basis can be used to create a period-4 counting loop:

This was as far as I got at first — I wasn’t sure if I could use the sine function to create a basis for any periods other than 2 and 4. Eventually I weasled out a period-3 basis using a single sine wave:

Which we can of course use to make a triple-counting function:

And most recently using all sorts of shameful tricks I found a basis for period-5:

I haven’t yet figured out if the witchcraft that was involved can be used for higher prime periods, of if there is any hope for aperiodic sequences like (1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,…). But I do know that if you multiply the 3-basis with the 5-basis you get a 15-basis, and so I have no choice but to conclude with a graph for a period-15 sequence of random integers from 0 to 10:

Apparently, the Qwerty-to-Dvorak keyboard permutation, which I just performed on an office keyboard, contains two large cycles, two double cycles (bicycles?), and two trivial cycles:

Easily convinced friends, your computer, and various internet sources not held accountable to any standard of accuracy may assert that 2011 is a prime number, but it would be foolish to blindly accept the claims of uninformed sheeple and agenda-driven pundits. If you’re interested in discovering the truth about this important issue and want to verify the primality yourself by hand, it should be sufficient to check the following equations:

• 2  × 1005 + 1  = 2011

• 3  × 670  + 1  = 2011

• 5  × 402  + 1  = 2011

• 7  × 287  + 2  = 2011

• 11 × 182  + 9  = 2011

• 13 × 154  + 9  = 2011

• 17 × 118  + 5  = 2011

• 19 × 105  + 16 = 2011

• 23 × 87   + 10 = 2011

• 29 × 69   + 10 = 2011

• 31 × 64   + 27 = 2011

• 37 × 54   + 13 = 2011

• 41 × 49   + 2  = 2011

• 43 × 46   + 33 = 2011

• 45 × 45        = 2025

Don’t immediately accept what you’re told! Always check the facts.

Google has this habit of providing extra links to sites within its search results, which go to specific supposedly popular pages within the site. I’ve made use of them a number of times and they’re usually pretty helpful, though I’ve never determined the sort of rules that produce the links (they’re plentiful enough that I assume they aren’t done manually).

Then today I noticed an interesting instance of the feature when I searched for “wiktionary”: