A cool sequence problem…

Our oldest son (nearly 10) posed the following challenge:

What comes next in this list?

1, 1, 1, 2, 2, 3, 2, 4, 3, …

Answer and rationale (his and mine) after the jump…

Reverse and Add

If you start with a positive integer, reverse the digits, and add that to the original number you sometimes get a palindrome.  For example,  123+321=444, and 1047+7401=8448.

But sometimes you don’t.  In that case, you might need to repeat the process a few times (where “a few” could mean “a lot”).  For example, 498+894=1392, then 1392+2931=4323, and finally 4323+3234=7557.

Based on this, we can define the palindromic order of a number as the number of time that you need to Reverse and Add before coming up with a palindrome.  In the examples above, 123 and 1047 have a palindromic order of 1, while 498 has a palindromic order of 3.  [Presumably under this definition a palindrome like 838 has palindromic order of 0.]  Incidentally, this definition of palindromic order is the one used by Susan Eddings here, as opposed to the one referenced in titles like “Optimization of the palindromic order of the TtgR operator enhances binding cooperativity” in The Journal of Molecular Biology.

So here’s the question:  Does every positive integer have a (finite) palindromic order?  In other words, if you pick a number and repeat this process, possibly neglecting all of your work and home commitments except for feeding the cats and watching The Big Bang Theory, can you be assured that you will eventually get a palindrome?

And the answer is:  I don’t know.  And neither does anyone else, although there’s evidence that the answer is No.

That evidence is the number 196.  If you start with 196, you won’t get a palindrome at first, within 200 steps (as Jason Doucette shows), or even within 700 million iterations.   There are other numbers that appear to have this same awkward non-palindromic property  [for example, 691, and also 295, 394, and a bunch more], but the number 196 is the smallest; in its honor, this “Reverse and Add” algorithm has come to be known as the 196-algorithm.

So spending all your time concentrating on a brute force method of finding out if 196 continues to produce non-palindromes is going to be tedious.  In good news, you could explore other interesting questions:  what do you notice about numbers with palindromic order 1?  Can you find one with palindromic order 4? Which number(s) under 100 has the largest palindromic order?

As a side note, I ran across this property while looking for  interesting mathematical processes that resulted in the sequence 2, 4, 6, 8, 10, 11, [part of my ongoing quest to find Patterns that Fail].  It turns out that if you look at which numbers can be written as the sum of a positive integer plus its reverse, you initially get the sequence 0, 2, 4, 6, 8, 10,  [0=0+0, 2=1+1, up to 10=5+5] but then 11 shows up, since 11=10+01.

The picture above is the Shoulder Sleeve Insignia of the 196th Infantry Bridage.  Isn’t the symmetry a nice parallel to the whole Reverse and Add idea? 196InfBdeSSI.gif

One, Two, Three, Four, Six [Again. And then again!]

I’m teaching a math course for non-majors, and right now we’re talking about Induction versus Deduction. I have some neat examples of Induction, like the fact that the US presidents elected in 1840, 1860, 1880, 1900, 1920, 1940, and 1960 all died in office, but Ronald Reagan did not. I’ve found, though, that these cultural examples don’t carry as much weight for the students as a mathematical pattern that continues for a while and then stops. Hence my interest in Patterns that Fail.

In this vein, last week I looked at how many necklaces could be made out of N beads, where the beads could be two different colors, and it turns out that the number of necklaces follows the pattern one [for 0 beads], two [for 1 bead], three [for 2 beads], four [for 3 beads], and then six [for 4 beads]. But there’s another setup that gives the same pattern 1, 2, 3, 4 before jumping to 6. This setup involves covering 3xN rectangles with dominoes that are 1×3 or 3×1 (tri-ominoes? But I think those are L-shaped).

If you start with N=2 (to avoid the sequence beginning 1,1,…), there is one way:

If N=3, there are two ways:

If N=4, there are three ways:

If N=5, there are four ways:

But if N=6, suddenlythere are six ways!

After that, the pattern grows in larger steps [following the recursive pattern a(n)=a(n-1)+a(n-3)].

Incidentally, there’s another pattern that starts off 1, 2, 3, 4, 6, ….: the number of ways to make N cents in 1¢, 2¢, 3¢, 5¢, 10¢, 20¢, 25¢, 50¢ and/or 100¢ coins, all of which are or have been valid US coins. For example:

• 1¢ can only be made with a 1¢ coin. [1 way]
• 2¢ can be made with two 1¢ coins or 1 2¢ coin. [2 ways]
• 3¢ can be made with three 1¢ coins, a 1¢ and a 2¢ coin, and a 3¢ coin. [3 ways]
• 4¢ can be made with four 1¢ coins, two 1¢ and one 2¢ coins, one 1¢ and one 3¢ coins, or two 2¢ coins. [4 ways]
• 5¢ an be made with five 1¢ coins, three 1¢ coins and one 2¢ coin, two 1¢ coin and one 3¢ coins, one 1¢ coin and two 2¢ coins, one 3¢ coin and two one 2¢ coins, or one 5¢ coin. [6 ways]

This sequence continues 8, 10, 13, 16…so it’s different than the previous sequences, giving me lots of examples to choose from in class!

One, Two, Three, Four, Six(?)

How many necklaces can you make if you have two different color beads (like purple and gold) at your disposal?

If you put 0 beads on your necklace, there’s only one way to do so and it’s mighty boring.

Suppose you put 1 bead on your necklace. It might be purple or it might be gold, giving you two possible necklaces.

If you want to put 2 beads on your necklace, you can do so in three ways. And if you want to use 3 beads, there are four possibilities.

What about with 4 beads? It looks like the answer should be five, right? Right? You know you want to say that. ALAS, there are actually six different ways to do it.

Once the pattern of consecutive integers is broken, it stays broken. There are eight ways to make a necklace out of 5 beads, and either thirteen or fourteen ways to make it out of 6 beads: thirteen if you allow reflexive symmetry — that is, the necklace is “free” and you can flip it over in addition to rotating it — and fourteen if the necklace is “fixed” so you can rotate it but can’t flip it. And then the numbers start to increase a little faster, into the thousands if you have fifteen beads (and, umm, enough time to make a whole bunch of necklaces).

4, 6, 8, 10, 12, 14,….What comes next?

The answer, naturally, is 15. If you’re talking about the Burnt Pancake problem, that is. (And the sequence actually starts 1, 4, 6, 8… but I left off the initial 1 because otherwise you would have known right away that something was amiss.)

The Burnt Pancake problem involves pancakes of different sizes, each with one burnt side, piled up on top of one another. Here’s how famous math guy and Emmy winner David X. Cohen initially described the problem in this interview with Sarah Greenwald:

The question was how do you sort these disks to get the biggest pancake on the bottom and the smallest pancake on top [with all the burnt sides down] if they start in an arbitrary disordered state, and the only thing you’re allowed to do is put a spatula somewhere in the middle, pick up the ones above it, flip them over, and put them down, as a group. Doing that repeatedly, putting a spatula in different places, you want to sort this out. So a very physical thing, that got me excited when I found out that no one knew the answer in general for how many flips it takes to sort this thing.

Here is help us visualize this problem is our friendly neighborhood Godzilla. He’s going to use oreos with tops removed to simulate the pancakes.

With only one “pancake”, if it starts like this

the “burnt” side is already at the bottom, so it needs 0 flips to get into the proper position.

If, instead, the pancake starts “burnt” side up, it needs one flip:

(Don’t you think that Godzilla looks a little bit like that guy Craig from Hell’s Kitchen?) As the Big G has just demonstrated, if you have just ONE burnt pancake then it could take as many as, well, 1 flip to orient it correctly. That’s where the 1 in the sequence 1, 4, 6, 8, … comes from.

Now let’s look at what happens with two burnt pancakes. We want to end up with the larger pancake on the bottom, and all the burnt sides down like this:

But what will happen if the pancakes start off in a different configuration? How many flips have to be done? It turns out that it could be as many as 4 flips:

Suppose your pancakes start off in this pile: , with the burnt parts on top. The first thing Godzilla does is to put the spatula on the bottom and flip the pile over.

Now the pancakes have the burnt side down, but the smaller one is on the bottom. The big top pancake will have to be flipped:

(Godzilla’s being a little sloppy here: he should only be picking up the top pancake.) After this maneuver the burnt parts are on the “outside” but big pancake is still on top. The entire stack needs to be flipped to get the little pancake back on top:

Now the little pancake is on the top and the burnt parts are on the “outside”, so the top pancake must be flipped:

And now voilà, the pancakes are in the right order!

See how happy Godzilla is! He knows he gets to eat these oreos when all is said and done.

With a different starting configuration (there are 2!·2²=8 ways they initially could be piled up, with the smaller pancake on the top or the bottom, and the various burnt sides up or down), it turns out that it will take at most 4 flips to get them in the correct order. That’s where the 4 comes from in 1, 4, 6, 8, ….

What happens if you start with three pancakes of different sizes? The desired ending configuration is this:

There are 3!·2³=48 different ways the pancakes could start out. Some of them could be turned into the proper configuration after just one flip:

but other configurations require more. This one, for example:

The cookies are in the right order, but it just takes a lot of maneuvering to get the burnt parts on the bottom instead of the top: 6 flips. That’s the most it would take no matter how the pancakes started out.

So for one pancake it could take as many as 1 flip, for two pancakes it takes up to 4 flips, for three pancakes up to 6 flips, for four pancakes up to 8 flips, for five pancakes up to 10 flips, for six pancakes up to 12 flips, and for seven pancakes up to 14 flips.

Then for eight pancakes, it only takes up to 15 flips. And for nine pancakes 17 flips, then for ten pancakes it goes up to 18 flips (according to the Online Encylopedia of Integer Sequences). But by 11 pancakes there are over 81 billion different initial configurations, so checking by hand to find the smallest number of flips for each configuration is tough. Fortunately, as described in this earlier post, we have E. Coli to help us figure it out. [They give the E. Coli a configuration, let them do a specific number of flips, and any E. Coli that get the virtual pancakes in the right order become resistant to the antibiotic tetracycline in honor of their good effort. Then the scientists add some tetracycline and if any of the E. Coli survive, they know that the pancakes could be put in order after that particular number of flips. The animation E. Hop gives the whole scoop.]

Meanwhile, Godzilla is going to take a little break. Bon appetit!

Kepler’s First Attempt

When it comes to orbits, Johannes Kepler knew his stuff. He’s the one who in 1602 realized that planets orbit in ellipses rather than circles, which became the first of his Three Planetary Laws. But no one is perfect, and these were not his first attempts at describing the motions of the Heavens. In 1596 he published Mysterium Cosmographicum (The Mysteries of the Cosmos), in which he proposed the following model for the solar system:

In this model, the six known planets were envisioned as traveling in circles, along the equators of six giant spheres. The six giant spheres were separated by the five platonic solids. Saturn and Jupiter were separated by a giant cube, and Jupiter and Mars by a giant tetrahedron. It’s harder to see the interior planets in the drawing above, so here’s a close up:

Mars and Earth were separated by a giant dodecahedron, Earth and Venus by a giant icosahedron, and, finally, Venus and Mercury by a giant octahedron. And then, in center of all the orbits, was the Sun.

Let’s see how accurate this model is. If you start with a giant platonic solid, like a cube, you can circumscribe a sphere on the outside and inscribe a sphere on the inside, and then compare the ratio of the radii of the two spheres. It turns out to be √3≈1.73. And lo, if you look at the average radius of Saturn’s orbit (9.021 Astronomical Units) and divide it by the average radius of Jupiter’s orbit (5.20336 AU), it rounds to 1.73. Let’s see how the other ratios match up:

	Giant Polyhedron	Ratio of spheres in model	Ratio of Actual Planet Orbits
Saturn to Jupiter	cube	1.73	1.73
Jupiter to Mars	tetrahedron	3.00	3.42
Mars to Earth	dodecahedron	1.26	1.52
Earth to Venus	icosahedron	1.26	1.38
Venus to Mercury	octahedron	1.73	1.87

Not too shabby! Plus, as a bonus, you can see that the cube and the octahedron, which are dual polyhedra, have the same ratios of the radii of the circumscribed and inscribed spheres (√3≈1.73); likewise, the dodecahedron and the icosahedron (which are also duals of each other) have the same ratio of the radii of circumscribed and inscribed sphere (≈1.26). And unlike the Titius-Bode law, the big gap between Jupiter and Mars didn’t really cause any problems since the tetrahedron fit nicely in there. But a few years later Kepler realized it was wrong, and Uranus’s discovery later would have sealed the deal in any case. Poor Kepler. But it’s still an impressive idea, and was deemed important enough even recently to put on a 2002 commemorative 10-Euro coin in Austria (designed by Thomas Pesendorfer).

Yeah Kepler!

The planet data came from NASA; the data on the radii of circumscribed and inscribed spheres came from Wolfram MathWorld. It’s not clear if the coin is copyrighted or even copyrightable or not; it seems to fall under fair-use guidelines, however. You can find the coin at the Austrian Mint.

1, 2, 4, 8, what comes next?

Suppose you take a circle, put some dots along the outside, and then connect them, as in the picture to the left (which has 5 dots on the outside). If only two lines cross at any point, how many regions will the circle be divided into?

Let’s find out! If you place 1 dot along the outside you can’t connect it to anything so you get one region (the entire circle). If you place 2 dots along the outside and connect them you divide the circle into 2 regions. By placing 3 dots along the outside you divide the circle into 4 regions.

Almost Perfect: The Titius-Bode Law

It’s not perfect, and it only works for 7 of the 8 planets, but it’s still great for getting an approximation for how far apart to hang the glow-in-the-dark planets from your ceiling.

The distance from the Sun to Mercury is approximately 4 tenths of an AU (Astronomical Unit — the average distance from the Sun to the Earth), and the average distance from the Sun to Venus, Earth, Mars, the asteroid belt, Jupiter, Saturn, and Uranus is approximately [4+(3·2^N)] tenths of an AU, where N=0,1,2,3,4,5, and 6 respectively. Isn’t that a neat equation? It was first observed by David Gregory in 1702 (in Latin; 1715 in English) in his book The Elements of Astronomy and is therefore named after Johann Titius (who published a German translation of a 1724 book by Christian Wolff that contained the same description) and Johann Bode (who read Titius’s translation and put it as a footnote in his own textbook). And here’s where I’m wondering if I can get my name added to the Law by virtue of just mentioning it here.