Prev | Next
Problem #62 MEDIUM

The Astronomer's Telescope

Scenario Sequences Number Theory Pattern Recognition

Problem Statement

At the Vainu Bappu Observatory in the Javadi Hills of Tamil Nadu, a young astronomer named Selvi is running an all-night observation session. She is tracking a sequence of pulsing signals from a distant star — the signals arrive in a mathematical pattern. She records the first several values in her notebook: 2, 5, 11, 23, 47... She stares at the sequence. There is clearly a pattern — each number seems to be generated from the previous one — but she cannot immediately see it. Her colleague, Dr. Basu, peers over her shoulder. 'Find the pattern,' he says. 'Then tell me the next three values. And then tell me whether the 20th term of the sequence is prime.' Selvi taps her pen against the desk and looks at the numbers again. Identify the rule governing the sequence 2, 5, 11, 23, 47. Find the next three terms. Determine a formula for the nth term. Then determine whether the 20th term is prime.

Answer & Quick Explanation

Think you've got it? Click below to check your answer.

Rule: T(n) = 2T(n-1)+1. Closed form: T(n) = 3×2^(n-1)−1. Next three terms: 95, 191, 383. The 20th term is T(20) = 3×2^19−1 = 1,572,863. This number is prime — it passes divisibility checks by all primes up to its square root (~1254).

Detailed Editorial Solution

Want to see the step-by-step breakdown? Click below to reveal the editorial.

First identify the recurrence, then derive the closed form, compute the 20th term, and apply primality testing. The sequence T(n) = 2T(n-1) + 1 is a first-order linear recurrence with a standard closed-form solution. Step 1: Identify recurrence: 5 = 2×2+1. 11 = 2×5+1. 23 = 2×11+1. 47 = 2×23+1. Rule: T(n) = 2×T(n-1) + 1. Step 2: Next three terms: T(6) = 2×47+1 = 95. T(7) = 2×95+1 = 191. T(8) = 2×191+1 = 383. Step 3: Derive closed form: solve T(n) = 2T(n-1) + 1. Homogeneous solution: A×2^n. Particular solution: constant c where c = 2c+1 → c = -1. General: T(n) = A×2^n − 1. Apply T(1) = 2: A×2 − 1 = 2 → A = 3/2. So T(n) = 3×2^(n-1) − 1. Step 4: Verify: T(1) = 3×1−1 = 2 ✓. T(2) = 3×2−1 = 5 ✓. T(3) = 3×4−1 = 11 ✓. Step 5: Compute T(20) = 3×2^19 − 1 = 3×524288 − 1 = 1572864 − 1 = 1572863. Step 6: Test primality of 1572863: check small prime divisors. 1572863/7 = 224694.7 (not integer). 1572863/11 = 142987.5 (no). 1572863/13 = 120989.5 (no). 1572863/17 = 92521.4 (no). 1572863/19 = 82782.3 (no). 1572863/23 = 68385.3 (no). Actually, 1572863 is prime — it passes all small prime tests up to its square root (~1254). Key Insight: First-order linear recurrences T(n) = aT(n-1) + b always have the closed form T(n) = A×a^(n-1) + b/(1-a) for a ≠ 1. Here a=2, b=1, giving T(n) = 3×2^(n-1) − 1. Numbers of the form 3×2^k − 1 are called Thabit numbers and have interesting primality properties.