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.

Suppose I have an alphabet (e.g. consisting of ABCDEF) and a lexicographic order is defined i.e.

A -> B ... -> F -> AA -> AB .. -> AF -> BA -> BB -> ... -> BF ... -> FF -> AAA -> ...

Is there a way to check, what the N-th word in the above sequence is? For instance, the first work is "A", the 7th is "AA".

share|improve this question

3 Answers 3

up vote 5 down vote accepted

It just looks like a numbering system with base 6 instead of 10. So I would just use the normal equation for changing bases.

Like $A=0, B=1, C=2, D=3, E=4, F=5$, and use the normal formula to switch the number between decimal system and system based on 6.


Actually, it looks a bit more complicated than that since there is no "zero" in this system. Define $S_n = \sum_{i=0}^n 6^n$. Given any $N$, let $j$ be the largest integer such that $S_j \leq N$. Let $N_0 = N - S_j$.

Now change $N_0$ into base 6, and fill the digits so that you get $j+1$ many digits. Then switch back to the alphabet system.

For instance, if you want to find 51st word, you would notice that $43 = S_2 < 51$, so $N_0 = 51-43 = 8$. $8$ in base 6 is $12$, so fill the zeroes in front to get $012$. Finally, the word you were looking for would be $ABC$.

share|improve this answer
    
But unfortunately you need to guess N, dont you? –  elmes Sep 14 '12 at 16:02
    
Isn't $N$ the given information? As in "find the $N$-th word". –  aviness Sep 14 '12 at 16:08
    
Uh, I meant S_n ... We cant tell the degree by looking at N, can we? –  elmes Sep 14 '12 at 16:13
    
Well, $S_n$ behaves like partial sum of a geometric series, so you could use the partial sum formula to simplify the process a bit, but writing $j$ in terms of $N$ seem difficult. –  aviness Sep 14 '12 at 16:19
    
$S_j$ assumes j>0. What about first words, e.g.3rd word in the sequence? –  elmes Sep 14 '12 at 16:35

Since you have six alphabets here, you are going to have to convert the n (term which you want to find, into a base 6 number).

For example if you want to find the 17th character in that sequence you will have to write something like (17) in base 10 = (25) in base 6.

You then assign each alphabet a number so you will have A = 1. B = 2. C = 3. D = 4. E = 5. F = 6.

Hence the number 25 in base six is BE. So BE is the 17th number in the sequence.

share|improve this answer

This is the same question as "How to change a number in decimal system to senary system?". Assume N=a1*6+a2*6^2+a2*6^3+...+ai*6^i(a1,a2,...,ai in {0,1,2,3,4,5}). The jth letter in the word belongs to aj(A if aj=1, B if aj=2 and so on).

share|improve this answer
    
Not exactly. As the first two-letter word ends in $A$, the letter $A$ should play the role of digit 0. But then we have "00" instead of "10" after "9". –  Hagen von Eitzen Sep 14 '12 at 14:41
    
You are right. aviness answer the question exactly. –  Yangzhe Lau Sep 14 '12 at 14:47

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.