Greedy Squares

Number Theory Level 5

Consider the following recursive process:

$a_{n+1}=a_n-\lfloor\sqrt{a_n}\rfloor^2$

For all positive integers $a_0$ , the process above eventually results in $a_n = 0$ for all $n \geq k$ for some positive integer $k$ . What is the first value of $a_0$ such that $k=7\text{?}$

The answer is 7223.

2 solutions

Garrett Clarke
Aug 29, 2015

It's clear that we have $a_0=k$ for $k=\{1,2,3\}$ because the largest square that can be subtracted for those values is $1$ . From there, we use the following recursive method to find the minimal $a_0$ for all $k>3$ , where $b_k=a_0$ for a given value of $k$ .

$b_{n+1} = b_n + \left(\frac{b_n+1}{2}\right)^2$

Starting with $b_3=3$ , we get $b_4=7$ , $b_5=23$ , $b_6=167$ , and $b_7=\boxed{7223}$ .

It looks like your indices are mixed up in the solution. To be consistent with the way the problem is posed, you should have $a_0=7223$ and $a_7=0$ . The oversight should be easy to correct.

Otto Bretscher - 5 years, 9 months ago

The formula above gives the answers for $a_0$ for a certain value of $k$ . What I should really do is change the variable in the solution to $b_n$ to a avoid confusion with the original problem. Thanks!

Garrett Clarke - 5 years, 9 months ago

Try this

Department 8 - 5 years, 8 months ago

Billy Sugiarto
Sep 2, 2015

Let $a_{0} = k_{0}^{2} + t_{1}$ for $k, t_{1} \in N$ . Thus $a_{1} = t_{1}$ .

Now let $t_{i} = k_{i}^{2} + t_{i+1} \forall i \in N$ . Thus we have $a_{k} = t_{k} \forall k \in N$ .

Let $a_{7} = t_{7} = 0$ , we have $a_{0} = k_{0}^{2} + k_{1}^{2} + ... + k_{6}^{2}$ .

Obviously $k_{i}^{2} \geq k_{i+1}^{2} + k_{i+2}^{2} + ... + k_{6}^{2} \forall i \in [0,5].$

Thus we have the smallest set of $(k_{6}, k_{5}, k_{4}, k_{3}, k_{2}, k_{1}, k_{0} ) = (1, 1, 1, 2, 4, 12, 84)$ . It implies that $a_{0} = 7223$ .

Greedy Squares

The answer is 7223.

2 solutions

0 pending reports