" wrote: note that $ x_n$ is a natural and square free number,now denote the sequence of prime numbers as $ p_0 = 2,p_1 = 3,\ldots.$ now denote the sequence $ a_n = \left(s_m,s_{m - 1},\ldots ,s_0\right)$ in which each $ s_i$ is equal to $ 1$ iff $ p_i\mid x_n$,and $ 0$ otherwise. now it can be easily proved,using induction,that $ a_n$ is the representation of $ n$ in base $ 2$,which yields that $ x_n = 1995$,$ a_n = (1,0,0,0,1,1,1,0)$ and $ n = 142$. QED

This problem happened to be reused in the 2014 AIME II (https://artofproblemsolving.com/wiki/index.php/2014_AIME_II_Problems/Problem_15)

Easy problem, but unfortunately I didn't get the binary representation idea . Anyway, here's my solution: Let $p_k$ denote the $k^{\text{th}}$ prime, and define the primorial $p_k^*=p_1 \times p_2 \times \dots \times p_k$. Note that if at any moment $x_{n-1}=p_{k-1}^*$, then $x_n=p_k$. The main claim is as follows:- CLAIM: If $x_n=p_k$ for some $k,n \in \mathbb{N}$, then $x_{n+2^{k-1}-1}=p_k^*$. Proof of Claim We proceed by strong induction on $k \geq 1$. The result easily follows for $k=1,2$. Suppose the result is true for $1,2, \dots ,k-1$. We will show that it is true for $k$ also. Notice that a prime greater than $p_k$ is not introduced into the sequence $(x_i)$ as long as we don't reach $p_k^*$. So till that instant (if we actually do reach $p_k^*$), we have that $p_k$ remains intact in the sequence. We claim that we eventually reach $p_ip_k$ for some $1 \leq i \leq k-1$. We again induct (nested induction ) on $i \geq 1$. Note that $x_{n+1}=2p_k=p_1p_k$, so the result is true for $i=1$. Suppose we reach $p_ip_k$, i.e. $x_m=p_ip_k$ for some $m>n$. Then after $2^{i-1}-1$ steps (from the induction hypothesis of the outer induction, which is applicable here since $i<k$), we will get to $p_i^*p_k$, or equivalently $x_{m+2^{i-1}-1}=p_i^*p_k$. Then, using the defining recursion of the sequence $(x_i)$, we have $x_{m+2^{i-1}}=p_{i+1}p_k$, as desired. By putting $i=k-1$ in the above result, we get that we'll eventually encounter $p_{k-1}^*p_k=p_k^*$. Also the number of steps in reaching $p_k^*$ from $p_k$ can now be easily calculated, as the sum of the number of steps it takes to reach $p_{i+1}p_k$ from $p_ip_k$ for all $1 \leq i \leq k-1$. This evaluates to $2^0+2^1+ \dots +2^{k-2}=2^{k-1}-1$. Thus, $x_{n+2^{k-1}-1}=p_k^*$, as required. $\Box$ Return to the problem at hand. Note that $1995=3 \times 5 \times 7 \times 19$, which means we have $p_k=19$ with $k=8$. Also, if $x_n=1995$, then $x_{n+1}=p_4^* p_k$ (since $p_4=7$). Thus, we will reach $1995$ in the sequence when first we'll encounter $p_i^*$ for all $1 \leq i \leq 7$, then encounter $p_j^*p_k$ for all $1 \leq j \leq 4$, and finally remove the last step of reaching $p_4^*p_k$. Thus, the number of steps required is $$(2^0+2^1+ \dots +2^6)+1+(2^0+2^1+2^2+2^3)-1=142 \Rightarrow x_{142}=1995$$Here, we add an intermediate $1$ to account for the step where we reach $p_k$ in the sequence.

For storage. Computing the first few terms, we have \begin{align*} x_0 &= 1 \\ x_1 &= 2^1\\ x_2 &= 2^0 \times 3^1.\\ x_3 &= 2^1 \times 3^1\\ x_4 &=2^0 \times 3^0 \times 5^1\\ x_5 &= 2^1 \times 3^0 \times 5^1 .\\ \end{align*} We see that the exponents in the value fo $x_n$ form the binary representation of $n.$ We can easily prove this with induction. So, we have $1995 = 3 \times 5 \times 7 \times 19,$ which means $n$ is $\overline{10001110}_2 = 142.$

I claim that if $n$ has a binary representation of the form $b_xb_{x-1}\ldots b_0$, and $p_i$ is the i-th prime (with $p_0=2$). \[x_n = \prod_{i=0}^{x} p_i^{b_i}\] We proceed with induction. The base case is trivial. Inductive step. Note that adding $1$ to $n$ will remove however many 1s there are on the right side of $n$, and replace the right-most 0 with a 1. Additionally, $x_{n+1}=\frac{x_np(x_n)}{q(x_n)}$ clearly amounts to the same thing, $\frac{1}{q(x_n)}$ removes the series of 1s at the end, and $p(x_n)$ replaces the rightmost 0 with a 1. Thus, these two processes are the same so our induction holds. $\blacksquare$ Thus, $x_n=1995 = 2^03^15^17^119^1 \Longrightarrow n =\overline{10001110} = 128+8+4+2=142$

ISL Sequences is a thing? Note that the sequence $x_i$ is unique. We claim that the sequence is: for $x_n$, convert $n$ into binary, and then read off the last digit as $v_2(x_n),$ the second to last digit as $v_3(x_n)$, and so on. We will then only need to show that this sequence works since there is only one possible sequence. We will use induction. This sequence clearly works at $n=0$ and $n=1$. Now, examine the equation $$x_{n+1}=x_n\cdot \frac{p(x_n)}{q(x_n)}.$$This is essentially saying that goin from $x_n$ to $x_{n+1}$, we gain 1 factor of the smallest prime that $x_n$ doesn't have, but then we lose our factors of all primes before that smallest prime. This is isomorphic to adding 1 in binary: the rightmost 0 digit becomes a 1, but everything after that becomes 0. Therefore, we have shown our claim by induction. Since $1995=3\cdot 5\cdot 7\cdot 19$, our answer is $$10001110_2=\boxed{142}.$$

The idea is to classify the sequence $x_n$. Suppose $n$ has $k$ digits in binary; then, for each $1 \leq i \leq k-1$, the $i$th digit from the right corresponds to the power of the prime $p_i$ in the sequence $\{x_n\}$. This is easy to show inductively. Thus the answer is $ 10001110_2 = \boxed{142}$.

Let $P_i$ be the $i+1$th prime number. We claim that $\sum_{i=0}^\infty 2^iv_{P_i}(x_n)=n$. This is easy to prove by induction. Since $1995=3\cdot5\cdot7\cdot19$, our answer is $2+4+8+128=142$.

We list out all the primes from greatest least. We claim that the binary representation of the exponents is the value of $n$ needed to obtain that number. For example since $1995 = 19^1 \cdot 7^1 \cdot 5^1 \cdot 3^1$ and $19$, $7$, $5$, and $3$ are the eighth, fourth, third, and second primes respectively. We see the this would give $2^7 + 2^3 + 2^2 + 2^1 = \boxed{142}$. We prove the result by induction. The base case is trivial since $x_1 = 2$. The inductive is obviously just adding $1$ in binary since we replace all of the consecutive ones and carry over the last $1$. $\blacksquare$ I solved this in like $5$ min because I had already done AIME 2014 problem 15

Just realized something called Sequences existed back then. Let $p_1,p_2,\cdots$ be the sequence $2,3,\cdots$ of the primes in increasing order. Now, fist we have $$x_0=1, x_1=2, x_2=3, x_3=6$$Then, assume that for $i=2^{k_1}+2^{k_2}+\cdots + 2^{k_j}$ $$x_i = p_{k_1+1}p_{k_2+1}\cdots p_{k_j+1}$$for all $i \leq 2^n-1$ Then, $$x_{2^n}=\frac{x_{2^n-1}p(x_{2^n-1})}{q(x_{2^n-1})} = p_{n+1}$$Then, say for some $1\leq k < 2^n-1$ we have $$x_{2^n+k}=x_kp_{n+1}$$for all $1, \cdots, k$ Thus, we obtain $$ x_{2^n+k+1} = \frac{x_{2^n+k}p(x_{2^n+k})}{q(x_{2^n+k})} $$Now, since $x_k<x_{2^n-1}=p_1p_2\cdots p_n$. There exists a prime $p \in \{p_1,\cdots,p_n\}$ such that $p \nmid x_k$. Thus, $p(x_{2^n+k})=p(x_kp_{n+1})=p(x_k)$. Thus, \begin{align*} x_{2^n+k+1} &= \frac{(x_kp_{n+1})p(x_kp_{n+1})}{q(x_kp_{n+1})}\\ &= \frac{(x_kp_{n+1})p(x_k)}{q(x_k)}\\ &= p_{n+1}x_{k+1} \end{align*}as needed. Thus by the Principle of Mathematical Induction we have that for all $1\leq k < 2^n$. Then, combining this with the previous fact we can again apply the Principle of Mathematical Induction to obtain that for all $n \in \mathbb{N}$ if $n=2^{k_1}+\cdots + 2^{k_j}$ then $x_n = p_{k_1+1}\cdots p_{k_j+1}$. Thus, we obtain that since $1995 = 3\times 5 \times 7 \times 19$ which gives us that if $x_i = 1995$ $$i = 2^1+2^2+2^3+2^7 = \boxed{142}$$which is the required answer.

For every base $10$ positive integer $n$, let $n_2$ be the binary representation of $n$, and $S_n$ be the set of all $i$ such that the $i$th digit of $n_2$ is $1$. Claim: For $n \ge 1$ we have $$x_n = \prod_{i \in S_n}p_i, $$where $p_i$ is the $i$th prime. Proof: We use induction on $n$. For the base case of $n = 1$, just note that $x_1 = 2$. For the inductive step, assume that the assertion holds for some positive integer $n$. Then to obtain $(n + 1)_2$, we need to: find the rightmost digit in $n_2$ which is a $0$ (if $n_2$ only contains $1$s, take the digit place to the left of its leftmost $1$) replace said digit with a $1$, and replace all of the digits to its right with a $0$ However, by the given formula, this is also exactly what happens to obtain $x_{n + 1}$ with the product on the RHS of the assertion. This proves the claim. Thus, since $1995 = 3 \cdot 5 \cdot 7 \cdot 19$, and $3 = p_2, 5 = p_3, 7 = p_4, 19 = p_8$, we can extract the final answer of $n = 2^1 + 2^2 + 2^3 + 2^7 = \boxed{142}$.

hmmm i didnt phrase my solution in terms of binary The answer is $n=142$ only. We prove a series of claims. Claim: $x_{n+1}=2x_n$ when $n$ is even. Furthermore, all even-indexed terms are odd, and all odd-indexed terms are even. That is, they alternate parity. Proof. First, observe for any odd term $x_i,$ we have $p(x_i)=2,$ so $q(x_i)=1.$ Thus $\tfrac{x_ip(x_i)}{q(x_i)}=2x_i.$ If $x_i$ is an even term, then $p(x_i)$ is odd, and the prime factorization of $q(x_i)$ contains $2.$ Then the $2$'s in the prime factorization of $x_i$ and $q(x_i)$ cancel and the remaining number is odd. Claim: There can be no divisors of multiplicity $>1$ in any $x_i.$ Proof. At each step, $x_i$ is multiplied by $p(x_i),$ which by definition is the smallest prime not in the prime factorization of $x_i.$ Dividing by $q(x_i)$ only removes existing divisors. Claim: Primes appear in the sequence in ascending order. In particular, the $i$th prime appears when $n=2^{i-1}.$ Proof. Induct with base case $x_1=2.$ For inductive step, let $p_i$ be the $i$th prime and assume $x_{2^{i-1}}=p_i.$ This consequently implies all past prime factorizations involving divisors $1,2, \dots, p_{i-1}$ have appeared before this point. We prove $x_{2^{i}}=p_{i+1}.$ The key observation is to scale the procedure $x_0 \to x_1 \to \dots \to x_{2^{i-1}-1}$ up by $p_i.$ Then, after scaling, $x_0=x_{2^{i}},$ so we may shift this procedure so the starting point is at $x_{2^{i-1}}.$ Then, the endpoint is at $x_{2^{i}-1}=2 \cdot 3 \cdots p_i,$ so $x_{2^i}=p_{i+1}.$ Claim: Every $x_i$ is unique. Proof. Induct with primes. For the base case $x_1=2$ we see every term before it is unique. For inductive step, assume every term before $x_{2^{i-1}}=p_i$ is unique. Then from the same scaling and shifting as before we see every term up until $p_{i+1}$ is unique. Extending this infinitely gives the result. Prime factorizing, $1995=3 \cdot 5 \cdot 7 \cdot 19.$ From our claims, we know $19$ appears at $x_{128}.$ It is easy to check from here that $1995$ is achieved at $x_{142}.$

Notice that all $x_i$ are squarefree. Consider representing $x_i$ as a binary string, where bit $k$ is 1 if and only if the $k$-th smallest prime divides $x_i$. Our recursion essentially states that we change the first nonzero bit to 1 and make every previous bit 0, which is simply adding 1 in binary. Since $x_0=1$ corresponds to 0 in binary, we know \[x_n = 19^1 \cdot 17^0 \cdot 13^0 \cdot 11^0 \cdot 7^1 \cdot 5^1 \cdot 3^1 \cdot 2^0 \implies n = 10001110_2 = \boxed{142}. \quad \blacksquare\]

Writing out the first few terms in prime form, it becomes apparent that the exponents of the primes in $x_n$ are (including zeros) the binary representation of $n$. For example, $x_5=10 = 2 \cdot 5 = {101}_2$. We can now view the statement as an analogy of adding $1$ in binary. We locate the first zero term, make it one, and make everything before it zero. This can be visualized as "carrying" when adding the one. Now $1995 = 3 \cdot 5 \cdot 7 \cdot 19 \implies {10001110}_2 = \boxed{142}$