The latest problem from fakalin. Took some wrong turns and hints to solve it…

Given a polynomial \(f: \mathbb{Z}\to \mathbb{Z}\) with positive integer coefficients, how many evaluations of \(f\) does it take to obtain the polynomial?

(An \(f: \mathbb{R}\to \mathbb{R}\) polynomial with real coefficients would take the number of degrees plus 1 to specify, which, if it held in this case, would render the answer unbounded. But the correct answer in this case is surprisingly small.)
(Read the article)

Comments(0)

Here is a problem on complexity, or alternatively, convergence.

If an integer \(n\) is reduced by the largest square less than it each time until it is terminated at zero, show that the number of steps taken is at most order \(\log \log n\).

More precisely, let \(f(n) = n – {\left\lfloor{\sqrt{n}}\right\rfloor}^2\) and \(g(n)=k\) be the minimum number of steps until \(f^k(n)=0\). Prove that there exists some fixed \(A\) such that \(g(n)< A \log \log n\) for all \(n\ge 3\).
(Read the article)

Comments(0)