Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL).
In the task, we have defined square factorisation as representation a positive natural number as sum of squares of different positive, integer numbers. For example 30 has two representations, 9 or 5 has only one and 8 doesn't have any:
$$
30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2 \\
5 = 1^2 + 2^2 \\
9 = 3^2
$$
And function $k$ returns the smallest of the largest squares from all representations.
For above example we have:
$$k(30) = \min\lbrace \max\lbrace1, 2, 5 \rbrace, \max\lbrace1,2,3,4\rbrace\rbrace= \min\lbrace5,4\rbrace = 4 \\
k(5) = \min\lbrace\max\lbrace1, 2\rbrace\rbrace = 2 \\
k(9) = \min\lbrace\max\lbrace3\rbrace\rbrace = 3
$$
We assume $k(x) = \infty^{+}$, if the factorisation for x is not possible.
$$k(8) = \infty^{+}$$
We call number x inter-grown if $\left(\exists y \in \mathbb{Z}_{+}\right)\left(y > x \wedge k(y) < k(x) \right) $. For example $k(378) = 12$, $k(380) = 10$, so 378 is inter-grown ($378 < 380~\wedge~k(378) > k(380)$). 8 is too: $(8 < 9 \wedge k(8) > k(9))$
The question was two-part. First was the value of $k(n)$, second was: How many exists smaller than n numbers, witch are inter-grown?
Restriction for $n$ was weak. $n \in \mathbb{Z}_{+} \wedge n \leq 10^{18}$.
I made this task absolutely non-mathematically. I wrote the program in python, witch provides me lot of information. I noticed depending and checked for lot examples (using computer, of course). Then I was thinking about proof. In fact I wrote something looks like proof, but I'm not satisfied. It's confusing, illegible and I'm not sure if it's correct. Fortunately we don't have to make proofs.
However, after contest ended I began to wonder, how should look simple and clear proof. And I ask about evidence of correctness first and second part of question. I ask for two things in one question, cause it's strongly related (at least in my attempt). All my knowledge I put below. A large part of it considers the case of sufficiently large $n$, cause it was easer. Small $n$ I calculated separately and placed in the table.
Inter-grown
-
The number of indecomposable numbers is finite, and it's well known fact. About others, we can read less.
-
On the basis of program, from 522 inter-grown numbers occur regularly in groups. Each contains 31 numbers, and there are located on same places, as indecomposable numbers. So
2, 3, 6, 7,..., if the group starts two numbers before fist inter-grown. I assume the begin of group is first inter-grown, so there are located on0, 1, 4, 5,...positions in group.I believe, the groups are for $n$ smaller than 522 and they overlap, but it doesn't change anything.
-
Groups started on positions
691, 887, 1112, 1368,..., distances between them are196, 225, 256,..., differences here are29, 31, 33, 35, .... Och! It's arithmetic progression. So, it's easy to calculate beginning of nth group. I believe, I don't have to write transformation here. We obtain that, nth group starts from$$887+\frac{1261 n}{6}+\frac{29 n^2}{2}+\frac{n^3}{3} \wedge n \in \mathbb{N}$$
We can calculate different between nth and next group. If I didn't make mistake it's $(n+14)^2$.
Value of $k(n)$
-
$k(n)$ can't be smaller than smallest x, for witch $\sum_{i=1}^{x} i^{2} = \frac{x^3}{3} + \frac{x^2}{2} + \frac{x}{6} \geq n$. But it's obvious.
-
I have observed, if number isn't inter-grown, and he is big enough ($n > 522$ is sufficient), that is the smallest number, witch satisfies the inequality of the preceding paragraph…
-
… otherwise, it's that number increased by one.
Clear is that all may be calculated in $O(lg~n)$ time. It's magnificent!
Naturally it's just calculations on small data, without any proof, and above patterns (witch are in fact correct) are thesis. If someone has an clear and pretty idea, how should look (proof!) I will be grateful for description.
Best Answer
Yesterday an official delineation of solution to this task appeared (PL). I am disappointed that it's much slower than above. However, it presents me a new point of view of the problem. In conjunction with it, my idea is quite nice.
Main thing in this proof is fact, that set of indecomposable numbers is finite. Accept this as a well-known fact, or if you don't want, look here.
Helpful in understanding, it may be observation, if $n$ isn't inter-grown, and $k(n) = x$ then $n + (x+1)^2$ isn't inter-grown.
Inter-grown
First observation should be, than $n = \sum_{i=1}^{x}{i^2}$ isn't inter-grown. $n$ uses all squares not larger than $x^2$, so if $n' > n$ it's impossible to present $n'$ using only lower, than $x^2$. Emphasize that $k(\sum_{i=1}^{x}{i^2}) = x$. Now we should take advantage of the observation from question. If $x$ is the smallest number, witch satisfies the inequality $\sum_{i=1}^{x} i^2 \geq n$, then $k(n) \geq x$. So, we can predicate, that $n$ is inter-grown, if $k(n) > x$.
Value of $k(n)$
Now, let's look at it from other side. Let $n' = \left(\sum_{i=1}^{x} i^2\right) - n$. In this case we can present $n$ as sum of different squares (not bigger than $x^2$) if and only if $n'$ isn't indecomposable. Simply subtract $\left(\sum_{i=1}^{x} i^2\right) - n'$, if $n'$ is indecomposable it's impossible. That's obvious. If $n'$ is indecomposable we have to check $n'' = \left(\sum_{i=1}^{x+1} i^2\right) - n$ in the same way. We need to check, until we find decomposable $n^{*}$. But, wait! The greatest indecomposable number is 128, so $(x+1)^2 > 128 \wedge n'' = n' + (x+1)^2$ guarantees that $n''$ is decomposable! So from sufficiently large $n$, $k(n)=x~~\dot{\vee}~~k(n) = x+1$.
It's not hard to see, if and only if $n'$ is indecomposable, $n$ is inter-grown.
Counting isn't hard too. As expected, we have to remember for small $n$, groups can overlap and we have to count it by computer. After we can just add 31 with each subsequent square. The last group not necessarily add 31, cause not all elements have to be in, but they occur on a regular relative position ($n' \in \lbrace 2, 3, 6, 7, 8, 11, 12, 15,..., 128\rbrace$, so it's obvious, why.) and it's really easy to count. I don't think I have to describe it.