User:Quantum-phantom

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=a_1+a_2+\cdots$ where all $a_i$ are powers of $2$. If $a_1=1$, then $a_2+a_3+\dots=n-1$, with $f(n-1)$ choices; If $a_1=2$, then $a_2+a_3+\dots=n-2$, with $f(n-2)$ choices... So $f(n)=\sum\limits_{i=0}^{\left\lfloor\log_2n\right\rfloor}f\left(n-2^i\right)$.

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

Page

Toolbox

Search

User:Quantum-phantom