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”

Nines in Binary

I discovered a cool property of positive integers of the form 10n-1, that is, integers made up of n digits of 9s: they have binary representations that have exactly n digits of trailing 1s. For example, 9,999,999 in decimal is 100110001001011001111111 in binary.

The property is interesting in and of itself, but what is more interesting is the process I went through to discover it. It’s a small-scale example of experimental mathematics: I observed something interesting, experimented to collect more data, developed a hypothesis, and constructed a proof.

Continue reading “Nines in Binary”

How I Taught My Mother Binary Numbers

I introduced my mother to binary numbers a few weeks ago when I showed her my One Hundred Cheerios in Binary poster. It shows the decimal number 100 in binary — 1100100. She’s not an engineer but she’s good with numbers, so I knew she would get it — if only I could find the right way to explain it. Two days ago, I found the right way.

Continue reading “How I Taught My Mother Binary Numbers”

Displaying the Raw Fields of a Floating-Point Number

A double-precision floating-point number is represented internally as 64 bits, divided into three fields: a sign field, an exponent field, and a fraction field. You don’t need to know this to use floating-point numbers, but knowing it can help you understand them. This article shows you how to access those fields in C code, and how to print them — in binary or hex.

Continue reading “Displaying the Raw Fields of a Floating-Point Number”

Converting Floating-Point Numbers to Binary Strings in C

If you want to print a floating-point number in binary using C code, you can’t use printf() — it has no format specifier for it. That’s why I wrote a program to do it, a program I describe in this article.

(If you’re wondering why you’d want to print a floating-point number in binary, I’ll tell you that too.)

Continue reading “Converting Floating-Point Numbers to Binary Strings in C”

Base Conversion in PHP Using BCMath

PHP has a component called BCMath which does arbitrary-precision, decimal arithmetic. I used BCMath in my decimal/binary converter because:

  • Arbitrary-precision lets it operate on very large and very small numbers, numbers that can’t be represented in standard computer word sizes.
  • Decimal arithmetic lets it use the same algorithms I’d use to convert between decimal and binary by hand.

(If you’ve written a conversion routine in standard code, especially one to convert decimal fractions to binary, you’ll see the advantage of the second point.)

This article describes the implementation of my conversion routines with BCMath.

Continue reading “Base Conversion in PHP Using BCMath”

Base Conversion In PHP Using Built-In Functions

The PHP programming language has many built-in functions for converting numbers from one base to another. In fact, it has so many functions that it can be hard to know which to use. Some functions have similar capabilities, and some work with parameters of different types. We’ll sort through the differences in this article, and explain the proper context in which to use each function.

Continue reading “Base Conversion In PHP Using Built-In Functions”

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”