Let Σ = {a, b, c, d, e} be an alphabet. Define g(a) = 3, g(b) = 5, g(c) = 7,…
2003
Let Σ = {a, b, c, d, e} be an alphabet. Define g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, and g(e) = 11. Let p_i denote the i-th prime number, with p_1 = 2. For a non-empty string s = a_1a_2...a_n, where each a_i ∈ Σ, define f(s) = ∏{i=1}^n p_i^{g(a_i)}. For a non-empty sequence <s_1, ..., s_k> of strings from Σ+, define h(s_1, ..., s_k) = ∏{i=1}^k p_i^{f(s_i)}. Which of the following numbers is the encoding h of a non-empty sequence of strings?
- A.
2⁷ · 3⁷ · 5⁷
- B.
2⁸ · 3⁸ · 5⁸
- C.
2⁹ · 3⁹ · 5⁹
- D.
2¹⁰ · 5¹⁰ · 7¹⁰
Attempted by 3 students.
Show answer & explanation
Correct answer: B
For any non-empty string s, f(s) is a product of prime powers whose exponents come from g. The smallest string is a, for which f(a) = 2^3 = 8. In the sequence encoding h(s_1, ..., s_k), the exponents of the consecutive prime bases must be the corresponding f(s_i) values. Thus 2^8 · 3^8 · 5^8 is valid because it represents the sequence <a, a, a>. The other options either use impossible exponents or skip a required consecutive prime base.