Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem...
How do I count how many iterations are between "a" and "bbb" if I keep incrementing the letters?
By incrementing, I mean sequencing in this manner:
a, b, c, ...., y, z, aa, ab, ac, ...., bbb
I'd like to "calculate" how many items are in that sequence.

How I came about this problem...
The Chrome's Keyboard Navigation extension produces keyboard shortcuts for all links on the current page. It assigns the keyboard shortcuts in the same way I described above.
One long page reached the shortcut "bbb" and just started wondering how many links that would be, and was unable to come up with a mathematical way to solve it.
So I wrote a quick program and found the answer is 1,405 iterations.
But surely math can answer faster than writing code for it.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

This post consists of three parts: A) a slow but steady way to do the calculation; B) a demonstration of how the idea of base $26$ representation of numbers can be used to speed up the calculation; C) an introduction to a modified notion of representation that gives an instant answer and will, we hope, befun to think about.

A) Slow but Steady: There are $26$ $1$-letter "words."

How many $2$-letter words are there? The first letter of a $2$-letter word can be chosen in $26$ ways. For each of these ways, the second letter can be chosen in $26$ ways, for a total of $26^2$. (If $26$ women each have $26$ children, then the total number of children is $26^2$.)

The same idea shows that there are $26^3$ $3$ letter words, $26^4$ $4$-letter words, and so on.

However, we don't even want to count all the $3$-letter words, only those up to $bbb$.

How many $3$-letter words start with $a$? We can complete $a$ to a $3$-letter word by appending to $a$ any $2$-letter word. There are $26^2$ such $2$-letter words. So $26^2$ $2$-letter words start with $a$.

Finally, we want to count the $3$-letter words that start with $b$, but we only want to get to $bbb$. So append any $2$-letter word that starts with $a$ (there are $26$ of these), and finally at the very end we must not forget about $bba$ and $bbb$ (2 words).

Add up. We get $1406$. But probably you did not intend to count the first word, just the "iterations" or "increments." There are $1405$ of these.

B) Using Base 26 Representation: The $1$-letter words were easy to count, as were the $2$-letter words. The $3$-letter words were a bit of a nuisance, since we did not have a "full set." And we were lucky that the end was at $bbb$.

If you know representing numbers to different bases, there is a neat way of counting the $3$-letter part.

Think of representing a number to the base $26$. Use $a$ to represent the digit we usually call $0$, $b$ to represent the digit we usually call $1$, $c$ to represent the digit we usually call $2$, and so on.

(This is not so far-fetched. When we use base $16$ (hexadecimal) we use the "digits" $0$, $1$, $\dots$, 9, A, B, C, D, E, and F. Here instead of recycling some of the old standard digits, we are using new symbols for "digits" from the beginning.)

We show that there is a close connection between numbers to the base $26$ and our $3$-letter words.

Let's first think in terms of ordinary base $10$ representation of numbers from $0$ to $999$. Most of them have $3$ digits, but the small ones have fewer. It is convenient to "pad" the short ones with initial $0$'s, so that each has $3$ digits. Thus seven would be represented as $007$.

Use the same convention with base $26$. So the $3$-letter words can be thought of as base $26$ numbers from $0$ to $26^3-1$. With this convention, the words $aaa$ to $bbb$ represent all numbers from $0$ to "$bbb$". But $bbb$ is $$1 \times (26)^2+1\times(26)^1+ 1\times (26)^0,$$ which, in decimal, is $703$. And there are $704$ numbers from $0$ to $703$.

Thus the total number of words is $$26 +26^2 +704.$$ Calculate. We get $1406$. To get the number of steps, we subtract $1$.

There is a way to short-circuit the computation even further, since the $26+26^2$ part, and the $1$ that we added to $703$, can be incorporated into the last part of the calculation.

To see how, note that $26^2+26+1$ is just $bbb$ in base $26$. So all we need to do is add $bbb$ to $bbb$, and evaluate. Unfortunately, $bbb$ occurs twice here, with different roles. So let's do another example, and ask how many words there are from $a$ to $dgc$, inclusive. To get the answer, just find $bbb+dgc$ Note that $bbb+dgc=ehd$, and evaluate. Or else, do the same thing more slowly:

$d$ represents $3$. Add $1$ to this, getting $4$;

$g$ represents $6$. Add $1$ to this, getting $7$;

$c$ represents $2$. Add $1$ to this, getting $3$.

The total is then $4 \times 26^2+7\times 26^1 +3\times 26^0$.

Exactly the same basic idea can be used to solve any problem of this general kind, over any alphabet, and up toa ny specified word, however long. It comes down to a mechanical one-line computation.

Using Modified Base $26$ Representation: Probably not a lot of people care about base $26$ representation, modified or not. So we use this opportunity to write about what we will call modified base $10$ representation.

Imagine a society which has a horror of zero, because it reminds them of hunger, or the great void, or whatever. Let's see how we can modify our usual base $10$ positional notation to suit their needs.

The idea is simple. We will use digits $1$, $2$, $3$, $\dots$, $9$ as usual, and introduce a new digit $x$ to stand for ten. Now a $4$-digit number like $25x8$ stands for $2 \times 10^3+5\times 10^2 +10\times 10^1 +8 \times 10^0$.

Let's practice counting in modified decimal. Here goes, to one hundred and one.

$$1, 2, \dots, 9, x, 11, 12, \dots, 19, 1x, 21, 22, \dots, 2x, \dots, 89, 8x, 91, \dots, 99, 9x, x1$$

Easy! And arithmetic, once you get used to it, is no harder than in conventional decimal.

We can similarly think of modified base $26$, with $a$ for $1$, $b$ for $2$, and so on up to $z$ for $26$. The crucial fact is that the number of words of length from $1$ to $k$, up to any $k$-letter word $W$, is just the value of $W$ when it is thought of as a modified base $26$ number. This is because these words are just the names, in order, of the numbers from $1$ to the value of $W$.

Thus the number of such words can be evaluated in one short line.

share|improve this answer
    
If $a$ represents digit zero, then $s$ and $as$ and $aas$ are the same number? –  GEdgar Jul 22 '11 at 20:15
    
Brilliant! When you had the step-by-step solution up, I was like "cool, that makes sense" but was waiting for the base-26 approach. As soon as you did that, I slapped the ACCEPT button! 10^5 thanks! –  BeemerGuy Jul 22 '11 at 23:13
    
@GEdgar: Again, thanks for pointing out my earlier egregious blunder. Have added a last section giving a bijective argument, without calling it that. –  André Nicolas Jul 23 '11 at 13:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.