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.

Binary/Hexadecimal Palindromes of n Hexadecimal Digits

To derive the formula to count binary/hexadecimal palindromes, look at the tables in my article “The Structure of Binary/Hexadecimal Palindromes”. There’s a table of palindromes for each starting hexadecimal digit: 1, 3, 5, 7, 9, and F. Each table lists the binary/hexadecimal palindromes of one to five hex digits, for each starting digit. If you count the palindromes in the tables — and continue the pattern beyond five digits — this is what you’ll get:

This pattern continues forever, based on the structure of the palindromes.

(Notice we’re not counting 0 as a palindrome — if you want to, add 1 to the formulas we derive below.)

There are two different count sequences: one of interleaved nonnegative powers of two, and one of interleaved nonnegative powers of four. As we learned when counting n-digit binary palindromes, the sequence of interleaved nonnegative powers of two is captured by these two formulas:

• When n is even: 2^n/2-1
• When n is odd: 2^(n+1)/2-1

Those two formulas apply to the starting hex digits 1 and 3, counting the number of n hex digit binary/hexadecimal palindromes for each.

You can use similar formulas to generate the sequence of interleaved nonnegative powers of four:

• When n is even: 4^n/2-1 = 2^2·(n/2-1) = 2^n-2
• When n is odd: 4^(n+1)/2-1 = 2^{2·((n+1)/2-1)} = 2^n-1

(It should not be surprising that these expressions simplify to powers of two — powers of four are powers of two.)

Those two formulas apply to the starting hex digits 5, 7, 9, and F, counting the number of n hex digit binary/hexadecimal palindromes for each.

Combining the Formulas

The formulas above count the number of n hex digit binary/hexadecimal palindromes by starting hex digit. We can combine them into one pair of formulas that counts all n hex digit binary/hexadecimal palindromes, by adding two copies of the first pair of formulas to four copies of the second pair:

• When n is even: 2·2^n/2-1 + 4·2^n-2 = 2^n/2 + 2ⁿ
• When n is odd: 2·2^(n+1)/2-1 + 4·2^n-1 = 2^(n+1)/2 + 2ⁿ⁺¹

Binary/Hexadecimal Palindromes of n Hexadecimal Digits or Less

To compute the total number of binary/hexadecimal palindromes of n hex digits or less, we need to add together the count of palindromes for each number of digits, 1 through n. We could create a series using the pair of formulas above, but it’s easier to start from scratch: we’ll create a series for each starting digit, and then add them together.

The count of palindromes for each starting digit, from 1 to n digits, is an interleaved sequence — either of nonnegative powers of two or nonnegative powers of four. If you separate those sequences and add their terms — creating series — you’ll have these building blocks, which I’ll use to derive a formula:

• The sum of the first m nonnegative powers of two: = 2^m – 1 .
• The sum of the first m nonnegative powers of four: = (4^m – 1)/3 .

We can use these expressions for each of the interleaved series, adding them together to get expressions that count palindromes of n digits or less by starting digit. We can then combine those expressions to get one pair of formulas — one that counts all palindromes of n digits or less.

Total Palindromes for Each of the Starting Digits 1 and 3

• The number of digits n is even

  The sum consists of two identical series of n/2 terms each:

  = 2^n/2 – 1.

  Added together, they are 2(2^n/2 – 1).

• The number of digits n is odd

  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = 2^(n-1)/2 – 1.

  Added together, they are 2·(2^(n-1)/2 – 1).

  The extra term is 2^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(2^(n-1)/2 – 1) + 2^(n-1)/2, which simplifies to 3·2^(n-1)/2 – 2.

Total Palindromes for Each of the Starting Digits 5, 7, 9, and F

• The number of digits n is even

  The sum consists of two identical series of n/2 terms each:

  = (4^n/2 – 1)/3.

  Added together, they are 2·(4^n/2 – 1)/3.

• The number of digits n is odd

  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = (4^(n-1)/2 – 1)/3.

  Added together, they are 2·(4^(n-1)/2 – 1)/3.

  The extra term is 4^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(4^(n-1)/2 – 1)/3 + 4^(n-1)/2, which simplifies to (5·4^(n-1)/2 – 2)/3.

Total Palindromes for All Digits

To get the total palindromes of n digits or less, we add two copies of the “1/3” pair of formulas to four copies of the “5/7/9/F” pair of formulas:

• The number of digits n is even

  2(2(2^n/2 – 1)) + 4(2(4^n/2 – 1)/3) = 4(2^n/2 – 1) + 8(2ⁿ – 1)/3

• The number of digits n is odd

  2(3·2^(n-1)/2 – 2) + 4((5·4^(n-1)/2 – 2)/3) = 2(3·2^(n-1)/2 – 2) + 4(5·2^n-1 – 2)/3

Summary

Here is a summary of the binary/hexadecimal palindrome counting formulas:

Here’s a table listing the values of these formulas for n = 1 to 16:

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Counting Binary/Hexadecimal Palindromes

I will show you how to install MPIR in Microsoft Visual C++ as a static, 32-bit library. I will also show you how to install the optional C++ interface — also as a static, 32-bit library. I will provide two example C programs that call the GMP integer and floating-point functions, and two equivalent C++ programs — programs that use the same GMP functions, only indirectly through the C++ interface.

1. Download What You Need

To install MPIR and run it under Visual C++ as I have, you’ll need four things:

• Microsoft Visual C++ (I use Visual C++ 2008 Express Edition).
• A file archiver (I use 7-Zip).
• The MPIR source code and Visual C++ solution (I use mpir-1.3.1.tar.gz, which is based on GMP version 4.2.1).
• The Yasm assembler (I use yasm-0.8.0-win32.exe).

(I won’t describe how to install Visual C++ or 7-zip.)

2. Prepare to Build MPIR

MPIR must be built with Visual C++; to prepare for that, do the following:

1. From mpir-1.3.1.tar.gz, use your file archiver to extract mpir-1.3.1.tar; from mpir-1.3.1.tar, extract folder mpir-1.3.1.
2. Copy \mpir-1.3.1\build.vc9\yasm.rules to the Visual C++ project defaults directory (mine is C:\Program Files\Microsoft Visual Studio 9.0\VC\VCProjectDefaults\).
3. Rename file yasm-0.8.0-win32.exe to yasm.exe.
4. Move yasm.exe to the Visual C++ binary directory (mine is C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\).

3. Build MPIR

Here’s how to build MPIR as a static Win32 library:

1. Open the MPIR Visual C++ solution \mpir-1.3.1\build.vc9\mpir.sln.

   You get the following error message if you are using Visual Studio Express:

   The project consists entirely of configurations that require support for platforms which are not installed on this machine. The project cannot be loaded.

   

   This message is referring to the 64-bit projects, which we won’t be using anyway. Hit ‘Enter’ to ignore (do this eight times — one for each 64-bit project in the solution.)

2. Right click on “Solution ‘mpir’ (14 projects)”, select “Properties” and then click on “Configuration Properties” and then click on “Configuration Manager”. In the box labeled “Active solution configuration” select “Release” and then click “Close” and then click “OK”.

   

3. Build the version of the library you want by right clicking on the project name and selecting “Build” (I built lib_mpir_p4, labeled in the readme file as the “MPIR library using Pentium IV assembler”).

   

   A successful build of lib_mpir_p4, which should take less than two minutes, gives this message:

   Build: 6 succeeded, 0 failed, 0 up-to-date, 0 skipped

   (You can ignore the compiler warning messages.)

4. Optional: for C++ interface only: Build the C++ interface by right clicking on project lib_mpir_cxx and selecting “Build” (again, ignore the compiler warning messages).

4. Install the MPIR Library in Visual C++

To install MPIR in Visual C++, you need to copy three files from the MPIR build directory into corresponding Visual C++ directories:

• Copy files mpir.lib and mpir.pdb from

  \mpir-1.3.1\build.vc9\lib_mpir_p4\Win32\Release\

  to the Visual C++ library directory

  C:\Program Files\Microsoft Visual Studio 9.0\VC\lib\.

• Copy \mpir-1.3.1\build.vc9\lib_mpir_p4\Win32\Release\mpir.h

  to the Visual C++ include directory

  C:\Program Files\Microsoft Visual Studio 9.0\VC\include\.

Optional: for C++ interface only: To install the library for the C++ interface, you need to copy three files from the MPIR build directory into corresponding Visual C++ directories:

• Copy files mpirxx.lib and mpirxx.pdb from

  \mpir-1.3.1\build.vc9\lib_mpir_cxx\Win32\Release\

  to the Visual C++ library directory

  C:\Program Files\Microsoft Visual Studio 9.0\VC\lib\.

• Copy \mpir-1.3.1\build.vc9\lib_mpir_cxx\Win32\Release\mpirxx.h

  to the Visual C++ include directory

  C:\Program Files\Microsoft Visual Studio 9.0\VC\include\.

(Unless you want to build another library, you can delete the folder mpir-1.3.1 at this point, and perhaps file mpir-1.3.1.tar.gz too. You might also want to wait until you run the test programs below.)

5. Configure Your Visual C++ Project to Use MPIR

• Open an existing Visual C++ solution or create a new one.
• Right click on the project name and select “Properties”. Then click “Configuration Properties”, then click “Linker”, and then click “Command Line”. In the “Additional options” box, enter “mpir.lib” and click OK.

  

  Optional: for C++ interface only: Also add “mpirxx.lib” to the command line:

  

• Right click on the project name and select “Properties”. Then click “Configuration Properties”, then click “C/C++”, and then click “Code Generation”. In the “Runtime Library” pulldown menu, select “Multi-threaded (/MT)” and click OK. This takes care of the linker warning message you would otherwise get:

  LINK : warning LNK4098: defaultlib ‘LIBCMT’ conflicts with use of other libs; use /NODEFAULTLIB:library

Writing a C/C++ Program that Uses the Standard GMP Interface

To access the GMP functions through their standard interface from your C/C++ source code, you must include the file “mpir.h”, as follows:

#include <mpir.h>

(A vanilla GMP program would have the line “#include <gmp.h>” instead; other than this, there are no source code differences.)

The MPIR GMP functions are documented in the MPIR manual, which is essentially the same document as the GMP manual.

Here are two C programs I wrote that you can use to test out the standard GMP interface: one uses some integer functions, and one uses some floating-point functions:

C Program Using GMP Integers Through the Standard Interface

#include <stdio.h>
#include <mpir.h>

int main (int argc, char *argv[])
{
 mpz_t aBigPO2;

 mpz_init(aBigPO2);

 mpz_set_ui(aBigPO2, 1073741824); //2^30
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^60
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^120
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^240
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^480
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^960
 mpz_mul(aBigPO2,aBigPO2,aBigPO2); //2^1920

 mpz_out_str(stdout,10,aBigPO2);
 printf ("\n");

 mpz_clear(aBigPO2);
}

This prints out 2¹⁹²⁰:

949711451807891414054698636958849699906924706346851167428009563305851
662866960338751057874083211050161729488483879798993810787765480587192
741530384819193300769874625884321977783469748956377553448566093328992
717820774610081821193616932757859144579109671494034728110890670954570
186561270637912025593911079819522904974136715161890547150302121514577
299257466073410681074505560366912534455201581754427662731068044605805
987604257959314070588213630129796572870132647963130222671409082294912
848599974253399700073940596408585364978789157781640247045138282505908
97948604589281308443672576

(I verified this with PARI/GP).

C Program Using GMP Floating-Point Numbers Through the Standard Interface

#include <stdio.h>
#include <mpir.h>

int main (int argc, char *argv[])
{
 mpf_t aSmallPO2;

 mpf_init2(aSmallPO2,4449); //Set precision to 4449 bits

 mpf_set_d (aSmallPO2,0.000000000931322574615478515625); //2^-30
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-60
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-120
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-240
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-480
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-960
 mpf_mul(aSmallPO2,aSmallPO2,aSmallPO2); //2^-1920

 mpf_out_str (stdout,10,0,aSmallPO2);
 printf ("\n");

 mpf_clear(aSmallPO2);
}

In case you are wondering, 4449 bits of precision is the minimum needed to print all the digits of 2^-1920, which is:

0.10529513970757941370610747782095090628278032322332406685248932058897
4872190707039601594120403123249585501787935873212314961661043417067942
8278180446530326422046737097860094653249850843254396524641486587776526
8438334467392843186701182578047022952222095279213542847547625013806063
5939813263124389547821599195698069457805581599831394945162148920227813
5870110642683804987806409062559492005002245124038200955046244238057665
8723954500997837640072880232154236046343680085877727078528072722123195
3662151119904110195371481974425580486352182740921723969072266817056082
2079226689557687055189455076290288097855736909213224995450090355633626
2479360506670537902070512869428970881638135729845035256195565406246915
5908284846389916152190520040559448133294815988479693870277001617833335
8035796655478612315835426745796222381146595433091161056422873002023624
5605524128583533967685249775398427450933606825973311143113749366383842
6445031772775456966272872821230559421629513369329254203751128364614621
2033824114891508165551708120643223406118819602960923135752402206346995
9597949051896076865883172740955991670305216873490456538967283758977304
0869715545540580641662604687640672610266478149937775606620121327969356
0952412990814675362368055269333370619407233848969981813715084977716048
9153948872988676360548263714707910434915092735830288717124858521856367
588043212890625e-577

(I verified this with PARI/GP).

Writing a C++ Program that Uses the GMP C++ Interface

(To use the C++ interface you will have had to have followed the build steps labeled ‘optional’ above.)

To access the GMP functions through their C++ interface, you must include the file “mpirxx.h”, as follows:

#include <mpirxx.h>

(A vanilla GMP program would have the line “#include <gmpxx.h>” instead.)

Also, your source code will require this additional line, if you want to remove the compiler warnings due to mpirxx.h:

#pragma warning(disable: 4800)

Without this, you will get about a dozen warning messages like this:

c:\program files\microsoft visual studio 9.0\vc\include\mpirxx.h(1610) : warning C4800: ‘int’ : forcing value to bool ‘true’ or ‘false’ (performance warning)

The MPIR GMP C++ interface is documented in the MPIR manual (and the GMP manual).

Here are two C++ programs I wrote that you can use to test out the GMP C++ interface: they are the equivalent of the two C programs above, except they’re expressed much more naturally (as to be expected in a C++ program):

C++ Program Using GMP Integers Through the C++ Interface

#include <iostream>
using namespace std;

#pragma warning(disable: 4800)
#include <mpirxx.h>
#pragma warning(default: 4800)

int main (int argc, char *argv[])
{
  mpz_class aBigPO2;

  aBigPO2 = 1073741824; //2^30
  aBigPO2*=aBigPO2; //2^60
  aBigPO2*=aBigPO2; //2^120
  aBigPO2*=aBigPO2; //2^240
  aBigPO2*=aBigPO2; //2^480
  aBigPO2*=aBigPO2; //2^960
  aBigPO2*=aBigPO2; //2^1920

  cout << aBigPO2 << endl;
}

(This gives the same output as the C program above.)

C++ Program Using GMP Floating-Point Numbers Through the C++ Interface

#include <iostream>
#include <iomanip>
using namespace std;

#pragma warning(disable: 4800)
#include <mpirxx.h>
#pragma warning(default: 4800)

int main (int argc, char *argv[])
{
  mpf_class aSmallPO2(0,4449); //Init to 0, precision 4449 bits

  aSmallPO2 = 0.000000000931322574615478515625; //2^-30
  aSmallPO2*=aSmallPO2; //2^-60
  aSmallPO2*=aSmallPO2; //2^-120
  aSmallPO2*=aSmallPO2; //2^-240
  aSmallPO2*=aSmallPO2; //2^-480
  aSmallPO2*=aSmallPO2; //2^-960
  aSmallPO2*=aSmallPO2; //2^-1920

  cout << setprecision (1343) << aSmallPO2 << endl;
}

The value of 1343 to setprecision is the precision in decimal digits.

The output differs slightly from it’s corresponding C program (the number is shifted one place and has the corresponding exponent to match):

1.05295139707579413706107477820950906282780323223324066852489320588974
8721907070396015941204031232495855017879358732123149616610434170679428
2781804465303264220467370978600946532498508432543965246414865877765268
4383344673928431867011825780470229522220952792135428475476250138060635
9398132631243895478215991956980694578055815998313949451621489202278135
8701106426838049878064090625594920050022451240382009550462442380576658
7239545009978376400728802321542360463436800858777270785280727221231953
6621511199041101953714819744255804863521827409217239690722668170560822
0792266895576870551894550762902880978557369092132249954500903556336262
4793605066705379020705128694289708816381357298450352561955654062469155
9082848463899161521905200405594481332948159884796938702770016178333358
0357966554786123158354267457962223811465954330911610564228730020236245
6055241285835339676852497753984274509336068259733111431137493663838426
4450317727754569662728728212305594216295133693292542037511283646146212
0338241148915081655517081206432234061188196029609231357524022063469959
5979490518960768658831727409559916703052168734904565389672837589773040
8697155455405806416626046876406726102664781499377756066201213279693560
9524129908146753623680552693333706194072338489699818137150849777160489
1539488729886763605482637147079104349150927358302887171248585218563675
88043212890625e-578

Besides the much cleaner syntax of the C++ programs, the underlying GMP functions — “*_init”, “*_clear”, “*_mul”, etc. — are hidden in the C++ classes.

For Further Information

This article is my distillation of the MPIR readme file for a specific build scenario — please refer to \mpir-1.3.1\build.vc9\readme.txt for details on other builds.

Acknowledgement

Thanks to Brian Gladman for answering my questions and for suggesting I explore the C++ interface.

Feedback

If you try these instructions, let me know how it works out (and if you have suggestions to improve them, please let me know that too).

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

How to Install and Run GMP on Windows Using MPIR

Installing

• Download the PARI/GP self-installing binary distribution for Windows.

  As of this writing, the current stable version is Pari-2-3-4.exe. (There’s no need to download or install the optional packages — at least I don’t need them).

• Double click on the installer file to install (install all components).

Changing Settings

You can set gp default settings by editing the gp customization file, “\PARI\.gprc”. For example, I have edited mine as follows:

• Changed the command prompt from the default timestamp format (prompt = "(%H:%M) gp > ") to ‘?’ (prompt = "? ").
• Added a line (format = "f") that makes all decimals print without scientific notation.

Running

Here are some basic things you should know about running gp:

• Starting gp. Launch gp from the PARI folder under the Windows start menu.
• Setting variables. You can assign constants or results of calculations to variables; for example, n=8.
• Reusing prior calculations. The results of calculations are stored in a history array: %1 is the result of the first calculation, %2 is the result of the second calculation, etc. You can use these as variables in subsequent expressions.
• Changing the default precision. The default precision of printed decimal values is 28 significant digits; this can be changed with the ‘\p’ command. For example, ‘\p 50’ changes the print precision to 50 digits (PARI may set its internal precision higher than what you ask for; it must respect boundaries dictated by its implementation).
• Printing decimals instead of fractions. To force gp to print decimals instead of fractions, make sure a decimal point appears in the expression; for example, 2.^-2
• Executing previous commands. Previous commands can be accessed with the up arrow and down arrow keys.
• Copying and pasting. This is cumbersome, but can be done by right-clicking on the top of the command window and selecting ‘edit’. For copy, select ‘mark’, highlight the desired text in the command window and then hit enter. For paste, select ‘paste’.
• Logging your session. Type ‘\l’ to record your session — all commands and output — to the default PARI log file (\PARI\examples\pari.log). Type ‘\l’ again to stop recording.
• Exiting gp. Type ‘quit’ to exit gp.

Running PARI/GP Calculator

Examples

See my article “Exploring Binary Numbers With PARI/GP Calculator” for example gp calculations.

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

How to Install and Run PARI/GP Calculator on Windows

Certainly they’re made up of the hexadecimal digits that are themselves palindromic in binary: 0, 6, 9, F; for example, F060F₁₆ = 11110000011000001111₂ and 9F9₁₆ = 100111111001₂. 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 525₁₆ = 10100100101₂ and 70207₁₆ = 1110000001000000111₂, 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

Inferring the Structure of Binary/Hexadecimal Palindromes

Before determining the structure of binary/hexadecimal palindromes analytically, let’s look at more examples. I listed the first 124 (nonzero) binary/hexadecimal palindromes — that is, those palindromes consisting of five hexadecimal digits or less — using my C program that finds multi-base palindromes. I noticed that each palindrome starts (and thus ends) with one of six hexadecimal digits: 1, 3, 5, 7, 9, F. I also noticed that, depending on the starting digit, only certain middle digits appear:

• Palindromes starting with 1: only 0 and 1 appear as middle digits.
• Palindromes starting with 3: only 0 and 3 appear as middle digits.
• Palindromes starting with 5 or 7: only 0, 2, 5, and 7 appear as middle digits.
• Palindromes starting with 9 or F: only 0, 6, 9, and F appear as middle digits.

Within each of the four groups of palindromes, the middle digits alternate in each digit position, in the order listed above.

Here is the output of my program, segmented by starting digit (the highlighted digits in the hexadecimal palindromes are the digits “inserted” into them to take them from n digits to n+1 digits):

Palindromes starting with hex ‘1’:

Palindromes starting with ‘3’:

Palindromes starting with hex ‘5’:

Palindromes starting with hex ‘7’:

Palindromes starting with hex ‘9’:

Palindromes starting with hex ‘F’:

You can see that binary palindromes starting with hex digits 1, 3, 5, and 7 are not multiples of four bits. This is because leading zeros do not count. Each of those four hex digits — when used as a starting digit — requires less than four bits. In this case, it’s important to remember that hex digits are formed in groups of four bits, from right to left.

Starting Digits

We’ve seen empirically that a nonzero binary/hexadecimal palindrome starts with the hexadecimal digit 1, 3, 5, 7, 9, or F — now it’s time to prove it.

First, observe that the starting hex digit must be odd: an even hex digit ends with a 0 when written in binary, and palindromes can’t start with 0. This leaves eight starting digits as candidates: 1, 3, 5, 7, 9, B, D, F.

Let’s classify our palindromes into two categories: single hex digit and multiple hex digit. A single hex digit palindrome is a single hex digit that is palindromic in binary: 1, 3, 5, 7, 9, and F are the only choices (1₁₆ = 1₂, 3₁₆ = 11₂, 5₁₆ = 101₂, 7₁₆ = 111₂, 9₁₆ = 1001₂, F₁₆ = 1111₂). A multiple hex digit palindrome as a whole is palindromic in binary, but individually, each hex digit may not be — and in fact, will not be — palindromic in binary.

Let’s analyze multiple hex digit palindromes by classifying them into two categories, depending on whether their ending hex digit has a binary equivalent that starts with a 1 or 0:

• Binary equivalent starts with 1.

  The hexadecimal palindrome will have an associated binary palindrome that is a multiple of four bits. This means that each hex digit must stand alone as a binary palindrome: 9 and F are the only choices for the starting digit. There are two 2-digit palindromes that start with 9 and F: 99₁₆ = 10011001₂ and FF₁₆ = 11111111₂; these will serve as “bookends” for all palindromes of 3 digits or more.

• Binary equivalent starts with 0.

  The hexadecimal palindrome will have an associated binary palindrome that is not a multiple of four bits. This means that each hex digit does not stand alone as a binary palindrome.

  The best way to show which starting digits are allowed in this case is to try all four candidates as 2-digit palindromes: 11₁₆ = 10001₂, 33₁₆ = 110011₂, 55₁₆ = 1010101₂, and 77₁₆ = 1110111₂. All are binary palindromes, so 1, 3, 5, 7 are the valid starting digits.

Middle Digits

We’ve seen empirically what the middle digits of multiple digit binary/hexadecimal palindromes are, and that they follow a pattern — now I’ll show why.

Definition. I’ll say a number is a leading-zero palindrome or is leading-zero palindromic if it is palindromic with zero or more leading zeros.

Middle Digits for Starting Digits 9, F

Palindromes starting with 9 or F are straightforward to analyze, so I’ll start with them. Each middle hex digit must stand alone as a leading-zero binary palindrome, so 0, 6, 9, and F are the choices.

The structure of these palindromes is easy to describe. The n+1 hex digit palindromes can be created from the n hex digit palindromes by inserting the digits 0, 6, 9, or F. When n is odd, one n+1 digit palindrome is spawned from each n digit palindrome, by replicating the middle hex digit (which will be 0, 6, 9 or F). When n is even, four n+1 digit palindromes are spawned from each n digit palindrome, by inserting the digits 0, 6, 9, and F in turn.

Middle Digits for Starting Digits 1, 3, 5, 7

The analysis of palindromes starting with 1, 3, 5, or 7 is based on the number of leading zeros in the binary representation of the ending hex digit; let’s define the three cases:

• 1 leading zero: 5 (0101) and 7 (0111).
• 2 leading zeros: 3 (0011).
• 3 leading zeros: 1 (0001).

Recall how palindrome generation works: each inserted hex digit takes an n digit palindrome and turns it into an n+1 digit palindrome. To ensure the result remains a binary palindrome, the inserted hex digit must maintain a binary palindrome around the “center”. Here’s how it’s done:

• The binary representation of the inserted hex digit must have the same number of leading zeros as the binary representation of the hex digit to its right.
• The binary representation of the inserted hex digit must be palindromic without the leading zeros.

In other words, the inserted leading zeros mirror the existing leading zeros, and the rest of the hex digit — which is between the sets of zeros — stands alone as a binary palindrome.

(There’s an alternate way to think of this: the inserted hex digit, with the one, two, or three leading binary zeros in the hex digit to its right, is a leading zero palindrome. The left side of this palindrome replaces the leading zeros used from the right.)

So what are the allowable middle digits? Hex digits 0-7 are the candidates, since they’re the only 4-bit hex digits that have leading zeros in their binary representations. But after you strip away the required number of leading zeros, only 0, 1, 2, 3, 5, and 7 stand alone as binary palindromes:

• 1 leading zero: 0 (000), 2 (010), 5 (101), 7 (111).
• 2 leading zeros: 0 (00) or 3 (11).
• 3 leading zeros: 0 (0) or 1 (1).

The insertion of middle digits can continue indefinitely, since the number of binary leading zeros in each group is the same for each digit. Any middle digit in each group can be adjacent to any other. The number of leading zeros in the ending digit is the number of leading zeros maintained throughout.

Example

This diagram shows an example of binary/hexadecimal palindrome generation:

Example Binary/Hexadecimal Palindrome Generation

Summary

In summary, the (nonzero) binary/hexadecimal palindromes are

• The single digit hexadecimal palindromes 1, 3, 5, 7, 9, and F.
• All hexadecimal palindromes that start and end with 1 and have only 0s and 1s between.
• All hexadecimal palindromes that start and end with 3 and have only 0s and 3s between.
• All hexadecimal palindromes that start and end with 5 or 7 and have only 0s, 2s, 5s, and 7s between.
• All hexadecimal palindromes that start and end with 9 or F and have only 0s, 6s, 9s, and Fs between.

(And now that we know their structure we can count them — see my article “Counting Binary/Hexadecimal Palindromes”.)

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

The Structure of Binary/Hexadecimal Palindromes

• When n is even: 9·10^n/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(10^n/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.

Binary Palindromes

Number palindromes have a simple structure: n-digit palindromes are related to n-1 digit palindromes. You can think of generating palindromes as an iterative process, where you start with single-digit palindromes and work your way through palindromes of an increasing number of digits. Here’s an example of the process, using binary numbers:

1. From the only (nonzero) one-digit palindrome, 1, make the two-digit palindrome 11.
2. From 11, make the two three-digit palindromes 101 and 111.
3. From 101, make 1001; from 111, make 1111.
4. From 1001, make 10001 and 10101; from 1111, make 11011 and 11111.
5. From 10001, make 100001; from 10101, make 101101; from 11011, make 110011; from 11111 make 111111.
6. …

From each odd-length palindrome, you can generate one even-length palindrome; you have to replicate the middle digit in order to keep it palindromic. From each even-length palindrome, you can generate two odd-length palindromes, by inserting a 0 or 1 in the middle.

This table illustrates the structure better — it shows all 1 through 8 digit binary palindromes:

Counting Binary Palindromes

As typical with things binary, there is a pattern in the palindromes involving powers of two. In this case, it’s easy to see why: each set of odd-length palindromes is double the size of the preceding set of even-length palindromes, and each set of even-length palindromes is the same size as the preceding set of odd-length palindromes. These two formulas capture this relationship, giving the number of n-digit binary palindromes:

• When n is even: 2^n/2-1
• When n is odd: 2^(n+1)/2-1

For n = 1 to 8, you can verify these formulas match the counts in the table: 1, 1, 2, 2, 4, 4, 8, 8.

(The formula can be stated in one expression as , which is the base 2 version of , the formula stated here. I rewrote it into two parts to remove the slightly cumbersome “floor” function, and to be consistent with the formulas below.)

Number of Binary Palindromes of n Digits or Less

You can further derive a formula for the total number of palindromes of n digits or less, by adding the terms 1, 1, 2, 2, 4, 4, 8, 8, … . Recognizing this sequence as two interleaved sequences of 1, 2, 4, 8, … — that is, sequences of nonnegative powers of two — the derivation of the formula is straightforward.

Here’s the formula to express the sum of the first m nonnegative powers of two:

= 2^m – 1

We can use this expression for each of the interleaved series, and then add them together. There are two cases:

• The number of digits n is even

  The sum consists of two identical series of n/2 terms each:

  = 2^n/2 – 1.

  Added together, they are 2(2^n/2 – 1).

• The number of digits n is odd

  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = 2^(n-1)/2 – 1.

  Added together, they are 2(2^(n-1)/2 – 1).

  The extra term is 2^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(2^(n-1)/2 – 1) + 2^(n-1)/2, which simplifies to 3·2^(n-1)/2 – 2.

For n = 1 to 8, you can verify these formulas match the total counts in the table: 1, 2, 4, 6, 10, 14, 22, 30.

Hexadecimal Palindromes

Using a similar analysis, here are the two formulas to count n-digit hexadecimal palindromes:

• When n is even: 15·16^n/2-1
• When n is odd: 15·16^(n+1)/2-1

For n = 1 to 8, the value of these formulas is 15, 15, 240, 240, 3840, 3840, 61440, 61440.

(The formula can also be stated in one expression as .)

To count the number of hexadecimal palindromes of n digits or less, we can add series just as we did for binary palindromes. If you factor out 15 from each term in the sequence above, you’re left with this sequence: 1, 1, 16, 16, 256, 256, 4096, 4096. Those are interleaved sequences of nonnegative powers of sixteen.

Here’s the formula to express the sum of the first m nonnegative powers of sixteen:

= (16^m – 1)/15

We can use this expression for each of the interleaved sequences, and then add them together. There are two cases:

• The number of digits n is even

  The sum consists of two identical series of n/2 terms each:

  = 16^n/2 – 1.

  Added together, they are 2(16^n/2 – 1).

• The number of digits n is odd

  The sum consists of two identical series of (n-1)/2 terms each, plus an extra term. Each series looks like this:

  = 16^(n-1)/2 – 1.

  Added together, they are 2(16^(n-1)/2 – 1).

  The extra term is 15·16^(n-1)/2, what would have been the next term in one of the series. Adding this to the two series we get 2(16^(n-1)/2 – 1) + 15·16^(n-1)/2, which simplifies to 17·16^(n-1)/2 – 2.

For n = 1 to 8, these formulas return these values: 15, 30, 270, 510, 4350, 8190, 69630, 131070.

Trying These Formulas in PARI/GP

In this section, I’ll demonstrate the formulas for counting binary palindromes, using PARI/GP.

Print the number of 1-digit to 20-digit binary palindromes, using the “floor” form of the expression:

? for (i=1,20,print(2^(floor((i-1)/2))))
1
1
2
2
4
4
8
8
16
16
32
32
64
64
128
128
256
256
512
512

Print the number of 1-digit to 20-digit binary palindromes, using the even and odd case palindrome counting expressions:

? for(i=1,20,if(i%2==1,print(2^((i+1)/2-1)),print(2^(i/2-1))))
1
1
2
2
4
4
8
8
16
16
32
32
64
64
128
128
256
256
512
512

Print the total number of binary palindromes of n digits or less, for n = 1 to 20:

? for(i=1,20,if(i%2==1,print(3*2^((i-1)/2)-2),print(2*(2^(i/2)-1))))
1
2
4
6
10
14
22
30
46
62
94
126
190
254
382
510
766
1022
1534
2046

Summary

Here is a summary of the binary palindrome counting formulas:

Here is a summary of the hexadecimal palindrome counting formulas:

Discussion

These formulas can be extended to any base, like octal. (You can see the pattern they follow, although that in itself is not a proof they hold for all bases.)

In my article “Finding Numbers That Are Palindromic In Multiple Bases” I showed how to generate palindromes by iterating through a counter. The analysis of palindromes in this article suggests another algorithm: generating n-digit palindromes from n-1 digit palindromes. (It’s probably not a better way though, at least not for large n, because the required storage space grows exponentially.)

What About Zero?

The number 0 is defined to be a palindrome, although you could make an argument against it. No palindrome can start with zero, yet 0 is a palindrome. In any case, it is not counted in the formulas above, simply because it makes the derivations easier. To count zero, add one to each formula.

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Counting Binary and Hexadecimal Palindromes

• Part 1 shows that the powers of five mod 2^m cycle with period 2^m-2, m ≥ 2, starting at 5⁰.
• Part 2 shows that the powers of five mod 10^m cycle with the same period as the powers of five mod 2^m, starting at 5^m.

The highlight of my proof is in part 1, where I derive a formula to show that the period, or order, of 5 mod 2^m is 2^m-2. While it is in general not possible to derive a formula for the order of a number, I’ll show it is possible for the powers of five mod 2^m — due to a hidden, binary structure I’ve uncovered.

To understand the proof, you’ll need to know some algebra and the basics of modular arithmetic.

Part 1: Period mod 2^m is 2^m-2

Part 1 shows that the order of 5 mod 2^m is 2^m-2. I break it into three steps, showing that

• The order of 5 mod 2^m is a power of two. This constrains the values for the order so that only expressions of the form 5²ⁿ – 1 need be considered.
• 5²ⁿ – 1 can be factored to isolate its factors of two. This is my key insight, made possible by recursive factoring of differences of squares.
• 5²ⁿ – 1 is divisible by 2ⁿ⁺². This shows that the order of 5 mod 2ⁿ⁺² is 2ⁿ, or equivalently, that the order of 5 mod 2^m is 2^m-2.

In addition, I show that the powers of five mod 2^m cycle starting at 5⁰; this is important because it will show that the cycle mod 10^m always starts after the cycle mod 2^m.

The Order of 5 mod 2^m is a Power of Two

The order of a mod b is related to , so let’s start there. is Euler’s phi function, the number of positive integers less than or equal to b that are relatively prime to b (for b a power of two, this is just the count of the odd numbers less than b). We want to compute , which we can do with this simple formula: . For p=2, this gives = 2^m-1.

The order of a mod b must divide , so the order of the powers of five mod 2^m must divide , or 2^m-1. In other words, the order must be a power of two — a power of two less than or equal to 2^m-1 to be specific — because the divisors of a positive power of two are all the positive powers of two less than or equal to it.

Let 2^e represent any of the candidates for the order of 5 mod 2^m: 1, 2, 4, 8, … , 2^m-2, 2^m-1. By definition, if the order is 2^e, , or equivalently, . That is, 5^2e – 1 is divisible by 2^m. Now all we have to do is figure out which e makes this true.

5²ⁿ – 1 Can Be Factored to Isolate its Factors of Two

You can factor 5²ⁿ – 1 into (5^2n/2 + 1)(5^2n/2 – 1), since it is a difference of two squares. You can factor 5^2n/2 – 1 similarly, into (5^2n/4 + 1)(5^2n/4 – 1). You can do this n times, since log₂(2ⁿ) = n. Here’s an example:

1. 5¹⁶ – 1 = (5⁸ + 1)(5⁸ – 1)
2. 5⁸ – 1 = (5⁴ + 1)(5⁴ – 1)
3. 5⁴ – 1 = (5² + 1)(5² – 1)
4. 5² – 1 = (5¹ + 1)(5¹ – 1)
5. 5¹ – 1 = 4

Recursive Factoring of Differences of Squares

Combining these recursively you get 5¹⁶ – 1 = 4(5¹ + 1)(5² + 1)(5⁴ + 1)(5⁸ + 1).

This generalizes to 5²ⁿ – 1 = 4(5¹ + 1)(5² + 1)(5⁴ + 1)···(5^2n/2 + 1).

There is a factor of two in each 5^2f + 1, as I’ll show in the next section.

5²ⁿ – 1 is divisible by 2ⁿ⁺²

The factor of four in the factored expression shows there are at least two factors of two in 5²ⁿ – 1. There is also exactly one factor of two in each of the factors 5^2f + 1. I’ll show it in two steps:

• 5^2f + 1 is divisible by 2.

  Every positive power of five ends in 5, so it is odd. This means 5^2f + 1 is even, meaning it’s divisible by 2.

• 5^2f + 1 is not divisible by any power of two greater than 2.

  To show this, it suffices to show that 5^2f + 1 is not divisible by 4. If it’s not divisible by 4, it’s not divisible by any higher power of two (because the divisors of a positive power of two are all positive powers of two less than or equal to it). So if 2² is not a factor, 2^s, s > 1, is not a factor.

  Let’s show 5^2f + 1 is not divisible by 4 by breaking it in two cases:

  • 5²⁰ + 1. 5¹ + 1 = 6, which obviously is not divisible by 4.
  • 5^2f + 1, f ≥ 1. 5^2f ends in 25, so 5^2f + 1 ends in 26. An integer is divisible by 4 if and only if its last two digits are divisible by 4. Since 26 is not divisible by 4, neither is 5^2f + 1.

So the example expression 4(5¹ + 1)(5² + 1)(5⁴ + 1)(5⁸ + 1) has a factor of 2⁶: 2² times four factors of 2.

This generalizes to show that 5²ⁿ – 1 is divisible by 2ⁿ⁺². Recasting this from the perspective of the power of five to the modulus, let’s substitute m-2 for n. This gives the equivalent statement 5^2m-2 – 1 is divisible by 2^m. Just to be explicit, this implies that no 5^2e, e < 2^m-2, is divisible by 2^m. So, the candidate power of two we were seeking is 2^m-2, the order of 5 mod 2^m.

The Powers of Five Mod 2^m Cycle Starting at 5⁰

Let the period p = 2^m-2. As we proved above, . We also know, trivially, that . The difference between the exponents p and 0 is p, showing a full cycle occurs starting at 5⁰.

Part 2: Period mod 10^m is 2^m-2

Part 2 shows, using the definition of modular arithmetic, the laws of exponents, and simple algebra, that the powers of five mod 10^m have the same period as the powers of five mod 2^m. It’s broken into two halves, showing that

• The period mod 2^m is a cycle mod 10^m.
• The cycle mod 10^m is the period mod 2^m.

The first half only shows that the period mod 2^m is a multiple of the period mod 10^m. The second half shows that the period mod 10^m is in fact the same as the period mod 2^m.

I’ll use the variable p for the period mod 2^m, as above, to simplify the notation in the proof that follows.

The period mod 2^m is a cycle mod 10^m

For i ≥ 0, what we’ve shown is that . That is, powers of five with exponents a period apart are congruent mod 2^m.

Congruence mod 2^m means that 5^i+p – 5ⁱ is a multiple of 2^m; that is, 5^i+p – 5ⁱ = n·2^m, for some nonnegative integer n.

Factoring out 5ⁱ we get 5ⁱ(5^p – 1) = n·2^m. When i≥m, n is a multiple of 5^m, so n = n’·5^m.

Substituting n’·5^m for n we get 5ⁱ(5^p – 1) = n’·5^m2^m = n’·10^m.

Reversing the process above, we can show congruence mod 10^m:

5ⁱ(5^p – 1) = 5^i+p – 5ⁱ = n’·10^m.

This shows that for i≥m, , so p is a cycle mod 10^m.

The cycle mod 10^m is the period mod 2^m

We’ve shown that p is a cycle mod 10^m, but not that p is the period mod 10^m. In other words, it’s possible the period mod 10^m is less than p — we have to show it isn’t.

For i ≥ m, we’ve shown that . Using the argument above, congruence mod 10^m means that:

5^i+p – 5ⁱ = n·10^m = n·5^m2^m = (n·5^m)2^m.

This shows that for i≥m, , so p is the period mod 2^m and mod 10^m.

Empirical Evidence

This section is not part of the proof, but it shows some PARI/GP calculations that support it.

Compute the order of 5 mod 2 through 5 mod 2¹⁶ (you can see they’re powers of two):

? for(m=1,16,print(znorder(Mod(5,2^m))))
1
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384

Show the factors in 5¹⁶ – 1:

? factor(5^16-1)
%1 =
[2 6]
[3 1]
[13 1]
[17 1]
[313 1]
[11489 1]

? factor(4*(5^1+1)*(5^2+1)*(5^4+1)*(5^8+1))
%2 =
[2 6]
[3 1]
[13 1]
[17 1]
[313 1]
[11489 1]

? factor((5^1+1))
%3 =
[2 1]
[3 1]

? factor((5^2+1))
%4 =
[2 1]
[13 1]

? factor((5^4+1))
%5 =
[2 1]
[313 1]

? factor((5^8+1))
%6 =
[2 1]
[17 1]
[11489 1]

Show the factors of two in 5ⁿ – 1, n = 1 to 32 (you can see how the nested cycles correspond to the powers of two):

? for(i=1,32,print("5^",i,"-1 has factor 2^",factor(5^i-1)[1,2]))

5^1-1 has factor 2^2
5^2-1 has factor 2^3
5^3-1 has factor 2^2
5^4-1 has factor 2^4
5^5-1 has factor 2^2
5^6-1 has factor 2^3
5^7-1 has factor 2^2
5^8-1 has factor 2^5
5^9-1 has factor 2^2
5^10-1 has factor 2^3
5^11-1 has factor 2^2
5^12-1 has factor 2^4
5^13-1 has factor 2^2
5^14-1 has factor 2^3
5^15-1 has factor 2^2
5^16-1 has factor 2^6
5^17-1 has factor 2^2
5^18-1 has factor 2^3
5^19-1 has factor 2^2
5^20-1 has factor 2^4
5^21-1 has factor 2^2
5^22-1 has factor 2^3
5^23-1 has factor 2^2
5^24-1 has factor 2^5
5^25-1 has factor 2^2
5^26-1 has factor 2^3
5^27-1 has factor 2^2
5^28-1 has factor 2^4
5^29-1 has factor 2^2
5^30-1 has factor 2^3
5^31-1 has factor 2^2
5^32-1 has factor 2^7

(The pattern of the powers of two is reminiscent of the representation of powers of two in a binary counter.)

Discussion

Part 2 of the proof is identical to part 2 of the proof in my article “Cycle Length of Powers of Two Mod Powers of Ten”, except that 5 and 2 are interchanged. Part 1 is quite different though. I could not use the same approach, since powers of two beyond four don’t have primitive roots.

Coming up with an alternate approach took some time. I had the elements of it early on: knowing that the order must be a power of two, knowing how to factor differences of squares, and knowing that each factor was even. But I was missing the piece that let me show each factor had exactly one factor of two — until I realized I could apply the divisibility by four test.

The binary structure of powers of a number computed mod powers of two make this approach possible (it should work for powers of any odd number, although it may be more difficult to show the factors of two).

Summary

To prove the period formula for the positive powers of five mod powers of ten, I first proved it for mod powers of two. I showed that the period must be a power of two, and derived an expression that showed which power of two. I then showed that the period mod powers of two and mod powers of ten must be the same, after a certain starting point.

I’ve previously shown a connection between the positive powers of five and negative powers of two; now I’ve shown a connection between the positive powers of five and the positive powers of two.

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Cycle Length of Powers of Five Mod Powers of Ten

Here they are in dd/mm/yy format:

2011

The same days also look like binary in 2011:

Here they are in dd/mm/yy format:

And in case you were wondering, 2010 = 11111011010 in binary, and 2011 = 11111011011 in binary.

(If this blog existed in 2001 — if blogs existed in 2001 period — I would have made tables for those dates as well.)

Palindromes

Considering dates as numbers leads you to wonder which are number palindromes. Numbers written with leading zeros are not palindromes, so numbers ending with zeros are not palindromes either. This means no dates in 2010 are palindromic. In 2011 however, there are palindromic dates. There are several consisting of all 1s, like 1/1/11, but those are not interesting. That leaves two palindromic dates made up of both 0s and 1s:

• January 10th, 2011, in mm/dd/yy format: 1/10/11.
• October 1st, 2011, in dd/mm/yy format: 1/10/11.

Both are the same binary number: 11011 (27 decimal).

Binary Times

People have also been tweeting about binary times. There are binary times every day, but they’ll seem more significant on binary days. There are 12, not including seconds and duplicates for AM/PM: 1:00, 1:01, 1:10, 1:11, 10:00, 10:01, 10:10, 10:11, 11:00, 11:01, 11:10, 11:11. (I’ll leave it as an exercise to compute these as decimal values.)

Now having thrown time into the mix, we can consider some new palindromes. For example, 1/1/10 (mm/dd/yy) at 1:11 AM is 1110111. Have a toast for me!

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Binary Dates in 2010 and 2011

Cycles in the Ending Digits of the Powers of Five

I will show you why these cycles exist, how they are expressed mathematically, and how to visualize them.

(This article is the companion article to “Patterns in the Last Digits of the Positive Powers of Two”. It describes the digit patterns in the negative powers of two, indirectly, since positive powers of five look like negative powers of two.)

Cycles in the Last One to Four Digits

You can use modular arithmetic to show the repeating digit cycles of the positive powers of five. You can find the last m digits of a positive power by computing its common residue mod 10^m. You can find the last m digits of a sequence of powers by computing them incrementally, mod 10^m. The cycle restarts when you get a result you’ve already seen.

Last Digit

Starting with 5, the last digit repeats in a cycle of period one: 5. You show it with incremental calculations mod 10:

1. 
2. 
3. …

In other words, every positive power of five ends in 5.

Last Two Digits

Starting with 5², the last two digits repeat in a cycle of period one: 25. You show it with incremental calculations mod 10²:

1. 
2. 
3. 
4. …

Last Three Digits

Starting with 5³, the last three digits repeat in a cycle of period two: 125, 625. You show it with incremental calculations mod 10³:

1. 
2. 
3. 
4. 
5. 
6. …

Last Four Digits

Starting with 5⁴, the last four digits repeat in a cycle of period four: 0625, 3125, 5625, 8125. You show it with incremental calculations mod 10⁴:

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. …

Whenever the residue is less than m digits, it is implicitly padded out with leading zeros. For example, the last 4 digits of 5⁸ = 390625 are 0625.

Cycles in the Last m Digits

If you continue this process, you’ll see that the period doubles for each additional ending digit; I did the calculations through ten ending digits:

This table implies that the ending m digits of the positive powers of five cycle with period 2^m-2, m ≥ 2, starting at 5^m. (The proof is here.)

Powers of five with exponents that are congruent mod 2^m-2 are themselves congruent mod 10^m. That is, 5ⁱ and 5^i+(2m-2)·k, i ≥ m, k ≥ 0, end with the same m digits.

Visualizing the Nesting of Cycles

The cycles in m digit, m-1 digit, m-2 digit, …, 1-digit endings can be viewed as nested, even though their starting points are staggered. You just have shift the starting points of the lesser digit cycles to make them coincide. For example, each copy of the length 4 cycle of four digit endings has within it two copies of the length 2 cycle of three digit endings; each copy of the length 2 cycle of three digit endings has within it 2 copies of the length 1 cycle of two digit endings.

This diagram shows the nesting by shading every other occurrence of a cycle (the millions place is fully shaded, because only one cycle of the last seven digits is shown):

Nested 1-7 Digit Ending Patterns from 5⁷ to 5³⁸

Not surprisingly, the nested powers of two in this pattern make it look similar to the pattern in consecutive binary integers.

Binary Tree

Another way to show the nesting of powers of two is with a perfect binary tree. Here is a tree showing the ending 1-5 digits:

Binary Tree Showing Nested 1-5 Digit Ending Patterns (Digits)

Each level contains the ending digits for a given cycle, from the last digit (the root, or first level) to the eight 5 digit endings (the leaves, or fifth level). Starting with the second level, each m digit ending is the suffix of two m+1 digit endings.

Here’s the same tree, except labeled with the smallest power of five corresponding to the ending digits:

Binary Tree Showing Nested 1-5 Digit Ending Patterns (Powers)

Each level from level 2 down includes the endings for 5^m through 5^(m+2m-2-1).

Notice two interesting things that become apparent with the binary tree representations:

• The starting digits of each pair of children, for m ≥ 3, differ by 5. For example, 3125 and 8125 on level 4 (digits 3 and 8).
• The exponents of each pair of children, for m ≥ 3, differ by 2^m-3. For example, 5⁵ and 5⁷ on level 4.

Exploring Ending Digits with PARI/GP

You can use PARI/GP to explore the cycles in the ending digits; here are two examples:

• Print the first 20 positive powers of five:

  ? for(i=1,20,print("5^",i,": ",5^i))
  5^1: 5
  5^2: 25
  5^3: 125
  5^4: 625
  5^5: 3125
  5^6: 15625
  5^7: 78125
  5^8: 390625
  5^9: 1953125
  5^10: 9765625
  5^11: 48828125
  5^12: 244140625
  5^13: 1220703125
  5^14: 6103515625
  5^15: 30517578125
  5^16: 152587890625
  5^17: 762939453125
  5^18: 3814697265625
  5^19: 19073486328125
  5^20: 95367431640625
  

• Show the cycle in the last m (in this case 5) digits:

  ? m=5; for(i=1,2^(m-2)+m,print("5^",i," mod 10^",m": ",5^i%10^m))
  5^1 mod 10^5: 5
  5^2 mod 10^5: 25
  5^3 mod 10^5: 125
  5^4 mod 10^5: 625
  5^5 mod 10^5: 3125
  5^6 mod 10^5: 15625
  5^7 mod 10^5: 78125
  5^8 mod 10^5: 90625
  5^9 mod 10^5: 53125
  5^10 mod 10^5: 65625
  5^11 mod 10^5: 28125
  5^12 mod 10^5: 40625
  5^13 mod 10^5: 3125
  

  (The leading 0 of 3125 is not printed.)

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Patterns in the Last Digits of the Positive Powers of Five

Powers of Two and Powers of Five that Look Alike

This relationship is not coincidence; it’s a by-product of how fractions are represented as decimals. I’ll show you simple algebra that proves it, as well as algebra that proves similar properties — in products involving negative powers.

Positive Powers of Five in Negative Powers of Two

A negative power of two in decimal form looks like a positive power of five, except that it has a decimal point and possibly some leading zeros. Here are some examples, the first eight pairs of positive powers of five and negative powers of two:

The powers that are paired have exponents that are additive inverses of each other. It’s easy to show this relationship holds for all such pairs of powers. A negative power of two is a number of the form 2ⁿ, n and integer less than 0, or equivalently, a number of the form 2^-n, n > 0. By the laws of exponents, 2^-n = 1/2ⁿ = (1/2)ⁿ = (5/10)ⁿ = 5ⁿ/10ⁿ. Written as a decimal, 5ⁿ/10ⁿ looks like a positive power of five, except that it’s a fraction with n decimal places.

A different transformation gives another way to look at this: 2^-n = 1/2ⁿ = (1/2)ⁿ = (0.5)ⁿ. If you were to multiply this out by hand, you would ignore the decimal point, multiply all the factors of five, and then place the decimal point when you were done. You’d end up with a positive power of five, but preceded with a decimal point and zero or more leading 0s — to pad it out to n decimal places.

Positive Powers of Two in Negative Powers of Five

Not surprisingly, a similar relationship exists in reverse; that is, between the positive powers of two and the negative powers of five. This makes sense, given the role of the numbers two and five in the decimal system.

A negative power of five in decimal form looks like a positive power of two, except that it has a decimal point and possibly some leading zeros. Here are some examples, the first eight pairs of positive powers of two and negative powers of five:

Again, the powers that are paired have exponents that are additive inverses of each other. Using a similar transformation as above, we can show this relationship holds for all such pairs of powers: 5^-n = 1/5ⁿ = (1/5)ⁿ = (2/10)ⁿ = 2ⁿ/10ⁿ. Written as a decimal, 2ⁿ/10ⁿ looks like a positive power of two, except that it’s a fraction with n decimal places.

There’s also an alternate way to view this: 5^-n = 1/5ⁿ = (1/5)ⁿ = (0.2)ⁿ. As above, think of it as multiplying the factors to get a power of two and then prefixing a decimal point and leading zeros.

Products of Negative Powers of Two and Positive Powers of Five

Because a negative power of two looks like a positive power of five, multiplying it by a positive power of five makes it look like yet another positive power of five. The resulting power of five has an exponent that is the sum of the absolute values of the exponents of the multiplied powers. For example: 2^-3·5⁴ = 78.125, which looks like 5⁷ = 78125; 2^-7·5³ = 0.9765625, which looks like 5¹⁰ = 9765625.

Algebraically, the multiplication is expressed as 2^-t·5^f, with t, f > 0. The result looks like 5^(t+f); here’s why: 2^-t = 5^t/10^t, so 2^-t·5^f = 5^(t+f)/10^t. This expression describes a positive power of five, only shifted right t decimal places.

You can think of these as looking like negative powers of two as well. The product 2^-t·5^f can be written equivalently as 2^-t·5^f·(2^-f·2^f) = 2^-(t+f)·10^f, which is 2^-(t+f) shifted left f decimal places.

Products of Negative Powers of Five and Positive Powers of Two

Similarly, the product of a negative power of five and a positive power of two looks like a positive power of two. For example, 5^-3·2³ = 0.064, which looks like 2⁶ = 64, and 5^-4·2¹² = 6.5536, which looks like 2¹⁶ = 65536.

Algebraically, the multiplication is expressed as 5^-f·2^t, with f, t > 0. The result looks like 2^(f+t); here’s why: 5^-f = 2^f/10^f, so 5^-f·2^t = 2^(f+t)/10^f. This expression describes a positive power of two, only shifted right f decimal places.

You can think of these as looking like negative powers of five as well. The product 5^-f·2^t can be written equivalently as 5^-f·2^t·(5^-t·5^t) = 5^-(f+t)·10^t, which is 5^-(f+t) shifted left t decimal places.

Products of Negative Powers of Two and Negative Powers of Five

A negative power of two times a negative power of five results in a string of digits that looks like either a positive power of five or a positive power of two, depending on which exponent is smaller. For example, 2^-4·5^-2 = 0.0025, which looks like a positive power of five, and 2^-2·5^-4 = 0.0004, which looks like a positive power of two.

Algebraically, the multiplication is expressed as 2^-t·5^-f, with t, f > 0, and f ≠ t. There are two cases:

• f < t: the result looks like 5^(t-f), with t decimal places. Here’s why:

  Recall from above that 2^-t = 5^t/10^t and that 5^-f = 2^f/10^f. This gives 2^-t·5^-f = (5^t/10^t)(2^f/10^f) = (5^t·2^f)/10^(t+f). Now factor out 10^f from the numerator, which we can do since f < t: (5^t·2^f)/10^(t+f) = (10^f·5^(t-f))/10^(t+f) = 5^(t-f)/10^t.

• t < f: the result looks like 2^(f-t), with f decimal places. Here’s why:

  Starting from (5^t·2^f)/10^(t+f), factor out 10^t from the numerator, which we can do since t < f: (5^t·2^f)/10^(t+f) = (10^t·2^(f-t))/10^(t+f) = 2^(f-t)/10^f.

(If you allow f = t, the answer would be 2⁰ = 5⁰ = 1, a nonnegative power, with f = t decimal places.)

Discussion

I came up with the algebra for the multiplication cases after I played around with some numbers in PARI/GP. I noticed a pattern, and then sought to state it mathematically.

The patterns hold for quotients of powers as well, since divisions can be converted to multiplications by inverting exponents.

Some Practical Uses

If you know the positive powers of five, or if you learn them, you will recognize negative powers of two more readily — similarly for the positive powers of two and negative powers of five.

If you wanted to print a table of negative powers of two or negative powers of five using a computer program, you could do so easily, just by using integers: convert the positive powers to strings, and then prefix each with a decimal point and the appropriate number of leading zeros.

References

• learner.org article “Fractions to Decimals”.

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Seeing Powers of Five in Powers of Two and Vice Versa

• Part 1 shows that the powers of two mod 5^m cycle with period 4·5^m-1, starting at 2⁰.
• Part 2 shows that the powers of two mod 10^m cycle with the same period as the powers of two mod 5^m, starting at 2^m.

To understand the proof, you’ll need to know some elementary number theory.

Part 1: Period mod 5^m is 4·5^m-1

The main goal of part 1 is to show that two is a primitive root mod powers of five, meaning that the order of 2 mod 5^m is the value of Euler’s phi function for 5^m. I break this into three steps, showing that

• = 4·5^m-1, where is Euler’s phi function (also known as Euler’s totient function).
• 2 is a primitive root mod 5.
• 2 is a primitive root mod 5^m.

In addition, I show that the powers of two mod 5^m cycle starting at 2⁰; this is important because it will show that the cycle mod 10^m always starts after the cycle mod 5^m.

= 4·5^m-1

is the number of positive integers less than or equal to n that are relatively prime to n. For a power of a prime number p, we can use this formula to compute it: . For p=5, this gives = 4·5^m-1.

2 is a Primitive Root Mod 5

To prove this, we just have to show that the order (also known as multiplicative order) of 2 mod 5 is equal to .

= 4, by the formula above. The order of 2 mod 5 — the smallest exponent a such that — is four, as shown by the following sequence of four calculations:

Thus, 2 is a primitive root mod 5.

2 is a Primitive Root Mod 5^m

To show that 2 is a primitive root mod all positive powers of 5, we can use this result from page 26 of “A Course in Computational Algebraic Number Theory” by Henri Cohen:

“…to find a primitive root modulo p^a for p an odd prime and a ≥ 2, proceed as follows: first compute g a primitive root modulo p …, then compute g₁ = g^p-1 mod p². If g₁ ≠ 1, g is a primitive root modulo p^a for every a…” .

In our case g = 2 and p = 5. We’ve already shown 2 to be a primitive root mod 5, so now all we need to show is that , which is trivial: .

So, 2 is a primitive root mod 5^m, which means that the order of 2 mod 5^m is . This proves that the powers of two mod 5^m cycle with period 4·5^m-1.

The Powers of Two Mod 5^m Cycle Starting at 2⁰

Let the period p = 4·5^m-1. , since 2 is a primitive root mod powers of 5 (Euler’s theorem applies). We also know, trivially, that . The difference between the exponents p and 0 is p, showing a full cycle occurs starting at 2⁰.

Part 2: Period mod 10^m is 4·5^m-1

Part 2 shows, using the definition of modular arithmetic, the laws of exponents, and simple algebra, that the powers of two mod 10^m have the same period as the powers of two mod 5^m. It’s broken into two halves, showing that

• The period mod 5^m is a cycle mod 10^m.
• The cycle mod 10^m is the period mod 5^m.

The first half only shows that the period mod 5^m is a multiple of the period mod 10^m. The second half shows that the period mod 10^m is in fact the same as the period mod 5^m.

I’ll use the variable p for the period mod 5^m, as above, to simplify the notation in the proof that follows.

The period mod 5^m is a cycle mod 10^m

For i ≥ 0, what we’ve shown is that . That is, powers of two with exponents a period apart are congruent mod 5^m.

Congruence mod 5^m means that 2^i+p – 2ⁱ is a multiple of 5^m; that is, 2^i+p – 2ⁱ = n·5^m, for some nonnegative integer n.

Factoring out 2ⁱ we get 2ⁱ(2^p – 1) = n·5^m. When i≥m, n is a multiple of 2^m, so n = n’·2^m.

Substituting n’·2^m for n we get 2ⁱ(2^p – 1) = n’·2^m5^m = n’·10^m.

Reversing the process above, we can show congruence mod 10^m:

2ⁱ(2^p – 1) = 2^i+p – 2ⁱ = n’·10^m.

This shows that for i≥m, , so p is a cycle mod 10^m.

The cycle mod 10^m is the period mod 5^m

We’ve shown that p is a cycle mod 10^m, but not that p is the period mod 10^m. In other words, it’s possible the period mod 10^m is less than p — we have to show it isn’t.

For i ≥ m, we’ve shown that . Using the argument above, congruence mod 10^m means that:

2^i+p – 2ⁱ = n·10^m = n·2^m5^m = (n·2^m)5^m.

This shows that for i≥m, , so p is the period mod 5^m and mod 10^m.

Empirical Evidence that 2 is a Primitive Root mod 5^m

This section is not part of the proof, but it shows some PARI/GP calculations that support it.

These two commands show indirectly that 2 is a primitive root mod 5 through mod 5²⁰, by showing that the order equals Euler’s phi function:

? for(m=1,20,print(eulerphi(5^m)))
4
20
100
500
2500
12500
62500
312500
1562500
7812500
39062500
195312500
976562500
4882812500
24414062500
122070312500
610351562500
3051757812500
15258789062500
76293945312500

? for(m=1,20,print(znorder(Mod(2,5^m))))
4
20
100
500
2500
12500
62500
312500
1562500
7812500
39062500
195312500
976562500
4882812500
24414062500
122070312500
610351562500
3051757812500
15258789062500
76293945312500

This command shows directly that 2 is a primitive root mod powers of 5, using PARI/GP’s znprimroot() function (znprimroot only returns the lowest primitive root, which luckily for us is 2):

? for(m=1,20,print(znprimroot(5^m)))
Mod(2, 5)
Mod(2, 25)
Mod(2, 125)
Mod(2, 625)
Mod(2, 3125)
Mod(2, 15625)
Mod(2, 78125)
Mod(2, 390625)
Mod(2, 1953125)
Mod(2, 9765625)
Mod(2, 48828125)
Mod(2, 244140625)
Mod(2, 1220703125)
Mod(2, 6103515625)
Mod(2, 30517578125)
Mod(2, 152587890625)
Mod(2, 762939453125)
Mod(2, 3814697265625)
Mod(2, 19073486328125)
Mod(2, 95367431640625)

Summary

To prove the period formula for the positive powers of two mod powers of ten, I first proved it for mod powers of five. I showed that two is a primitive root mod powers of five, meaning that the period formula is Euler’s phi function for the powers of five. I then showed that the period mod powers of five and mod powers of ten must be the same, after a certain starting point.

References

These are the main influences behind my proof:

• Challenging Mathematical Problems with Elementary Solutions, Volume 1. Page 198: “It can be proved that the last k digits of the number 2ⁿ are repeated in groups of 4·5^k-1, starting with the number 2^k.”
• The USSR Olympiad Problem Book; Selected Problems and Theorems of Elementary Mathematics. Page 57, problem 243, and its answer, on page 354, discuss the case for powers of two mod 10¹⁰.
• Question I asked at physicsforums.com. User hamster143’s proof that the period for powers of five and ten are equal.
• Discussion at physicsforums.com. User shmoe’s comment: “a power of 2’s congruence class mod 10 is completely determined by its congruence class mod 5”.
• Hakmem Item 57. Two comments by Schroeppel:
  • “After the nth, they are all multiples of 2ⁿ.”
  • “They get into a loop of length 4·5^m-1. (Because 2 is a primitive root of powers of 5.)”
• Question I asked at mathoverflow.net.

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Cycle Length of Powers of Two Mod Powers of Ten

NaNs in NPR Media Player (click image to enlarge).

The counter displays NaN:NaN:NaN. It should show the current time count, like 01:12 (why it shows three NaNs instead of two I don’t know). NaN is the floating-point representation of “not a number,” which means something went wrong in their calculation of the timestamp.

This happened after I hibernated my computer and powered up, while the media player was paused.

(Maybe my blogging “will bring change” to the NPR Media Player .)

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

Floating-Point Error in the NPR Media Player

My Custom Binary-Themed Calendar For 2010

Here are thumbnail images of each month:

January 2010

February 2010

March 2010

April 2010

May 2010

June 2010

July 2010

August 2010

September 2010

October 2010

November 2010

December 2010

This is my personal calendar — it’s not for sale!

(Courtesy Stock.XCHNG, Dreamstime, Morguefile, and shutterfly.)

By Rick Regan (Copyright © 2008-2010 Exploring Binary)

My Custom Binary Themed Calendar for 2010