Let Sigma = {a, b, c, d, e} be an alphabet. We define an encoding scheme as follows: g(a) = 3, g(b) = 5, g(c) = 7, g(d) ...

Question

Let Sigma = {a, b, c, d, e} be an alphabet. We define an encoding scheme as follows: g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11. Let p_i denote the i-th prime number (p_1 = 2). For a non-empty string s = a_1 ... a_n, where each a_i in Sigma, define f(s) = prod_{i=1}^{n} p_i^{g(a_i)}. For a non-empty sequence (s_1, ..., s_n) of strings from Sigma^+, define h((s_1, ..., s_n)) = prod_{i=1}^{n} p_i^{f(s_i)}. Which of the following numbers is the encoding, h, of a non-empty sequence of strings? A. 2^7 * 3^7 * 5^7  B. 2^8 * 3^8 * 5^8  C. 2^9 * 3^9 * 5^9  D. 2^10 * 3^10 * 5^10

Accepted Answer

Only 2^8 * 3^8 * 5^8 has exponents equal to a valid f-value (8 = f('a')), so the answer is Option B. The scheme uses unique prime factorization twice. A string s becomes f(s) = a product of primes 2, 3, 5, ... whose exponents are the g-values 3, 5, 7, 9, 11 (all ODD). A sequence becomes h = product of primes 2, 3, 5, ... whose exponents are the f-values of the strings. So for a given number to be a valid h, each of its prime exponents must itself be a legal f(s). The smallest legal f-value is f of a one-letter string a, namely 2^3 = 8. So an exponent of 8 is achievable, but 7, 9, 10 are not f-values, which selects option B.