Collatz Tree

For some reason, I have a fascination with all the different sequences of numbers that arise out of thinking about the Collatz conjecture. In this post, we’ll look at a few more of these.

The Collatz chain for a number N is the sequence of numbers that arise from repeatedly iterating the function
Screen Shot 2019-06-16 at 11.09.39 PM
until you get to 1. The Collatz conjecture is the statement that this sequence always terminates, no matter what n you start at.

In other words, f(N) is the function that tells you what N becomes after a single iteration. Let’s look at the inverse of this: what numbers become N after a single iteration?

One such number is 2N: 2N is always even, so after one step it falls down to n. Another possibility is m = (N-1)/3. Why? Well, if m is an odd number, then it will become 3m+1 = 3 (N-1)/3 + 1 = N – 1 + 1 = N. So for each N, we get either one or two new values.

The Collatz tree is what we get if we start at 1 and repeatedly iterate the inverse function. After n iterations, we get to the set of all numbers that take at most n steps to get to 1. Here’s what it looks like!

Screen Shot 2019-06-17 at 6.18.05 PM

I’ve never actually seen it plotted this way, and I think it shows something potentially important. Look at the order in the image! Why do we get this grid of apparently identical rhombuses? I’d love an explanation for this.

I also like the idea of “surfing” the jagged lower end of this graph, staying as small as possible while iterating f. In general, the lower end of the graph is the sequence of smallest numbers that take N steps to get to 1.

Here are the first thirty numbers in this sequence:

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 72, 25, 49, 98, 33, 65, 130, 43

Plotted, this sequence looks like:

Collatz Minimums

The first twelve of these numbers themselves form a Collatz chain. We leave this particular chain on the thirteenth step, at which point we enter a new chain containing 17. We stay in this new chain until seven steps later, at which point we enter a new chain containing 25. But now we only stay in this new chain for one step before departing for a new one! This is another sequence of numbers that fascinate me: the chain lengths at which our minimum values switch to entirely new chains. Here are the values for up to 100 steps:

12, 23, 24, 26, 27, 34, 36, 37, 38, 39, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 60, 61, 63, 64, 65, 72, 73, 74, 75, 76, 97, 98

The differences between these values are plotted here:

Differences

Whenever this plot spikes, this points to an existence of a Collatz chain that surfs the bottom of the Collatz tree for some time before jumping up to a higher value!

Producing all numbers using just four fours

How many of the natural numbers do you think you can produce just by combining four 4s with standard mathematical operations?

The answer might blow your mind a little bit. It’s all of them!

In particular, you can get any natural number by using the symbols ‘4’, ‘√’, ‘log’, and ‘/’. And in particular, you can do it with just four 4s!

Try it for yourself before moving on!

 

 

Continue reading “Producing all numbers using just four fours”

Buddhabrot, Mandelbrot’s older sibling

Many people have heard of Mandelbrot’s famous set. But far fewer have heard of its older sibling: the Buddhabrot. I find this object even more beautiful than the Mandelbrot set, and want to give it its proper appreciation here.

To start out with: What is the Mandelbrot set? It is defined as the set of complex values c that stay finite under arbitrary many repeated applications of the function fc(z) = z2 + c (where the first iteration is applied to z = 0).

So, for example, to check if the number 2 is in the Mandelbrot set, we just look at what happens when we plug in 0 to the function f2 and repeat:

0 becomes 02 + 2 = 2
2 becomes 22 + 2 = 6
6 becomes 62 + 2 = 38
38 becomes 382 + 2 = something large, and on and on.

You can probably predict that as we keep iterating, we’re going to eventually run off to infinity. So 2 is not in the set.

On the other hand, see what happens when we plug in -1:

0 becomes 02 + (-1) = -1
-1 becomes (-1)2 + (-1) = 0
0 becomes -1
-1 becomes 0
… and so on to infinity

With -1, we just bounce around back and forth between 0 and -1, so we clearly never diverge to infinity.

Now we can draw the elements of this set pretty easily, by simply shading in the numbers on the complex plane that are in the set. If you do so, you get the following visualization:

overallmandelbrot

Cool! But what about all those colorful visualizations you’ve probably seen? (maybe even on this blog!)

Well, whether you’re in the Mandelbrot set or not is just a binary property. So by itself the Mandelbrot set doesn’t have a rich enough structure to account for all those pretty colors. What’s being visualized in those pictures is not just whether an element is in the Mandelbrot set, but also, if it’s not in the set (i.e. if the 0 diverges to infinity upon repeated applications of fc), how quickly it leaves the set!

In other words, the colors are a representation of how not in the set numbers are. There are some complex numbers that exist near the edge of the Mandelbrot that hang around the set for many many iterations before finally blowing up and running off to infinity. And these numbers will be colored differently from, say, the number “2”, which right away starts blowing up.

And that’s how you end up with pictures like the following:

Screen Shot 2019-05-22 at 3.37.11 PM.png

Now, what if instead of visualizing how in the set various complex numbers are, we instead look at what complex numbers are most visited on average when running through Mandelbrot iterations? Well, that’s how we get the Buddhabrot!

Specifically, here’s a procedure we could run:

  1. Choose a random complex number c.
  2. Define z = 0
  3. Update: z = fc(z)
  4. Give one unit of credit to whatever complex number z is now.
  5. Repeat 3 and 4 for some fixed number of iterations.
  6. Start over back at 1 with a new complex number.

As you run this algorithm, you can visualize the results by giving complex numbers with more credits brighter colors. And as you do this, a curious figure begins to appear on the (rotated) complex plane:

Screen Shot 2019-05-22 at 4.23.06 PM.png

 

 

That’s right, Buddha is hanging out on the complex plane, hiding in the structure of the Mandelbrot set!

Hopping Midpoints

Put down three points on a piece of paper. Choose one of them as your “starting point”. Now, randomly choose one of the three points and hop from your starting point, halfway over to the chosen point. Mark down where you’ve landed. Then repeat: randomly choose one of the three starting points, and move halfway from your newly marked point to this new chosen point. Mark where you land. And on, and on, to infinity.

What pattern will arise? Watch and see!

Controls:
E to increase points/second.
Q to decrease points/second.
Click and drag the red points to move them around.
Pressing a number key will make a polygon with that number of sides.

Exploring Julia Sets

Here’s a natural follow-up to my last post on the Mandelbrot set – an interactive Julia set explorer!

The Julia set corresponding to a particular point c = x + iy in the complex plane is defined as the set of complex numbers z that stay finite upon arbitrary iterations of the following function: fc(z) = z2 + c. The Mandelbrot set, by comparison, is defined as the set of complex numbers c such that the value obtained by starting with 0 and iterating the function fc arbitrarily many times converges.

What’s remarkable is now beautiful and complex the patterns that arise from this simple equation are. Take a look for yourself: just hover over a point to see its corresponding Julia set!


Resolution is preset at a value good for seeing lots of details and loading at a reasonable speed, but should you want to change it, controls are ‘E’ to increase it and ‘Q’ to decrease it. To reset to default, press ‘SPACE’.

Mandelbrot Exploration

I finally figured out how to embed programs that I write onto these blog posts! I’m really excited about the way this will expand my ability to describe and explain all sorts of topics in the future. I’ll inaugurate this new ability with an old classic: a program that allows you to explore the Mandelbrot set. I’ve preset it with a pretty good resolution limit that allows for nice viewing as well as not too slow load times, but you can adjust it as you please! Enjoy!

Controls:


UP or W to zoom in

DOWN or S to zoom out

CLICK to center view on the clicked point

E to double resolution (mashing this will slow things down a LOT, so use sparingly)

Q to halve resolution

SPACE to reset everything

Try zooming in on a region near the edge of the set where there are black regions and increasing the resolution. “Resolution” here really means “the number of Mandelbrot iterations run to test if the point diverges or converges”, and the black points are those that were judged to be convergent. So some of these points might be found to be no longer convergent with increasing resolution! Which is why you might notice black regions suddenly filling up with color if you increase the resolution. (Of course, some regions are truly convergent, like the central chunk of the Mandelbrot set around (0,0), so such points’ colors will not depend on the resolution.)

If you’re confused about what this image is, I recommend checking out Numberphile’s video on the Mandelbrot set. (Actually, I recommend it even if you aren’t confused.)

Hopping Midpoints and Mathematical Snowflakes

Let me start this off by saying that if you’re reading this blog and haven’t ever checked out the Youtube channel Numberphile, you need to go there right away and start bingeing their videos. That’s what I’ve been doing for the last few days, and it’s given me tons of cool new puzzles to consider.

Here’s one:

Naturally, after watching this video I wanted to try this out for myself. Here you see the pattern arising beautifully from the randomness:

Serpinski

I urge you to think hard about why the Sierpinski triangle would arise from something as simple as randomly hopping between midpoints. It’s very non-obvious, and although I have a few ideas, I’m still missing a clear intuition.

I also made some visualizations for other shapes. I’ll show some of them, but encourage you to make predictions about what pattern you’d expect to see before scrolling down to see the actual result.

First:

Square

Instead of three points arranged as above, we will start out with four points arranged in a perfect square. Then, as before, we’ll jump from our starting point halfway to one of these four, and will continue this procedure ad infinitum.

What pattern will arise? Do you think that we’ll have “missing regions” where no points can land, like with the triangle?

Scroll down to see the answer…

(…)

(…)

(…)

Square

Okay! So it looks like the whole square gets filled out, with no missing regions. This was pretty surprising to me; given that three points gave rise to a intricate fractal pattern, why wouldn’t four points do the same? What’s special about “3” .

Well, perhaps things will be different if we tweak the positions of the corners slightly? Will any quadrilateral have the same behavior of filling out all the points, or will the blank regions re-arise? Again, make a prediction!

Quadrilaterals

Let’s see:

4 TemplesCross4 Double Temples4 Rolos

Okay, now we see that apparently the square was actually a very special case! Pretty much any quadrilateral we can construct will give us a nested infinity of blank regions, as long as at least one angle is not equal to 90º. Again, this is fascinating and puzzling to me. Why do 90º angles invariably cause the whole region to fill out? I’m not sure.

Let’s move on to a pentagon! Do you think that a regular pentagon will behave more like a triangle or a square?

Pentagon

Take a look…

Pentagon

And naturally, the next question is what about a hexagon?

Hexagon

Hexagon

Notice the difference between the hexagon and all the previous ones! Rather than having small areas of points that are never reached, it appears that suddenly we get lines! Again, I encourage you to try to think about why this might be (what’s so special about 6?) and leave a comment if you have any ideas.

Now, I because curious about what other types of patterns we can generate with simple rules like these. I wondered what would happen if instead of simply jumping to the average of the current point and a randomly chosen point, we built a pattern with some “memory”. For instance, what if we didn’t just look at the current point and the randomly chosen point, but also at the last chosen point? We could then take the middle of the triangle formed by these three points as our new point.

It turns out that the patterns that arise from this are even more beautiful than the previous ones! (In my opinion, of course)

Take a look:

Triangle

Threes Triangle

Square

Threes Square

Pentagon

Threes Pentagon

Hexagon

Threes Hexagon

Heptagon

Threes Heptagon

I’ll stop here, but this is a great example of how beautiful and surprising math can be. I would have never guessed that such intricate fractal patterns would arise from such simple random rules.

A probability puzzle

probpuzzle.jpg

To be totally clear: the question is not assuming that there is ONLY one student whose neighbors both flipped heads, just that there is AT LEAST one such student. You can imagine that the teacher first asks for all students whose neighbors both flipped heads to step forward, then randomly selected one of the students that had stepped forward.

Now, take a minute to think about this before reading on…

It seemed initially obvious to me that the teacher was correct. There are exactly as many possible worlds in which the three students are HTH as there worlds in which they are HHH, right? Knowing how your neighbors’ coins landed shouldn’t give you any information about how your own coin landed, and to think otherwise seems akin to the Gambler’s fallacy.

But in fact, the teacher is wrong! It is in fact more likely that the student flipped tails than heads! Why? Let’s simplify the problem.

Suppose there are just three students standing in a circle (/triangle). There are eight possible ways that their coins might have landed, namely:

HHH
HHT
HTH
HTT
THH
THT
TTH
TTT

Now, the teacher asks all those students whose neighbors both have “H” to step forward, and AT LEAST ONE steps forward. What does this tell us about the possible world we’re in? Well, it rules out all of the worlds in which no student could be surrounded by both ‘H’, namely… TTT, TTH, THT, and HTT. We’re left with the following…

HHH
HHT
HTH
THH

One thing to notice is that we’re left with mostly worlds with lots of heads. The expected total of heads is 2.25, while the expected total of tails is just 0.75. So maybe we should expect that the student is actually more likely to have heads than tails!

But this is wrong. What we want to see is what proportion of those surrounded by heads are heads in each possible world.

HHH: 3/3 have H (100%)
HHT: 0/1 have H (0%)
HTH: 0/1 have H (0%)
THH: 0/1 have H (0%)

Since each of these worlds is equally likely, what we end up with is a 25% chance of 100% heads, and a 75% chance of 0% heads. In other words, our credence in the student having heads should be just 25%!

Now, what about for N students? I wrote a program that does a brute-force calculation of the final answer for any N, and here’s what you get:

N

cr(heads)

~

3

1/4

0.25

4

3/7

0.4286

5

4/9

0.4444

6

13/32

0.4063

7

1213/2970

0.4084

8

6479/15260

0.4209

9

10763/25284

0.4246

10

998993/2329740

0.4257

11

24461/56580

0.4323

12

11567641/26580015

0.4352

13

1122812/2564595

0.4378

14

20767139/47153106

0.4404

15

114861079/259324065

0.4430

16

2557308958/5743282545

0.4453

17

70667521/157922688

0.4475

These numbers are not very pretty, though they appear to be gradually converging (I’d guess to 50%).

Can anybody see any patterns here? Or some simple intuitive way to arrive at these numbers?

 

Solving the common knowledge puzzle

Read this post and give it a try yourself before reading on! Spoilers ahead.

I’ve written up the way that I solved the puzzle, step by step:

1. A looks at B and C and says “I don’t know what my number is.”

We assess what information this gives us by considering in which scenario A would have known what their number was, and ruling it out.

Well, for starters, if A saw two different numbers, then A would consider there to be two logically possible worlds, one in which they are the sum of the two numbers, and another in which they are one of the two that are added together. But if A saw the SAME two numbers, they A would know that they must be the sum of those two (since zero is not a possible value for themselves). What this means is that the fact that A doesn’t know their number tells us with certainty that B ≠ C! Furthermore, since B and C will go through this same line of reasoning themselves, they will also know that B ≠ C. And since all of them know that B and C will go through the same line of reasoning, it becomes common knowledge that B ≠ C.

Good! So after A’s statement, we have added one piece of common knowledge, namely that B ≠ C.

2. B thinks a moment and then says “Me neither.”

Ok, one thing this tells us is that A ≠ C, for the exact same reason as before.

But it also tells us more than this, because B knows that B ≠ C and still doesn’t know. So we just need to think of the scenario in which knowing that B ≠ C (and knowing the values of A and C, of course) would tell B the value that they have. Try to figure it out for yourselves!

The answer is, the scenario is that A = 2C! Imagine that B sees that A is 10 and C is 5. This tells them that they are either 5 or 15. But they know they can’t be 5, because C is five and B ≠ C. So they must be 15! In other words, since they would know their value if A equaled 2C and they don’t know their value, this tells us that A ≠ 2C!

So now we have two more pieces of common knowledge: A ≠ C, and A ≠ 2C. Putting this together with what we knew before, we have a total of three pieces of information:

B ≠ C
A ≠ C
A ≠ 2C

3. C thinks a moment and then says “Me neither.”

By exact analogy with the previous arguments, this tells us that A ≠ B, as well as that A ≠ 2B and B ≠ 2A. (We saw previously that B could conclude from B ≠ C that A ≠ 2C. By the same arguments, C can conclude from C ≠ A that B ≠ 2A. And from C ≠ B, C can conclude that A ≠ 2B.)

There’s one more piece of information that we haven’t taken into account, which is that A ≠ 2C. In which situation does the fact that A ≠ 2C tell C their value? Well, if A = 10 and B = 15, then C is either 5 or 20. But C can’t be 5, because then A would be twice C. So C could conclude that they are 20. Since C doesn’t conclude this, we know that 3A ≠ 2B.

Putting it all together, we know the following:

B ≠ C
A ≠ C
A ≠ 2C
A ≠ 2B
B ≠ 2A
3A ≠ 2B

4. A thinks, and says: “Now I know! My number is 25.”

The question we need to ask ourselves is what the values of B and C must be in order that the above six conditions to allow A to figure out their own value. Pause to think about this before reading on…

 

 

 

Let’s work through how A processes each piece of information:

A could figure out their own value by seeing B = C. But we already know that this isn’t the case.

Since A knows that A ≠ C, A could figure out their value by seeing B = 2C. So that’s a possibility… Except that if B = 2C, then A = B + 2C = 3C. But 25 is not divisible by 3. So this can’t be what they saw.

Since A knows that A ≠ B, A could figure out their value by seeing C = 2B. But again, this doesn’t work, since it would imply that A was divisible by 3, which it is not.

Since A knows that A ≠ 2C, A could figure out their value by seeing B = 3C (e.g. B = 15, C = 5). They would rule out themselves being one component of the sum, and conclude that they are 4C. But 25 is not divisible by 4. So this is not the case.

Since A knows that A ≠ 2B, A could figure out their value by seeing C = 3B (e.g. B = 5, C = 15). By the same reasoning as before, this cannot be the case.

Since B ≠ 2A, A could figure out their value by seeing 3B = 2C (e.g. B = 10, C = 15). They would know that they cannot be just one component of the sum, so they would conclude that they must be B + C, or 2.5 B. Now, is there an integer B such that 25 = 2.5 B? You betcha! B = 10, and C = 15!

We can stop here, since we’ve found a logically consistent world in which A figures out that their own value is 25. Since there can only be one such world (as the problem statement implies that this information is enough to solve the puzzle), we know that this must be what they saw. So we’ve found the answer! (A,B,C) = (25,10,15). But if you’re curious, I’d suggest you go through the rest of the cases and show that no other values of B and C would be consistent with them knowing that their own value is 25.

One thing that’s interesting here is the big role that the number 25 played in this. The fact that 25 was not divisible by 3 but was divisible by 2.5, was crucial. For the same puzzle but a different value that 25, we would have come to a totally different answer!

My challenge to anybody that’s made it this far: Consider the set of all integers that A could have truthfully declared that they knew themselves to be. For some such integers, it won’t be the case that A’s declaration is sufficient for us to conclude what B and C are. Which integers are these?