3
$\begingroup$

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".

$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ But unfortunately you need to guess N, dont you? $\endgroup$
    – elmes
    Sep 14, 2012 at 16:02
  • $\begingroup$ Isn't $N$ the given information? As in "find the $N$-th word". $\endgroup$
    – aviness
    Sep 14, 2012 at 16:08
  • $\begingroup$ Uh, I meant S_n ... We cant tell the degree by looking at N, can we? $\endgroup$
    – elmes
    Sep 14, 2012 at 16:13
  • $\begingroup$ 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. $\endgroup$
    – aviness
    Sep 14, 2012 at 16:19
  • $\begingroup$ $S_j$ assumes j>0. What about first words, e.g.3rd word in the sequence? $\endgroup$
    – elmes
    Sep 14, 2012 at 16:35
0
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ 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". $\endgroup$
    – Hagen von Eitzen
    Sep 14, 2012 at 14:41
  • $\begingroup$ You are right. aviness answer the question exactly. $\endgroup$
    – Yangzhe Lau
    Sep 14, 2012 at 14:47
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .