Collaborative Mathematics: Challenge 16

My colleague Jason Ermer at Collaborative Mathematics is back from summer hiatus and has published Challenge 16 on his website: http://www.collaborativemathematics.org/challenge16.html

Multiplication and Animaniacs

One of my guilty pleasures in the 1990s, when I was far too old to be watching children’s cartoons, was the fantastic show “Animaniacs.” In the clip below, Yakko Warner describes how to multiply 47 and 83.

Lessons from teaching gifted elementary school students (Part 5d)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

A bright young student of mine noticed that multiplication is repeated addition:

$x \cdot y = x + x + x \dots + x$ ,

Also, exponentiation is repeated addition:

$x \uparrow y = x^y = x \cdot x \cdot x \dots \cdot x$ ,

The notation $x \uparrow y$ is unorthodox, but it leads to the natural extensions

$x \upuparrows y = x \uparrow x \uparrow x \dots \uparrow x$ ,

$x \uparrow^3 y = x \upuparrows x \upuparrows x \dots \upuparrows x$ ,

and so. I’ll refer the interested reader to Wikipedia and Mathworld (and references therein) for more information about Knuth’s up-arrow notation. As we saw in yesterday’s post, these numbers get very, very large… and very, very quickly.

When I was in elementary school myself, I remember reading in the 1980 Guiness Book of World Records about Graham’s number, which was reported to be the largest number ever used in a serious mathematical proof. Obviously, it’s not the largest number — there is no such thing — but the largest number that actually had some known usefulness. And this number is only expressible using Knuth’s up-arrow notation. (Again, see Wikipedia and Mathworld for details.)

From Mathworld, here’s a description of the problem that Graham’s number solves:

Stated colloquially, [consider] every possible committee from some number of people $n$ and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find $N$ , the smallest $n$ that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees.

In 1971, Graham and Fairchild proved that there is a solution $N$ , and that $N \le F(F(F(F(F(F(F(12)))))))$ , where

$F(n) = 2 \uparrow^n 3$ .

For context, $2 \uparrow^4 3$ is absolutely enormous. In yesterday’s post, I showed that $2 \uparrow^3 = 65,536$ . Therefore,

$2 \uparrow^4 3 = 2 \uparrow^3 (2 \uparrow^3 2)$

$= 2 \uparrow^3 65,536$

$= 2 \upuparrows 2 \upuparrows 2 \upuparrows \dots \upuparrows 2$ ,

repeated 65,536 times.

That’s just $2 \uparrow^4 3$ . Now try to imagine $F(12) = 2 \uparrow^{12} 3$ . That’s a lot of arrows.

Now try to imagine $F(F(12)) = 2 \uparrow^{F(12)} 3$ , which is even more arrows.

Now try to imagine $F(F(F(F(F(F(F(12)))))))$ . I bet you can’t. (I sure can’t.)

Graham and Fairchild also helpfully showed that $N \ge 6$ . So somewhere between 6 and Graham’s number lies the true value of $N$ .

A postscript: according to Wikipedia, things have improved somewhat since 1971. The best currently known bounds for $N$ are

$13 \le N \le 2 \uparrow^3 6$ .

Lessons from teaching gifted elementary school students (Part 5c)

A bright young student of mine noticed that multiplication is repeated addition:

$x \cdot y = x + x + x \dots + x$ ,

Also, exponentiation is repeated addition:

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

So, my student asked, why can’t we define an operation that’s repeated exponentiation? Like all good explorers, my student claimed naming rights for this new operation and called it $x \hbox{~playa~} y$ :

$x \hbox{~playa~} y = x^{x^{x^{\dots}}}$

For example,

$4 \hbox{~playa~} 3 = 4^{4^4} = 4^{256} \approx 1.34 \times 10^{154}$

Even with small numbers for $x$ and $y$ , $x \hbox{~playa~} y$ gets very large.

Unfortunately for my student, someone came up with this notion already, and it’s called Knuth’s up-arrow notation. I’ll give some description here and refer the interested reader to Wikipedia and Mathworld (and references therein) for more information. Surprisingly, this notion has only become commonplace since 1976 — within my own lifetime.

Let’s define $x \uparrow y$ to be ordinary exponentiation:

$x \uparrow y = x \cdot x \cdot x \dots \cdot x$ .

Let’s now define $x \upuparrows y$ to be the up-arrow operation repeated $y$ times:

$x \upuparrows y = x \uparrow x \uparrow x \dots \uparrow x$ .

In this expression, the order of operations is taken to be right to left.

Numbers constructed by $\upuparrows$ get very, very big and very, very quickly. For example:

$2 \upuparrows 2 = 2 \uparrow 2 = 2^2 = 4$ .

Next,

$2 \upuparrows 3 = 2 \uparrow (2 \uparrow 2)$

$= 2 \uparrow (2^2)$

$= 2 \uparrow 4$

$= 2^4$

$= 16$

Next,

$2 \upuparrows 4 = 2 \uparrow (2 \uparrow (2 \uparrow 2))$

$= 2 \uparrow 16$

$= 2^{16}$

$= 65,536$

Next,

$2 \upuparrows 5 = 2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow 2)))$

$= 2 \uparrow 65,536$

$= 2^{65,536}$

$\approx 2.0035 \times 10^{19,728}$

Next,

$2 \upuparrows 6 = 2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow (2 \uparrow 2))))$

$= 2 \uparrow 2^{65,536}$

$= 2^{2^{65,536}}$

$\approx 10^{6.031 \times 10^{19,727}}$

We see that $2 \upuparrows 6$ is already far larger than a googolplex (or $10^{10^{100}}$ ), which is often (and erroneously) held as the gold standard for very large numbers.

I’ll refer the interested reader to a previous post in this series for a description of how logarithms can be used to write something like $2^{65,536}$ in ordinary scientific notation.

Knuth’s up-arrow notation can be further generalized:

$x \uparrow^3 y = x \upuparrows x \upuparrows x \dots \upuparrows x$ ,

repeated $y$ times. The numbers $x \uparrow^4 y$ , $x \uparrow^5 y$ , etc., are defined similarly.

These numbers truly become large quickly. For example,

$2 \uparrow^3 2 = 2 \upuparrows 2 = 4$ , from above.

Next,

$2 \uparrow^3 3 = 2 \upuparrows (2 \upuparrows 2)$

$= 2 \upuparrows 4$

$= 65,536$ , from above

Next,

$2 \uparrow^3 4 = 2 \upuparrows (2 \upuparrows (2 \upuparrows 2))$

$= 2 \upuparrows 65,536$

$= 2 \uparrow 2 \uparrow 2 \uparrow \dots \uparrow 2$ ,

where there are 65,536 repeated 2’s on this last line. It’d be nearly impossible to write this number in scientific notation, and we’ve only reached $2 \uparrow^3 4$ .

Lessons from teaching gifted elementary school students (Part 5b)

Here’s a question I once received (though I probably changed the exact wording somewhat):

Exponentiation is to multiplication as multiplication is to addition. In other words,

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

$x \cdot y = x + x + x \dots + x$ ,

where the operation is repeated $y$ times.

So, multiplication is to addition as addition is to what?

My kneejerk answer was that there was no answer… while exponents can be thought of as repeated multiplication and multiplication can be thought of as repeated addition, addition can’t be thought of as some other thing being repeated. But it took me a few minutes before I could develop of proof that could be understood by my bright young questioner.

Suppose $y = 1$ . Then the expressions above become

$x^1 = x$

and

$x \cdot 1 = x$

However, we know full well that

$x + 1 \ne x$ .

Therefore, there can’t be an operation analogous to addition as addition is to multiplication or as multiplication is to exponentiation.

Lessons from teaching gifted elementary school students (Part 5a)

Here’s a question I once received (though I probably changed the exact wording somewhat):

Exponentiation is to multiplication as multiplication is to addition. In other words,

$x^y = x \cdot x \cdot x \dots \cdot x$ ,

$x \cdot y = x + x + x \dots + x$ ,

where the operation is repeated $y$ times.

So, multiplication is to addition as addition is to what?

Which then naturally led to my student’s next question, which I was dreading:

Can you prove that?

This led to another kneejerk reaction, but I kept this one quiet: “Aw, nuts.”

I suggested that $x + y$ can be thought of as starting with $x$ and then adding $1$ repeatedly $y$ times, but my bright student wouldn’t hear of this. After all, in the repeated renderings of $x^y$ and $x \cdot y$ , there’s no notion of starting with a number and then doing something with a different number $y$ times.

So I had to put my thinking cap on, and I’m embarrassed to say that it took me a good five minutes before I came up with a logically correct answer that, in my opinion, could be understand by the bright young student who asked the question.

I’ll reveal that answer in tomorrow’s post. In the meantime, I’ll leave a thought bubble if you’d like to think about it on your own.

Siri: What is 0 divided by 0?

In case you missed it, the programming geniuses behind the iPhone’s Siri came up with a startling response to the question, “What is 0 divided by 0?”

Lessons from teaching gifted elementary school students: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on various lessons I’ve learned while trying to answer the questions posed by gifted elementary school students.

Part 1: A surprising pattern in some consecutive perfect squares.

Part 2: Calculating 2 to a very large exponent.

Part 3a: Calculating 2 to an even larger exponent.

Part 3b: An analysis of just how large this number actually is.

Part 4a: The chance of winning at BINGO in only four turns.

Part 4b: Pedagogical thoughts on one step of the calculation.

Part 4c: A complicated follow-up question.

Too many significant digits: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my short series on what happens when too many significant digits are reported.

Part 1: An analysis of the report of this Nike app:

Part 2: Links to resources that discuss how many significant digits should be reported.

Second-Grade Teacher Uses NBA Games To Teach Basic Math To His Students

I love this: http://www.thepostgame.com/blog/dish/201501/second-grade-teacher-uses-nba-games-teach-basic-math-students