I think it is a really nice problem.Can anybody post a solution different from the official (I privately think that the official solution is too hard to come up with )

It is not true. Consider $N=(k+1)^2+...(k+n)^2=\frac{n[2n^2+3n(2k+1)+6k^2+6k+1]}{6}$. If $N=p>2$ is prime must be $n|6$. $n=1$ give $N=(k+1)^2\not =p$. $n=2$ give $N=2k^2+6k+5=f_2(k)$, $n=3$ give $N=3k^2+12k+14=f_3(k)$, $n=6$ give $N=f_3(k)+f_3(k+3)=f_6(k)=6k^2+42k+91$. there are infinitely many primes p, suth that $p\not =f_2(k_1),f_3(k_2),f_6(k_3)$, because $\pi(N)>3\sqrt N$ for big N.

Who said that these perfect squares have to be consecutive?

hxy09 wrote: I think it is a really nice problem.Can anybody post a solution different from the official (I privately think that the official solution is too hard to come up with. This actually is a well-known result. Check out Sloane for some references: http://www.research.att.com/~njas/sequences/A001422

By a theorem due to Lagrange, any positive integer is expressible as a sum of 4 squares (possibly 0). There are 4 possible cases for having 2 non-distinct squares: (1) $4(a^2)$ (2) $2(a^2 + b^2), a \neq b$ (3) $3a^2 + b^2, a \neq b$ (4) $2a^2 + c^2 + d^2$, $a,c,d$ are distinct. Incomplete progress:

Also, the number of representation of $n$ as a sum of 4 squares is at least $8 \sum_{d|n} d$. But each solution is counted at most $4! \cdot 16$ times, so when $\frac {8 \sum_{d|n} d}{24 \cdot 16} = \frac {\sum_{d|n} d}{48}$ is big enough (the least amount of distinct representations) we can probably avoid having equal squares.

bambaman wrote: ...The number of representations by 2 squares is known: $\prod_{p \equiv 1 \pmod 4} (1 + v_p(n))$... where can I find this forluma?

http://mathworld.wolfram.com/SumofSquaresFunction.html ($r_2$)

bambaman wrote: Also, the number of representation of $n$ as a sum of 4 squares is at least $8 \sum_{d|n} d$. No The exact number is $8 \sum_{4\nmid d|n} d$, which is smaller in general (but shows that you just need to adapt for $n$ having large $2$-adic valuation). Flakky wrote: where can I find this forluma? In the formulary.

test20 wrote: hxy09 wrote: I think it is a really nice problem.Can anybody post a solution different from the official (I privately think that the official solution is too hard to come up with. This actually is a well-known result. Check out Sloane for some references: http://www.research.att.com/~njas/sequences/A001422 Thank you,but how can I find the proof of it? And bambaman's approach is similar to mine,but I can't continue with complicated cases,I think we couldn't just use "representations by 2 squares "

hxy09 wrote: I think it is a really nice problem.Can anybody post a solution different from the official (I privately think that the official solution is too hard to come up with ) hxy09 wrote: Thank you,but how can I find the proof of it? I found this solution which I think is not too hard to come up with if finite (but long) time (or a computer) is given. Statement 1: 1) All numbers in the interval $[u,v)$ can be represented as sum of squares of distinct positive integers $\le k$ Lemma 1: If statement 1 is true for some positive integers $k,u,v$ such that $v\ge u + (k + 1)^2$ then it is also true for $k + 1$ in place of $k$, $v + (k + 1)^2$ in place of $v$ (and u unchanged).

Lemma 2: There is such a $k$ satisfying statement 1.

Now we have a base case for statement 1, lemma 1 implies $k$ can get bigger and bigger and the interval $[u,v)$ will get bigger and bigger with no end. But numbers which cannot be represented as sum of distinct perfect squares cannot lie in that interval. So it must be less than $u$ fir the least $k$ (this $u$ is actually $129$).

hxy09 wrote: test20 wrote: This actually is a well-known result. Check out Sloane for some references: http://www.research.att.com/~njas/sequences/A001422 Thank you,but how can I find the proof of it? So did you take a look at http://www.research.att.com/~njas/sequences/A001422 ??? This page provides references to the following five sources: R. E. Dressler and T. Parker, "12,758", Math. Comp., 28 (1974), 313-314. S. Lin, Computer experiments on sequences which form integral bases, pp. 365-370 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970. Harry L. Nelson, The Partition Problem, J. Rec. Math., 20 (1988), 315-316. J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 222. R. Sprague, Ueber Zerlegungen in ungleiche Quadratzahlen, Math. Z. 51, (1948), 289-290. The paper by Dressler and Parker has the following abstract: Sprague [Math. Z. 51 (1948), 289--290; MR0027285 (10,283d)] proved that every positive integer greater than 128 can be expressed as a sum of distinct perfect squares. He also proved [ibid. 51 (1948), 466--468; MR0028892 (10,514h)] that, for every integer $n\geq 2$, there exists a largest positive integer $r_n$ that is not expressible as a sum of distinct $n$th powers (of positive integers). In the light of the first reference above, we have $r_2=128$. Unfortunately, the technique used in the second reference above is existential and does not give any idea of the size of $r_n$ for $n>2$. Our purpose here is twofold: (1) we use a computer to find explicitly the value of $r_3$ (it turns out to be 12,758), and (2) in the process we give a new quantitative proof of Sprague's theorem for $n=3$.

To Akashnil: Thank you for such a nice proof I like it very much! To test20: Thank you for the precious information

This problem is a obvious consequence of the theorem of Bohman-Froberg-Riesel.

What is the theorem of Bohman-Froberg-Riesel, please help me!

It says that, there are only $31$ numbers that cannot be expressed as the sum of distinct squares: $2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128$.

thank you ngv,can you prove it ?

I am unsure if we can avoid bashing out the small cases (of course, elementarily speaking). We begin by checking small cases and we observe that all numbers from $129$ to $324$ can be written as sums of distinct squares. (hooray!) Now, let's induct. Assume that all numbers from $129$ to $k$ are good. Furthermore, assume that $i^2\leq k+1<(i+1)^2.$ Then, observe that: $128=18^2-14^4\leq i^2-(i-4)^2<k+1-(i-4)^2\leq k$ so $k+1-(i-4)^2$ can be written as the sum of distinct squares. Furthermore, $k+1-(i-4)^2<(i+1)^2-(i-4)^2<(i-4)^2$ so those squares are different from $(i-4)^2.$ Therefore, $k+1$ can be written as the sum of distinct squares. Hence, all $N>128$ have the desired property.

Here's a different proof without bashing small cases: Let $S$ be set of all representable numbers. We want to show $| \mathbb Z_{>0} \setminus S|$ is finite. Claim 1: There is a constant $C$ such that for any $n \in \mathbb Z_{>0}$, there is a element $n' \in S$ with $0 \le n- n' \le C$. Proof: For each $n \in \mathbb Z_{>0}$, define $f(n)$ as the least non-negative integer of set $n - S$. To prove $f(1),f(2),\ldots$ is bounded. Basically, if $n$ is large, then $$f(n) \le f \left(n - \lfloor n \rfloor^2 \right)$$ where $f(0) = 0$ by convention. More particularly, there is a constant $D$ such that for all $n > D$, we have $f(n) \le f(n_0)$ for some $n_0 < n$. It follows $$C = \max(f(1),f(2),\ldots,f(D) )$$ just works. $\square$ Claim 2: There is a constant $k$ such that the set $$S \oplus (\{0,4\} \oplus \{0,8\} \oplus \cdots \oplus \{0,4k \})$$ contains all sufficiently large integers. Proof: Pick a sufficiently large $n$. Define $$\lambda(n) = \begin{cases} n \qquad &\text{if } n \equiv 0 \pmod{4} \\ n - 1^2 \qquad & \text{if } n \equiv 1 \pmod{4} \\ n - 1^2 - 3^2 \qquad & \text{if } n \equiv 2 \pmod{4} \\ n - 1^2 - 3^2 - 5^2 \qquad &\text{if } n \equiv 3 \pmod{4} \end{cases}$$ By definition $\lambda(n)$ is sufficiently large and divisible by $4$. By using only numbers divisible by $4$ in representation of $\lambda(n)$, we obtain it suffices to have the set $$S \oplus (\{0,1\} \oplus \{0,2\} \oplus \cdots \oplus \{0,k\})$$ to contain all sufficiently large numbers $\lambda(n)$. But this just follows from the facts that $$\begin{align*} f(\lambda(n)) &\le C \\ \{0,1\} \oplus \{0,2\} \oplus \cdots \oplus \{0,k\} &= \left\{ 0,1,2,\ldots,\frac{k(k+1)}{2} \right\} \end{align*}$$ This proves our claim. $\square$ We return to our main problem now. Pick a large $M$. We will in fact show the set $$T = 4S \oplus ( \{0,3^2,5^2\} \oplus \{ 0,7^2,9^2\} \oplus \cdots \oplus \{0,(4M-1)^2,(4M+1)^2 \} )$$ contains all sufficiently large numbers $n$ (above set is clearly a subset of $S$). Pick $N \in [M-3,M]$ with $n \equiv N \pmod{4}$. Let, $$n - (3^2 + 7^2 + \cdots + (4N-1)^2) = 4\alpha$$ As $\alpha$ is sufficiently large (as $M$ was fixed and $n$ was large), so by Claim 2, we obtain $$\alpha \in S \oplus (\{0,4\} \oplus \{0,8\} \oplus \cdots \oplus \{0,4N\} )$$ which then implies that $$n \in 4S \oplus ( \{3^2,5^2\} \oplus \{ 7^2,9^2\} \oplus \cdots \oplus \{(4N-1)^2,(4N+1)^2 \} )$$ completing the proof. $\blacksquare$

Can you explain $$f(n) \le f \left(n - \lfloor n \rfloor^2 \right)$$ ?

Say $k^2 \le n < (k+1)^2$. So if you write $n = k^2 + (n-k^2)$, where $n - k^2 < k^2$ since $n$ large, so one directly gets desired conclusion. Basically, all numbers while writing a number $\le n- k^2$ will be $< k^2$, so we don't need to worry about repetition. After that, $f(n) \le f(n-k^2)$ pretty much follows by definition.

ngv wrote: It says that, there are only $31$ numbers that cannot be expressed as the sum of distinct squares: $2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128$. Where do I read more about this theorem?, I can't find a reliable source on searching

orl wrote: Show that the set of positive integers that cannot be represented as a sum of distinct perfect squares is finite. good number: any number who can be represented as sum of distinct squares Claim: if n=4k+2 and k>7 then n is a good number and k is odd if and only if we used 4 for making n prove by induction : it's obvious that if we prove statement for even k then the statement is proven the we could check n for any k less than 16 now we need to prove if claim is right for any k with is 16<k<a the claim is right for k=a now there are to cases case1: n-(biggest even square less than n)>22 now we put biggest even square less than n and by induction hypothesis the claim is proved case2: n-(biggest even square less than n) <26 now consider b such that b is biggest even square less than biggest even square less than n now put b and use induction hypothesis consideration: it's easy to check after adding b number is less than half of it therefore we wont use b again same argument could be used for case 1 thus claim is proved Claim 2 : if n=4k+1 then n is a good number prove by induction :it's easy to check claim for k less than 17 therefor it's enough to prove if the statement is right for any k such that 16<k<a is right then claim is right for k=a now consider b such that b is closest even square to n now put b and by induction hypothesis the claim is proved notice that we have same consideration with claim 1 Claim 3 : if n=4k+3 and k>30 then n is a good number Case 1 : n-(biggest odd square less than n )>22 put biggest odd square less than n and use claim 1 Case 2 : n-(biggest odd square less than n)<26 let c be biggest odd square less than biggest odd square less than n now put c and use claim 1 and claim is proved notice we have same consideration with two other cases Claim 4 : if n=4k such that k>900 then n is a good number Case 1 : n-(biggest odd square less than n)>123 then we put biggest odd square less than n and use claim 3 Case2: n-(biggest odd square less than n)<119 define d such that d is biggest odd square less than biggest odd square less than n now put d and use claim 3 and claim is proved notice we have same consideration with other 3 claims now by what we proved we now every number more than 3600 is good number with means number of number who are not good is at most 3600