User:Quantum-phantom

Revision as of 07:34, 14 March 2024 by Quantum-phantom (talk | contribs)

This message is regarding [url=https://artofproblemsolving.com/community/c594864h3265596p30137934]this post[/url]. [quote="fura3334"][b]Problem 10[/b] (unclear source) For a positive integer $n$, denote by $f(n)$ the number of ways to represent $n$ as the sum of powers of 2. Different orders [color=#960000]are[/color] considered different representations, e.g. $4+1+1$ and $1+4+1$ are two different representations of $6$. Call $n$ "good" if $f(n)$ is even. Let $A$ be the largest number of consecutive good numbers in $\{1,2,\cdots,2025\}$. Find the remainder when $A$ is divided by 1000.[/quote]

I just read [color=#960000]are[/color] as [color=#960000]aren't[/color]. (yesterday)

Let n=a1+a2+ where all ai are powers of 2. If a1=1, then a2+a3+=n1, with f(n1) choices; If a1=2, then a2+a3+=n2, with f(n2) choices... So f(n)=i=0log2nf(n2i).

We use induction on n to show that $f(n)$ is odd iff $n$ is in the form of 2t1, where t is a natural number.