MathDB
A function that is O(n)

Source: 2022 IMOC N2

September 5, 2022
IMOCnumber theory

Problem Statement

For a positive integer nn, define f(x)f(x) to be the smallest positive integer xx satisfying the following conditions: there exists a positive integer kk and kk distinct positive integers n=a0<a1<a2<<ak1=xn=a_0<a_1<a_2<\cdots<a_{k-1}=x such that a0a1ak1a_0a_1\cdots a_{k-1} is a perfect square. Find the smallest real number cc such that there exists a positive integer NN such that for all n>Nn>N we have f(n)cnf(n)\leq cn.
Proposed by Fysty and amano_hina