A sequence s0,s1,s2,s3,… is defined by s0=s1=1 and, for every positive integer n,s2n=sn,s4n+1=s2n+1,s4n−1=s2n−1+s2n−12/sn−1. What is the value of s1000?
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
720 Some experimentation with small values may suggest that sn=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 100010=11111010002, with six ones, s1000=6!=720.
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.