6
$\begingroup$

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 on 0, 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 are 196, 225, 256,..., differences here are 29, 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.

$\endgroup$
  • $\begingroup$ You need the formula gives the solution to this equation? $$x^2+y^2+z^2=a^2+b^2+c^2+q^2$$ $\endgroup$ – individ Nov 5 '14 at 4:34
  • $\begingroup$ @individ: I believe no. I mean, I don't know how it could be helpful, but maybe I can't see something, what you can. $\endgroup$ – Tacet Nov 5 '14 at 4:49
  • $\begingroup$ If You don't need a formula then what you are looking for? So it is possible figures to go through indefinitely. $\endgroup$ – individ Nov 5 '14 at 4:51
  • $\begingroup$ I did not understand. Need a formula or not? $\endgroup$ – individ Nov 5 '14 at 5:41
  • 1
    $\begingroup$ No. I have equations. I can find result in $O(lg~n)$ time, so it's very good. But I'm looking for simple evidence of correctness my equations, witch are correct. Exactly about positions in group of inter-grown numbers, such groups even exist... $\endgroup$ – Tacet Nov 5 '14 at 6:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.