dangerousliri wrote: Denote $\mathbb{Z}_{>0}=\{1,2,3,...\}$ the set of all positive integers. Determine all functions $f:\mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$ such that, for each positive integer $n$, $\hspace{1cm}i) \sum_{k=1}^{n}$ is a perfect square, and $\vspace{0.1cm}$ $\hspace{1cm}ii) f(n)$ divides $n^3$. Proposed by Dorlir Ahmeti, Albania what is in the summation? @ below Ok thanks @above please make the desired changes

$f(k)$${}$

DapperPeppermint wrote: dangerousliri wrote: Denote $\mathbb{Z}_{>0}=\{1,2,3,...\}$ the set of all positive integers. Determine all functions $f:\mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$ such that, for each positive integer $n$, $\hspace{1cm}i) \sum_{k=1}^{n}$ is a perfect square, and $\vspace{0.1cm}$ $\hspace{1cm}ii) f(n)$ divides $n^3$. Proposed by Dorlir Ahmeti, Albania what is in the summation? @ below Ok thanks @above please make the desired changes Fixed. Sorry.

Wrong solution. Ignore this message.

EpicNumberTheory wrote: Since $f(n)$ divides $n^3$, we can get that $f(n)=an^3$ for some positive integer $a$. Then by condition $ii)$ we have $\sum_{k=1}^{n} an^3=a(n(n+1)^2/4)$ is a perfect square. Since $(n(n+1)^2/4)$ is a perfect square. We get that $a=1$ and hence $f(n)=n^3$ is the only solution. Wrong solution.

Now is it correct?

no.${}{}{}{}$

Fantastic problem, as always from Dorlir! I claim $f(n)=n^3$ for every $n\in\mathbb{N}$, shown as follows. Note that $f(1)=1$, and since $1+f(2)$ is a square and $f(2)\mid 8$, it follows $f(2)=2$. Having established these base cases, we now induct on $n$: suppose $f(i)=i^3$ for $1\le i\le n$. Now, we inspect $f(n+1)$. Using the sum condition, it follows there is a $k$ such that \[ \frac{n^2(n+1)^2}{4} + f(n+1)=\left(\frac{n(n+1)}{2}+k\right)^2, \]thus $f(n+1) = k(n(n+1)+k)$. For some $k\ge 1$. Note also that $k\le n+1$, as otherwise this quantity exceeds $(n+1)^3$. The goal is to show $k=n+1$. Assume $k\le n$. Now note that if $p\mid k$ is a prime, then $p\mid n+1$, as well. I now claim that $k\mid (n+1)^2$. For any prime $p\mid k$, if $v_p(k)\le v_p(n+1)$, we are done. Else, note that $v_p(k(n(n+1)+k)) = v_p(k)+v_p(n+1)\le 3v_p(n+1)$, hence $v_p(k)\le 2v_p(n+1)$, hence the claim. Equipped with this, set now $k =(n+1)^2/i$, where $i\ge n+1$ (since $k\le n+1$). With this, \[ k(n(n+1)+k) = \frac{(n+1)^2}{i} \left(n(n+1) + \frac{(n+1)^2}{i}\right). \]Inserting this, it follows that $ni+n+1\mid i^2$. Now, $ni+n+1\mid n^2i^2 + n^2i+ni$, and $ni+n+1\mid n^2i^2$. Thus, $ni+n+1\mid n^2i+ni$. Since $ni+n+1$ is coprime to $n$, it follows $ni+n+1\mid ni+i$. Hence, $ni+n+1\mid i-(n+1)$. Now, if $i>n+1$, then $ni+n+1\le i-n-1$, that is $ni+2(n+1)\le i$ gives a clear contradiction since $n>2$. Hence, $i=n+1$, which is precisely the desired conclusion.

EpicNumberTheory wrote: Now is it correct? it says that f(n) divides n^3 not the opposite

EpicNumberTheory wrote: Now is it correct? Please read the question properly since it is $f(n)$ divides $n^3$ and not the otherwise. Even if it was otherwise it means $f(n)=g(n)\cdot n^3$ and not $f(n)=an^3$. Please check when you post a solution since it will lose the interest of what we are talking about so please don't do it next time.

dangerousliri wrote: Denote $\mathbb{Z}_{>0}=\{1,2,3,...\}$ the set of all positive integers. Determine all functions $f:\mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$ such that, for each positive integer $n$, $\hspace{1cm}i) \sum_{k=1}^{n}f(k)$ is a perfect square, and $\vspace{0.1cm}$ $\hspace{1cm}ii) f(n)$ divides $n^3$. Proposed by Dorlir Ahmeti, Albania one can easily get $f(1)=1,f(2)=8$ . now we induct on $n$ and prove $f(n)=n^3$ since $f(n+1)|(n+1)^3$ and $f(n+1)+(\frac{(n+1)n}{2})^2=k^2$ let $k=a+\frac{(n+1)n}{2}$ so $f(n+1)=a(a+(n+1)n)$ and also $a(a+(n+1)n)|(n+1)^3$ . as $a+n(n+1)|n^3(n+1)^3$ we have $a+n(n+1)|a^3$ as well and $a(a+(n+1)n)|(n+1)^3$ if $a=n+1$ we get our desired information. if not. then clearly $a<n+1$ . let $a=n+1-b$ so $(n+1)^2-b|(n+1)^3$ so $(n+1)^2-b|b(n+1)$ this gives $\frac{(n+1)^2}{n+2} \le b$ so $b>n$ but also $1 \le a = n+1-b $ which gives us a contradiction. so $a=n+1$ and $f(n)=n^3$ for all possitive integers. . . verry nice problem

I like this problem! I claim that our answer is $f(n) = n^3$ for all positive integers $n$. We shall strong induct; this is clearly the case for $n = 1$, so our base case is complete. For the inductive step, suppose that $f(i) = i^2$ for all $i \in [1, k-1]$ for some $k$. We wish to show that $f(k) = k^3$. Indeed, we want\[f(1) + f(2) + \ldots + f(k) = (1^3 + \ldots (k-1)^3) + f(k) = \binom{k}{2}^2 + f(k) = m^2\]for some positive integer $m > \tbinom{k}{2}$. Write $m = \tbinom{k}{2} + \ell$ for some positive integer $\ell$. We see that\[f(k) = m^2 - \binom{k}{2}^2 = \ell(k(k-1) + \ell) = \ell(k^2 - k + \ell)\]which must divide $k^3$. This means that $\ell(k^2 - k + \ell)$ must also divide $k^3\ell - k\ell(k^2 - k + \ell) = k^2\ell - k\ell^2$ which turns into\[k^2 - k + \ell \mid k^2 - k\ell\]but clearly $k^2 - k + \ell > k^2 - k\ell$, always. Also, note that $\ell \leq k$, or else $f(k) > k^3$, which is not possible. Hence, $k^2 - k\ell$ remains nonnegative and therefore must be $0$. Thus, $\ell = k$ is the only option, and this does indeed give $f(k) = k^3$, completing our inductive step. $\blacksquare$

Isn't this a bit too easy? Or am I making a mistake somewhere? The answer is $f(n) = n^3$. We proceed by induction. Clearly $f(1) = 1$. So suppose that for some $n, \sum_{i=1}^{n-1}f(i) = \sum_{i=1}^{n-1}i^3 = \frac{n^2(n-1)^2}{4}$. Now let $\sum_{i=1}^{n}f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 \implies f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 - \frac{n^2(n-1)^2}{4} = k(n^2 - n + k)$. It is easy to see that $k \leq n$. We know $k(n^2 - n + k) \mid n^3 \implies n^2 - n + k \mid n^3 \implies n^2 - n + k \mid n^3 - n(n^2 - n + k) = n^2 - nk$. But since $n^2 - n + k$ is larger than $n^2 - nk$ and $n^2 - nk$ is at least $0$, it means that $n^2 - nk = 0 \implies k = n$. So $f(n) = n(n^2 - n + n) = n^3$ and our induction step is complete.

green_leaf wrote: Isn't this a bit too easy? Or am I making a mistake somewhere? The answer is $f(n) = n^3$. We proceed by induction. Clearly $f(1) = 1$. So suppose that for some $n, \sum_{i=1}^{n-1}f(i) = \sum_{i=1}^{n-1}i^3 = \frac{n^2(n-1)^2}{4}$. Now let $\sum_{i=1}^{n}f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 \implies f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 - \frac{n^2(n-1)^2}{4} = k(n^2 - n + k)$. It is easy to see that $k \leq n$. We know $k(n^2 - n + k) \mid n^3 \implies n^2 - n + k \mid n^3 \implies n^2 - n + k \mid n^3 - n(n^2 - n + k) = n^2 - nk$. But since $n^2 - n + k$ is larger than $n^2 - nk$ and $n^2 - nk$ is at least $0$, it means that $n^2 - nk = 0 \implies k = n$. So $f(n) = n(n^2 - n + n) = n^3$ and our induction step is complete. This is almost same solution as mine. When I did propose I thought it would be P1 if it is accepted. What I'm more surprised is that it was consider as Algebra and not as Number Theory which I think is strange.

@dangerousliri It's a great problem! Congratulations!

dangerousliri wrote: This is almost same solution as mine. When I did propose I thought it would be P1 if it is accepted. What I'm more surprised is that it was consider as Algebra and not as Number Theory which I think is strange. This is definitely Number theory. The most straightforward approach is induction followed by some divisibility, there is no reason for this to be considered as Algebra.

dangerousliri wrote: green_leaf wrote: Isn't this a bit too easy? Or am I making a mistake somewhere? The answer is $f(n) = n^3$. We proceed by induction. Clearly $f(1) = 1$. So suppose that for some $n, \sum_{i=1}^{n-1}f(i) = \sum_{i=1}^{n-1}i^3 = \frac{n^2(n-1)^2}{4}$. Now let $\sum_{i=1}^{n}f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 \implies f(n) = \left( \frac{n(n-1)}{2} + k \right)^2 - \frac{n^2(n-1)^2}{4} = k(n^2 - n + k)$. It is easy to see that $k \leq n$. We know $k(n^2 - n + k) \mid n^3 \implies n^2 - n + k \mid n^3 \implies n^2 - n + k \mid n^3 - n(n^2 - n + k) = n^2 - nk$. But since $n^2 - n + k$ is larger than $n^2 - nk$ and $n^2 - nk$ is at least $0$, it means that $n^2 - nk = 0 \implies k = n$. So $f(n) = n(n^2 - n + n) = n^3$ and our induction step is complete. This is almost same solution as mine. When I did propose I thought it would be P1 if it is accepted. What I'm more surprised is that it was consider as Algebra and not as Number Theory which I think is strange. Sometimes when PSC don't like problems from one subject they put problem from other subject and classify as subject they need. One of the examples is IMO 2014 P5 being number theory.

We will prove that $f(n) =n^3$ by induction on $n$. Base case is trivial. Now suppose that $f(s)=s^3$ for $s<=n$. We will prove it for $n+1$. Using the formula for sum of cubes, we have that $n^2(n+1)^2/4+f(n+1)=(n(n+1)/2+k)^2$ Equivalently, we have that $f(n+1)=n^2k+nk+k^2=k(n^2+n+k)/(n+1)^3$. Hence $n^2+n+k/n^3+3n^+3n+1$. Thus $n^2+n+k/n^3+3n^2+3n+1-n^3-n^2-kn=2n^2+3n-kn+1$. Therefore $n^2+n+k/2n^2+3n-kn+1-2n^2-2n-2k=-(k+1)n+1$. Hence $n^2+n+k<=(k+1)n-1$, which gives easily that $k>=(n+1)$. But if $k>n+1$ then $k(n^2+n+k)>(n+1)^3$, absurd. Therefore we have equality and this finishes the Inductive Step.

My solution is using induction and square bounding. Maybe a bit easy for BMO P2, but a very beautiful problem in my opinion

EDIT: Thanks to dangerousliri for pointing out a mistake that has now been corrected. I claim that $f(n) = n^3 \ \ \forall n \in \mathbb{N}$. Let's prove it by induction. $f(1) \mid 1 \implies f(1)=1$. Suppose $$\sum_{i=1}^k f(i) = \sum_{i=1}^k i^3 = \left( \frac{k(k+1)}{2} \right)^2$$Then $f(k+1) = \frac{(k+1)^3}{b}$. We want to show $b=1$. AFSOC $b \ne 1$. Note $\left( \frac{k(k+1)}{2} \right)^2 + \frac{(k+1)^3}{b} = (k+1)^2 \left( \frac{k^2}{4} + \frac{k+1}{b}\right)$. So $k^2 +\frac{4k+4}{b}$ must be a rational square. Write $k^2 +\frac{4k+4}{b} =\frac{p^2}{q^2}$ where $p,q$ are coprime. Then $q^2(bk^2+4k+4)=bp^2$. Hence $q^2 \mid b \implies b=lq^2 \implies l(qk)^2 + 4k+4 = lp^2$. But,$$l(qk)^2 < l(qk)^2+4k+4 < l(qk+2)^2$$So $l(qk)^2+4k+4 = l(qk+1)^2 \implies l = \frac{4k+4}{2qk+1}$. If $q>2$ then $1>l \not\in \mathbb{N}$. And if $q=1,2$, $l \not\in \mathbb{N}$. Hence $b=1$ and thus $f(k+1) = (k+1)^3$ completing our induction.

mastermind.hk16 wrote: I claim that $f(n) = n^3 \ \ \forall n \in \mathbb{N}$. Let's prove it by induction. $f(1) \mid 1 \implies f(1)=1$. Suppose $$\sum_{i=1}^k f(i) = \sum_{i=1}^k i^3 = \left( \frac{k(k+1)}{2} \right)^2$$Then $f(k+1) = \frac{(k+1)^3}{b}$. We want to show $b=1$. AFSOC $b \ne 1$. Note $\left( \frac{k(k+1)}{2} \right)^2 + \frac{(k+1)^3}{b} = (k+1)^2 \left( \frac{k^2}{4} + \frac{k+1}{b}\right)$. So $k^2 +\frac{4k+4}{b}$ must be a perfect square. But note $$k^2 < k^2+ \frac{4k+4}{b} < k^2 + 4k+4 = (k+2)^2$$So $k^2 + \frac{4k+4}{b} = (k+1)^2 \implies b = \frac{2k+1}{4k+4}$. But $\frac{2k+1}{4k+4} \not\in \mathbb{N}$. Contradiction. Hence $b=1$ and thus $f(k+1) = (k+1)^3$ completing our induction. It is not correct solution but you are very close. The part $$k^2 < k^2+ \frac{4k+4}{b} < k^2 + 4k+4 = (k+2)^2.$$doesn't imply $k^2+\frac{4k+4}{b}$ should be a perfect square of an integer, it could be a perfect square of a rational number. But it can be fixed easily just look more carefully.

dangerousliri wrote: mastermind.hk16 wrote: I claim that $f(n) = n^3 \ \ \forall n \in \mathbb{N}$. Let's prove it by induction. $f(1) \mid 1 \implies f(1)=1$. Suppose $$\sum_{i=1}^k f(i) = \sum_{i=1}^k i^3 = \left( \frac{k(k+1)}{2} \right)^2$$Then $f(k+1) = \frac{(k+1)^3}{b}$. We want to show $b=1$. AFSOC $b \ne 1$. Note $\left( \frac{k(k+1)}{2} \right)^2 + \frac{(k+1)^3}{b} = (k+1)^2 \left( \frac{k^2}{4} + \frac{k+1}{b}\right)$. So $k^2 +\frac{4k+4}{b}$ must be a perfect square. But note $$k^2 < k^2+ \frac{4k+4}{b} < k^2 + 4k+4 = (k+2)^2$$So $k^2 + \frac{4k+4}{b} = (k+1)^2 \implies b = \frac{2k+1}{4k+4}$. But $\frac{2k+1}{4k+4} \not\in \mathbb{N}$. Contradiction. Hence $b=1$ and thus $f(k+1) = (k+1)^3$ completing our induction. It is not correct solution but you are very close. The part $$k^2 < k^2+ \frac{4k+4}{b} < k^2 + 4k+4 = (k+2)^2.$$doesn't imply $k^2+\frac{4k+4}{b}$ should be a perfect square of an integer, it could be a perfect square of a rational number. But it can be fixed easily just look more carefully. Thank you for pointing this out. Perhaps, this shall fix it; $k^2 +\frac{4k+4}{b}$ must be a rational square. Write $k^2 +\frac{4k+4}{b} =\frac{p^2}{q^2}$ where $p,q$ are coprime. Then $q^2(bk^2+4k+4)=bp^2$. Hence $q^2 \mid b \implies b=lq^2 \implies l(qk)^2 + 4k+4 = lp^2$. But, $$l(qk)^2 < l(qk)^2+4k+4 < l(qk+2)^2$$So $l(qk)^2+4k+4 = l(qk+1)^2 \implies l = \frac{4k+4}{2qk+1}$. If $q>2$ then $1>l \not \in \mathbb{N}$. And if $q=1,2$, $l \not \in \mathbb{N}$. Hence $b=1$ and thus $f(k+1) = (k+1)^3$ completing our induction.

Define $g:\mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ such that $\sum_{k=1}^{n}{f(k)}=g(n)^2$ for all $n$. As $f(n) \leq n^3$: $$g(n)^2 \leq \sum_{k=1}^{n}{k^3}=\left(\frac{n(n+1)}{2}\right)^2 \Rightarrow g(n) \leq \frac{n(n+1)}{2} \quad \quad \left(\blacktriangle \right)$$Also $g$ is striclty increasing so $g(n) \geq n$ for all $n$. Now let $n=p$ be prime. As $f(p) \vert p^3$ we have $f(p) \in \{1,p,p^2,p^3\}$. As: $$f(p)=g(p)^2-g(p-1)^2=\left(g(p)-g(p-1)\right)\left(g(p)+g(p-1)\right)$$and the second bracket is at least $p+p-1>p$ we know $f(p) \in \{p^2,p^3\}$. If $f(p)=p^2$ we would have: $$\begin{cases} g(p)-g(p-1)=1 \\ g(p)+g(p-1)=p^2 \end{cases} \Rightarrow g(p-1)=\frac{p^2-1}{2}$$but $\frac{p^2-1}{2}>\frac{p(p-1)}{2}$ so this contradicts $(\blacktriangle)$. We therfore have $f(p)=p^3$. We have two possibles cases: $$\begin{cases} g(p)-g(p-1)=1 \\ g(p)+g(p-1)=p^3 \end{cases} \Rightarrow g(p)=\frac{p^3+1}{2}$$$$\begin{cases} g(p)-g(p-1)=p \\ g(p)+g(p-1)=p^2 \end{cases} \Rightarrow g(p)=\frac{p(p+1)}{2}$$Notice that the former case can't happen because $\frac{p^3+1}{2}>\frac{p(p+1)}{2}$ contradicting $(\blacktriangle)$. So in fact $g(p)=\frac{p(p+1)}{2}$. We now have: $$\left(\frac{p(p-1)}{2}\right)^2=g(p)^2=\sum_{k=1}^{p}{f(k)} \leq \sum_{k=1}^{p}{k^3}=\left(\frac{p(p-1)}{2}\right)^2$$so we have equality throughout forcing $f(k)=k$ for all $1 \leq k \leq p$. As $p$ was an arbitrary prime, it follows $f(n)=n$ for all $n$ which clearly works.

As in previous solutions, we induct on $n$, and considering $f(k)=k^{3}$ for $k=1,2,...,n$, we get $f(n+1)=q(q+n(n+1))$, where $1 \le q \le n+1$. Then let $a=\frac{(n+1)^{3}}{q(q+n(n+1))} \in \mathbb{Z}^{*}$ and $d=(q,n+1)$. We write $q=dq_{0},n+1=db$ with $(q_{0},b)=1$. We get $db^{3}=aq_{0}(q_{0}+nb)$. Since $(q_{0},b)=1$, we have $q_{0}|d$ so $\alpha = \frac{d}{q_{0}} \in \mathbb{Z}$ and $\alpha \le \frac{n+1}{1}=n+1$ because $d|n+1$. Since $(q_{0},b)=1$, we have $(b^{3},q_{0})=1$ and $(b^{3},q_{0}+nb)=1$ so $b^{3}|a$. Then $\beta = \frac{a}{b^{3}} \in \mathbb{Z}^{*}$. Finally we have $\alpha = \beta (q_{0}+nb) \ge \beta (1+n)$, and from $\alpha \le n+1$ we get $\beta \le 1$, so $\beta = 1$ and $a=b^{3}$. This means we have equality all over, so $b=1$ and $a=1$, so $f(n+1)=(n+1)^{3}$.

The only working function is $f(x)=x^3,$ it's easy to check that it works. We proceed via induction on $n$ and simultaneoulsy a contradiction. Clearly $f(1)=1$ and that $f(2)=2^3$. Henceforth, assume $f(i)=i^3,~\forall i\le m$. Now, notice that $$\left(\frac{m(m+1)}{2}\right)^2<\underbrace{\sum_{k=1}^{m+1} f(k)}_{\text{A}~\text{perfect}~\text{square}}\le \left(\frac{(m+1)(m+2)}{2}\right)^2=\left(\frac{m(m+1)}{2}+m+1 \right)^2$$Now assume for contrary that $$\sum_{k=1}^{m+1}f(k)=\left(\tfrac{m(m+1)}{2}+\ell \right)^2~\text{for}~1 \le\ell < m+1$$which gives, $f(m+1)=\ell^2+m(m+1)\ell \mid (m+1)^3$. Assume $\gcd (\ell,m+1)=d,$ and $\ell=dr$ and $m+1=ds$ by which we get $r^2+s(ds-1)r \mid ds^3$ and $r<s$. Since $\gcd(s,r)=1$ we get $r \mid d,$ assume $d=kr$ to get $$r+s(ksr-1) \mid ks^3 \implies \underbrace{r+s(ksr-1)}_{>0} \mid \underbrace{s^2-sr}_{>0} \implies r+s(ksr-1) \le s^2-sr \implies s^2(1-kr) \ge sr+r-s >0$$Contradiction! So we deduce $\ell=m+1,$ which inturns gives $f(m+1)=(m+1)^3,$ completing the inductive hypothesis and thus finishing the problem. $\blacksquare$

I hope this solution works. We proceed by induction on $n$. It is easy to check that $f(1) = 1$ and $f(2) = 2^3$. Assume that $f(l) =l^3, \forall l \le n$. We will prove that $f(n+1) =(n+1)^3$. Observe that clearly we have that $f(l) \le l^3, \forall l \in \mathbb{N}$. We note that: $$ f(1) + f(2) + \ldots f(n) =( \frac{n(n+1)}{2} )^2 $$Therefore: $$(\frac{n(n+1)}{2})^2 <f(1) + f(2) + \ldots +f(n+1) \le (\frac{(n+1)(n+2)}{2})^2 $$This implies that $f(1) +f(2) + \ldots +f(n+1) = (\frac{(n(n+1)}{2} +k)^2$ with $1 \le k \le n+1$ . Therefore: $$ f(n+1) =(\frac{(n(n+1)}{2} +k)^2 -( \frac{(n(n+1)}{2})^2 = kn(n+1) + k^2 $$It is given that $f(n+1) \mid (n+1)^3$ and this yields to: \begin{align*} kn(n+1) + k^2 \mid (n+1)^3 \\ kn(n+1) + k^2 \mid (n+1)^2(kn(n+1) +k^2) - kn(n+1)^3 \\ kn(n+1) + k^2 \mid k^2(n+1)^2 \\ kn(n+1) + k^2 \mid k^2n^2 + 2k^2n +k^2 - k(kn(n+1)+k^2) \\ kn(n+1) + k^2 \mid k^2n +k^2 - k^3 \\ n(n+1) + k \mid kn+k -k^2 \\ n(n+1)+k \mid k(n +1 -k ) \end{align*}Now we will prove that $n(n+1)+k > k(n+1-k)$. This is equivalent to: $$ n^2+n+ k \ge kn +k-k^2 \implies n^2+n +k^2 >(n+1)n \ge kn $$Thus we must have $k(n+1-k) =0 \implies k= n+1 $ and consequently $f(n+1) = (n+1)^3 $ as desired.

dangerousliri wrote: Denote $\mathbb{Z}_{>0}=\{1,2,3,...\}$ the set of all positive integers. Determine all functions $f:\mathbb{Z}_{>0}\rightarrow \mathbb{Z}_{>0}$ such that, for each positive integer $n$, $\hspace{1cm}i) \sum_{k=1}^{n}f(k)$ is a perfect square, and $\vspace{0.1cm}$ $\hspace{1cm}ii) f(n)$ divides $n^3$. Proposed by Dorlir Ahmeti, Albania Hi Dorlir Ahmeti,Nice problem! My Solution $f(1)\mid 1\implies f(1)=1$ $f(2)\mid 8$ and $1+f(2)=m^2$.Then $f(2)=8$ $f(1)=1^3,f(2)=2^3,.....,f(n)=n^3$ $induction \implies 1^3+2^3+...+n^3+f(n+1)=(\frac{n(n+1)}{2}+l)^2,f(n+1)\mid (n+1)^3$ $f(n+1)=(\frac{n(n+1)}{2}+l)^2-(\frac{n(n+1)}{2})^2=l(l+n(n+1))$ Then $l(l+n(n+1))\mid (n+1)^3\implies l\leq n+1$ $gcd(l,n+1)=t\implies l=tl_1,n+1=tk,gcd(l_1,k)=1\implies l_1\leq k \blacksquare$ $l_1(l_1+(tk-1)k)=tk^3\implies k\mid l_1\implies k\leq l_1 \blacksquare$ $l_1\leq k$ and $l_1\geq k$$\implies l_1=k=1\implies f(n+1)=n+1$

Nothing special, just induct and use bounds on divisibility condition. And of course it's not number theory, the only number theoretical part is using the divisibility condition to obtain a bound. More concretely, we have by induction that $f(n)=r(n^2-n)+r^2$ for some $r$. This implies $n^2-n+r$ divides $n^3$, which means $n^2-n+r$ divides $n^2-nr$. If $r<n$, then $n^2-n+r>n^2-nr>0$, a contradiction. If $r>n$, then $r(n^2-n)+r^2>n^3$, a contradiction. Hence $r=n$ and $f(n)=n^3$, which completes the step of induction.

Does this work?

Nice and easy - posting for storage.

We claim that $f(n) = n^3$ is the only solution. Firstly note that $n^3 = f(n)|n^3$, and that \[\sum_{k=1}^n f(k) = 1^3+\cdots+n^3 = \left(\frac{n(n+1)}{2}\right)^2\]then we proceed by induction to prove that it's the only solution. Base Case: $n = 1$, notice that $f(1)|1$, thus $f(1) = 1$. Assume that for some positive integer $n$, $f(k) = k^3$ for all $1\leq k\leq n$. For $n+1$, we have that $f(n+1)|(n+1)^3$ and that $f(n+1)+\left(\frac{n(n+1)}{2}\right)^2$ is a perfect square. Then notice that \[f(n+1)+\left(\frac{n(n+1)}{2}\right)^2\leq (n+1)^3+\left(\frac{n(n+1)}{2}\right)^2= \left(\frac{(n+1)(n+2)}{2}\right)^2\]Then we can write \[f(n+1) = \left(\frac{n(n+1)}{2}+k\right)^2-\left(\frac{n(n+1)}{2}\right)^2\]for some integer $1 \leq k\leq n+1$. Thus \[k(k+n(n+1))|(n+1)^3\]\begin{claim*} The only integer $k$ with $1\leq k\leq n+1$ that satisfies \[k(k+n(n+1))|(n+1)^3\]is $k = n+1$. \end{claim*} \begin{proof} Let $d:= \gcd(k,n+1)$, and write $k = pd$, $n+1 = qd$. We have \[pd(pd+(qd-1)qd)|q^3d^3\implies p(q^2d-q+p)|q^3d\]However notice that \[\gcd(p,q^3) = 1\]since $\gcd(p,q) = 1$. Thus we have $p|d$, and let $d = pr$. Then we have \[p(q^2pr-q+p)|q^3pr\implies q^2pr-q+p|q^3r\]also since \[\gcd(q^2pr-q+p,q^3) = \gcd(q(qpr-1)+p,q^3) = 1\]since $\gcd(p,q) = 1$. Thus we must have \[q^2pr-q+p|r\implies r\geq q^2pr-q+p\geq q^2r-q+1\]\[\implies r(1-q^2)\geq 1-q\]and if $q\neq 1$, we have \[r\leq \frac{1-q}{1-q^2} = \frac{1}{1+q}\leq \frac{1}{2}\]which is impossible. Thus $q = 1$, and since $q\geq p$ by condition, $p = 1$. This implies that $k = n+1$, and since \[(n+1)(n+1)^2 = (n+1)^3|(n+1)^3\]we are done.

Really nice The answer is $f(n)=n^3$, it is easy to verify that this indeed satisfies both the given conditions. By manual checking we get that $f(1)=1$, $f(2)=8$ and $f(3)=27$. Perform strong induction, assume $f(n)=n$ for $1 \le n \le a$. $$\sum_{i=1}^{a+1}f(i) = \left(\frac{a(a+1)}{2}\right)^2 + f(a+1) = \text{Perfect Square}$$Thus assume $$f(a+1)=2\left(\dfrac{a(a+1)}{2}\right)p + p^2 = p^2 + a(a+1)p$$for some $p$. $$p^2 + a(a+1)p \mid (a+1)^3 \implies a(a+1)+p \mid (a+1)^3 \implies a(a+1) + p \mid (a+1)^3 - (a+1)[a(a+1) + p]$$$$\implies a^2 + a + p \mid a^2 + 2a + 1 - (a+1)p \implies (a+1)^2 - (a+1) + p \mid (a+1)^2 - (a+1)p$$But notice that the LHS is bigger than the RHS (if we leave the edgy cases behind by considering few more values as base cases), so for the divisibility to hold, it must be true that $(a+1)^2 - (a+1)p = 0 \implies p=a+1$. Substituting this back into our original expression for $f(a+1)$ we have that $f(a+1)=(a+1)^3$ completing the induction.

I claim that $f(n)=n^3 \forall n$. To prove it, I will induct. The base cases $n=1,2$ are not too hard to prove via casework. Let $f(k)=n^3 \forall n \in \{1,2, \dots, k \}$. First, note that $$(\frac{k(k+1)}{2})^2+f(k+1)$$is a perfect square. Hence, $$f(k+1)=mk(k+1)+m^2$$for some $k$. From the second condition, we deduce that, $$mk(k+1)+m^2|(k+1)^3 \implies mk(k+1)+m^2|m(k+1)^3 \implies mk(k+1)+m^2|m(k+1)^3-mk(k+1)^2-m^2(k+1) \implies m+k(k+1)|(k+1)^2-m(k+1)$$. But $(k+1)^2-m(k+1) \geq k(k+1)+m \iff m \leq \frac{k+1}{k+2}$. Also, clearly $k+1 \geq m$ since if not, $f(k+1) > (k+1)^3$. Hence $(k+1)^2-m(k+1) = 0 \iff m=k+1$ is forced, so we proved that $f(k+1)=(k+1)^3 \blacksquare$

Strong induction method: Claim that only $f(x)=x^3$ satisfy the problem Basis step: one can know easily that $f(1)=1$ and $f(2)=2^3$ Induction step: suppose that $f(n)=n^3$ for some $n\in\mathbb{N}$ We get that $S^2=\sum_{k=1}^nk^3+f(n+1)=\left(\frac{n(n+1)}{2}\right)^2+f(n+1)$ is a perfect square and $f(n+1)|(n+1)^3$ Note that $\left(\frac{n(n+1)}{2}\right)^2<S^2\leq (n+1)^2\left(\frac{n^2}{4}+n+1\right)=\left(\frac{(n+1)(n+2)}{2}\right)^2$. Let $S=\frac{n(n+1)}{2}+a$ where $1<a\leq n+1$ We get $f(n+1)=(an(n+1)+a^2)|(n+1)^3\Longrightarrow (a+n(n+1))|(n+1)^3\Longrightarrow (n+1)^2\leq a(n+1)\Longrightarrow n+1\leq a$ Therefore, $a=n+1$, which make $f(n+1)=(n+1)^3$ Thus, $f(n)=n^3$ is the only solution.