Maths Olympiad Prep

Library / /12 of 144

Number theory Difficulty 7.6 National olympiad, round 2 Find the answer

For an integer x1x \geq 1, let p(x)p(x) be the least prime that does not divide xx, and define q(x)q(x) to be the product of all primes less than p(x)p(x). In particular, p(1)=2.p(1) = 2. For xx having p(x)=2p(x) = 2, define q(x)=1q(x) = 1. Consider the sequence x0,x1,x2,x_0, x_1, x_2, \ldots defined by x0=1x_0 = 1 and xn+1=xnp(xn)q(xn) x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} for n0n \geq 0. Find all nn such that xn=1995x_n = 1995.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are given a sequence x0,x1,x2, x_0, x_1, x_2, \ldots defined by x0=1 x_0 = 1 and the recursive formula

xn+1=xnp(xn)q(xn) x_{n+1} = \frac{x_n p(x_n)}{q(x_n)}

where p(x) p(x) is the least prime that does not divide x x and q(x) q(x) is the product of all primes less than p(x) p(x) . If p(x)=2 p(x) = 2 , then q(x)=1 q(x) = 1 .

Our goal is to find all n n such that xn=1995 x_n = 1995 .

### Step-by-Step Calculation

Initial value:
x0=1 x_0 = 1

**For x0=1 x_0 = 1 :**
- p(1)=2 p(1) = 2 (the smallest prime not dividing 1)
- q(1)=1 q(1) = 1 (by definition for p(x)=2 p(x) = 2 )

x1=x0p(x0)q(x0)=121=2 x_1 = \frac{x_0 \cdot p(x_0)}{q(x_0)} = \frac{1 \cdot 2}{1} = 2

**For x1=2 x_1 = 2 :**
- p(2)=3 p(2) = 3 (the smallest prime not dividing 2)
- q(2)=2 q(2) = 2

x2=x1p(x1)q(x1)=232=3 x_2 = \frac{x_1 \cdot p(x_1)}{q(x_1)} = \frac{2 \cdot 3}{2} = 3

**For x2=3 x_2 = 3 :**
- p(3)=2 p(3) = 2 (the smallest prime not dividing 3)
- q(3)=1 q(3) = 1 (by definition for p(x)=2 p(x) = 2 )

x3=x2p(x2)q(x2)=321=6 x_3 = \frac{x_2 \cdot p(x_2)}{q(x_2)} = \frac{3 \cdot 2}{1} = 6

From here, we proceed computing each value of xn x_n in a similar fashion, leveraging the division and properties of the primes defined by p(x) p(x) and q(x) q(x) .

### Finding n n such that xn=1995 x_n = 1995

Continuing the sequence recursively as defined:

- Compute subsequent terms using the defined recursive relationship.
- Track when xn=1995 x_n = 1995 .

Ultimately, through this method, one finds:

n=142 n = 142

Therefore, the value of n n such that xn=1995 x_n = 1995 is 142\boxed{142}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.