Powers Of Two In The Josephus Problem

Pradeep Mutalik of The New York Times recently blogged about a puzzle that is an instance of the Josephus Problem. The problem, restated simply, is this: there are n people standing in a circle, of which you are one. Someone outside the circle goes around clockwise and repeatedly eliminates every other person in the circle, until one person — the winner — remains. Where should you stand so you become the winner?

Here’s an example with 13 participants:

Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)
Alternating Elimination with 13 people, order of elimination shown in red (winner is person 11)

As Pradeep and his readers point out, there’s no need to work through the elimination process — a simple formula will give the answer. This formula, you won’t be surprised to hear, has connections to the powers of two and binary numbers. I will discuss my favorite solution, one based on the powers of two.

Continue reading “Powers Of Two In The Josephus Problem”

Elements of Binary in the NCAA Basketball Tournament

If you’re a sports fan, you think of basketball when you see this:

Diagram of the NCAA Basketball Tournament
Basketball or Binary?

If you’re like me, you also think of powers of two, binary trees, logarithms, laws of exponents, geometric sequences, geometric series, and Bernoulli trials — in short, the elements of binary numbers, binary code, and binary logic.

I hope you’re thinking: “wow — all that math stuff I hated actually has a practical use!”

Continue reading “Elements of Binary in the NCAA Basketball Tournament”

Nonstandard Names for The Powers of Two

Now that you know how the powers of two are named, lets look at other, nonstandard ways to name them. You will see these names on the internet as well as in books. We will not use them on this site other than in this article, and we only discuss them here to make you aware of their use. As a by-product of this discussion, you may gain some insight into the nature of the powers of two. But beware — you may become confused as well!

Continue reading “Nonstandard Names for The Powers of Two”

How to Check If a Number Is a Power of Two

How can you tell if a number is a power of two?

That’s easy if it’s in the form 2n, where n is an integer. For example, 212, 20, and 2-37 are powers of two. That is by definition. But what about arbitrary positive numbers like 16,392, 524,288, or 0.00390625? Are they powers of two? Here’s how to tell — if they can be simplified to the form 2n, they are; if they can’t, they’re not.

Continue reading “How to Check If a Number Is a Power of Two”

Composing Powers of Two Using The Laws of Exponents

Powers of two can be combined, under the laws of exponents, to create other powers of two. Under these rules, you can multiply powers of two, divide powers of two, or raise a power of two to a power and still get another power of two. You can combine these rules to create complicated expressions, expressions that result in a single power of two. For example,

\mbox{\footnotesize{\displaystyle {{\left(\frac{2^4 \cdot 2^3}{2^5}\right)}^3 = \: 2^6}}} .

The laws of exponents apply generally to any base; two is no different. But since we’re interested in powers of two, we’ll couch them in terms of powers of two. Once we explain the laws in this way, you’ll understand the math behind the example above.

Continue reading “Composing Powers of Two Using The Laws of Exponents”