Competition problem — Algebra — Maths Olympiad Prep

Library / /418 of 860

Algebra Difficulty 5.2 AIME, harder Find the answer

A sequence $s_{0}, s_{1}, s_{2}, s_{3}, \ldots$ is defined by $s_{0}=s_{1}=1$ and, for every positive integer $n, s_{2 n}=s_{n}, s_{4 n+1}=s_{2 n+1}, s_{4 n-1}=s_{2 n-1}+s_{2 n-1}^{2} / s_{n-1}$ . What is the value of $s_{1000}$ ?

Your answer

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

Solution

720 Some experimentation with small values may suggest that $s_{n}=k$ !, where $k$ is the number of ones in the binary representation of $n$ , and this formula is in fact provable by a straightforward induction. Since $1000_{10}=1111101000_{2}$ , with six ones, $s_{1000}=6!=720$ .

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.