Binary Division

This is the fourth of a four part series on “pencil and paper” binary arithmetic, which I’ve written as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; the third article discusses binary multiplication; this article discusses binary division.

An Example of Binary Division
Example of Binary Division

The pencil-and-paper method of binary division is the same as the pencil-and-paper method of decimal division, except that binary numerals are manipulated instead. As it turns out though, binary division is simpler. There is no need to guess and then check intermediate quotients; they are either 0 are 1, and are easy to determine by sight.

Continue reading “Binary Division”

Binary Multiplication

This is the third of a four part series on “pencil and paper” binary arithmetic, which I’m writing as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; this article discusses binary multiplication.

An Example of Binary Multiplication
Example of Binary Multiplication

The pencil-and-paper method of binary multiplication is just like the pencil-and-paper method of decimal multiplication; the same algorithm applies, except binary numerals are manipulated instead. The way it works out though, binary multiplication is much simpler. The multiplier contains only 0s and 1s, so each multiplication step produces either zeros or a copy of the multiplicand. So binary multiplication is not multiplication at all — it’s just repeated binary addition!

Continue reading “Binary Multiplication”

One Hundred Acorns in Binary

Today is the 100th day of school at my son’s elementary school. I’ve had my binary influence on prior 100th day projects, and this year was to be no different. But alas, his class is not doing one this year. I didn’t want to waste the acorn tops we saved though, so I made my own 100th day project (well not quite — I didn’t glue them):

A Binary Multiplication Problem Expressed With One Hundred Acorn Tops
A Binary Multiplication Problem Expressed With One Hundred Acorn Tops.

Continue reading “One Hundred Acorns in Binary”

Binary Subtraction

This is the second of a four part series on “pencil and paper” binary arithmetic, which I’m writing as a supplement to my binary calculator. The first article discusses binary addition; this article discusses binary subtraction.

An Example of Binary Subtraction
Example of Binary Subtraction

The pencil-and-paper method of binary subtraction is just like the pencil-and-paper method of decimal subtraction you learned in elementary school. Instead of manipulating decimal numerals, however, you manipulate binary numerals, according to a basic set of rules or “facts.”

Continue reading “Binary Subtraction”

How I Taught Third Graders Binary Numbers

Last week I introduced my son’s third grade class to binary numbers. I wanted to build on my prior visit, where I introduced them to the powers of two. By teaching them binary, I showed them that place value is not limited to base ten, and that there is a difference between numbers and numerals.

My presentation was based on base-ten-block-like imagery, since I knew the students were comfortable expressing numbers with base ten blocks. I thought extending the block model to other bases would work well. I think it did.

The Number Twenty-Seven, Broken Into Powers of Two
The Number Twenty-Seven in Tape Flags, Broken Into Powers of Two

Continue reading “How I Taught Third Graders Binary Numbers”

In Search of Decimal/Binary/Hexadecimal Palindromes

Are there any multiple digit hexadecimal number palindromes that are also palindromic in binary and decimal? I have been searching but have not found any.

I started my search with my program that finds multiple-base palindromes. I generated palindromes in binary, and then checked them to see if they were also palindromes in hexadecimal and decimal. I looked for decimal/binary/hexadecimal palindromes up to 16 hex digits long, but did not find any.

To continue my search into bigger numbers, I wrote a program that uses arbitrary-precision integer arithmetic and a more efficient algorithm. Despite being able to search much further, I still have not found any.

In this article, I’ll analyze the size of the palindrome “search space”, explain my improved algorithm, and discuss the state of my search.

Continue reading “In Search of Decimal/Binary/Hexadecimal Palindromes”

Counting Binary/Hexadecimal Palindromes

In my article “Counting Binary and Hexadecimal Palindromes” I derived formulas for counting binary palindromes and hexadecimal palindromes. For each type of palindrome, I derived two pairs of formulas: one pair to count n-digit palindromes, and one pair to count palindromes of n digits or less.

In this article, I will derive similar formulas to count binary/hexadecimal palindromes — multi-base palindromes I’ve shown to have an algorithmically defined structure.

Continue reading “Counting Binary/Hexadecimal Palindromes”

The Structure of Binary/Hexadecimal Palindromes

Binary/hexadecimal palindromes are integers that are palindromic in both binary and hexadecimal. Unlike binary/decimal palindromes, for example, they have a predictable structure. This means they can be generated directly, rather than searched for. So what is their structure?

Certainly they’re made up of the hexadecimal digits that are themselves palindromic in binary: 0, 6, 9, F; for example, F060F16 = 111100000110000011112 and 9F916 = 1001111110012. Each of these four hexadecimal digits maps neatly to a 4-digit binary palindrome, so any hexadecimal palindrome made from them is automatically palindromic in binary.

But there are other binary/hexadecimal palindromes, like 52516 = 101001001012 and 7020716 = 11100000010000001112, that contain hexadecimal digits that are not palindromic in binary. In this case, binary palindromes are produced with combinations of hexadecimal digits. It turns out there are a limited number of valid combinations, and that they’re localized — they span only two hexadecimal digits.

In this article, I’ll analyze binary/hexadecimal palindromes and describe their structure — a structure due to the relationship of the two bases, binary and hexadecimal.

Example Binary/Hexadecimal Palindromes
Example Binary/Hexadecimal Palindromes

Continue reading “The Structure of Binary/Hexadecimal Palindromes”

Counting Binary and Hexadecimal Palindromes

How many nonzero, n-digit, decimal number palindromes are there? These two formulas give the answer:

  • When n is even: 9·10n/2-1
  • When n is odd: 9·10(n+1)/2-1

How many nonzero, decimal number palindromes are there, consisting of n-digits or less? These two formulas give the answer:

  • When n is even: 2(10n/2 – 1)
  • When n is odd: 11·10(n-1)/2 – 2

So for example, there are 900 5-digit decimal palindromes, 9,000 8-digit decimal palindromes, 1,098 decimal palindromes of 5 digits or less, and 19,998 decimal palindromes of 8 digits or less.

In this article, I will derive similar formulas to count binary and hexadecimal number palindromes.

Continue reading “Counting Binary and Hexadecimal Palindromes”

Binary Dates in 2010 and 2011

People have been tweeting about the upcoming dates that look like binary numbers. 10/10/10 seems to be a favorite, both because of its symmetry and because 101010 = 42 in decimal (you know, the answer to the ultimate question of life, the universe, and everything). Here are the nine dates in 2010, interpreted as binary numbers, and with their decimal equivalents:

Continue reading “Binary Dates in 2010 and 2011”