Problem: Let $c>0$ be a real number, and suppose that for every positive integer $n$, at least one percent of the numbers $1^c,2^c,3^c,\dotsc,n^c$ are integers. Prove that $c$ is an integer.

My progress: At first we will deal with the case when $c$ is a rational number. Suppose $c=\frac{a}{b}$. It indeed suffices to prove the statement for rationals of the form $\frac{1}{a}$. Observe that there are $\lfloor{M^{\frac{1}{a}}}\rfloor$ integers of the form $n^{\frac{1}{a}}$ between $1$ and $M$. So the percentage of integers of the form $n^{\frac{1}{a}}$ among the first $M$ integers is $$\frac{\lfloor{M^{\frac{1}{a}}}\rfloor}{M}\times 100\le \frac{M^{\frac{1}{a}}}{M}\times 100=\frac{100}{M^{1-\frac{1}{a}}}$$ which will be less than 1 for sufficiently large $M$.

But I am unable to prove the problem for any real $c$. I tried approximating reals with a sequence of rational numbers, but it didn't work well.

I was recently working on an open problem of similar kind, and I stumbled upon this sub-problem. How to solve this one (preferably not requiring too much heavy tool)?

  • 5
    $\begingroup$ This was the problem A6 in 1971 Putnam. There is a solution here $\endgroup$
    – Wojowu
    Commented May 26, 2019 at 16:47
  • 6
    $\begingroup$ @Wojowu Putnam problem was for 100 percents, not 1 percent. Although the proof may be modified. $\endgroup$ Commented May 26, 2019 at 17:11
  • 1
    $\begingroup$ @FedorPetrov Ah, shame on me, I have actually not read the problem carefully enough! While the problem might still be of interest to the OP, I don't think the proof I link generalizes - it crucially depends on taking differences, and if we only know some fraction of terms are integers, we are not guaranteed any first difference is an integer! However, much more sophisticated tools, like ones discussed here, should give a proof. Of course, OP asks for an elementary proof, which I cannot really provide... $\endgroup$
    – Wojowu
    Commented May 26, 2019 at 17:16
  • $\begingroup$ @Wojowu you may use other difference type operators $\endgroup$ Commented May 26, 2019 at 17:22
  • 4
    $\begingroup$ The six exponential theorem would show that if $n_1$, $n_2$, $n_3$ are three integers with $n_i^c \in {\Bbb N}$ then $\log n_i$ are linearly dependent over ${\Bbb Q}$. (I assume that $c$ is irrational.) You should be able to show from this that at most $\ll (\log N)^2$ integers up to $N$ can satisfy $n^c \in {\Bbb N}$. $\endgroup$
    – Lucia
    Commented May 27, 2019 at 1:20

2 Answers 2


We may modify the finite differences argument. Let $0=t_0<t_1<t_2<\ldots<t_d$ be fixed rational numbers. Our local goal is to find such rational coefficients $\lambda_0,\lambda_1,\ldots,\lambda_d$ that the mean value theorem $$\exists \tilde{x}\in [x,x+t_d]\colon\quad f^{(d)}(\tilde{x})=\sum \lambda_i f(x+t_i)$$ holds for any real $x$ and any $d$ times continuously differentiable on $[x,x+t_d]$ function $f$. This may be done as follows: consider the interpolating polynomial $$h(y)=\sum_{i=0}^d f(x+t_i)\prod_{j\ne i}\frac{y-x-t_j}{t_i-t_j}, \quad \deg h\leqslant d, \quad h(x+t_i)=f(x+t_i).$$ The function $g(y):=f(y)-h(y)$ has zeroes at $y=x+t_i,i=0,\ldots,d$. Therefore by Rolle's theorem there exists $\tilde{x}\in [x,x+t_d]$ such that $g^{(d)}(\tilde{x})=0$. This rewrites as $$ f^{(d)}(\tilde{x})=\sum \lambda_i f(x+t_i),\quad \lambda_i=\frac{d!}{\prod_{j\ne i} (t_i-t_j)}. $$

Now back to the problem. Choose a positive integer $d$ such that $c-d<0$ and integer $M>1000 d$. Call an integer $k$ nice if the set $[k\cdot M+1,k\cdot M+2,\ldots,k\cdot M+M-1]$ contains at least $d+1$ integers $y$ for which $y^c$ is integer. By density condition there exist arbitrarily large nice integers. Denoting the corresponding $d+1$ integers by $x+t_0,x+t_1,\ldots,x+t_d$, where $0=t_0<t_1<\ldots<t_d<M$, and applying our formula we get $$c(c-1)\ldots (c-d+1)\tilde{x}^{c-d}=\sum \lambda_i (x+t_i)^{c}\in (M!)^{-1}\mathbb{Z}.$$ But LHS becomes arbitrarily small while non-zero for large $x$.


To expand on a comment of Lucia, when $c$ is irrational, we can show that there are at most $O((\log N)^2)$ values of $n\leq N$ such that $N^c$ is rational, let alone an integer.

Let $\mathcal{A}$ be the set of $n\leq N$ such that $n^c$ is rational and $n > 1$. Let $n_1$ be the smallest element of $\mathcal{A}$ and let $n_2$ be the smallest element of $\mathcal{A}$ that is not a rational power of $n_1$. The number of elements of $\mathcal{A}$ when no such $n_2$ exists is $O((\log N)^{1+\varepsilon})$ (exercise to the reader).

Since $n_2$ is not a rational power of $n_1$, given a prime $p\mid n_1n_2$, there exists another prime $q\mid n_1n_2$ such that $$ \tag{1}\label{1} \nu_p(n_1)\nu_q(n_2) - \nu_p(n_2)\nu_q(n_1) \neq 0, $$ where $\nu_p(m)$ is the exponent of $p$ in the prime factorization of $m$.

Let $n_3$ be a third element of $\mathcal{A}$ that is not a rational power of $n_1$ or $n_2$ (we're done if this element doesn't exist). Then since $1$ and $c$ are linearly independent over $\mathbb{Q}$, and since $$ \begin{gathered} \exp\left(\log n_1\right),\ \exp\left(\log n_2\right),\ \exp\left(\log n_3\right),\\ \exp\left(c\log n_1\right),\ \exp\left(c\log n_2\right),\ \exp\left(c\log n_3\right) \end{gathered} $$ are all rational, the six exponentials theorem implies that the three real numbers $\log(n_1),\log(n_2),\log(n_3)$ are linearly dependent over $\mathbb{Q}$. That is, there exist rational numbers $A,B,C$ not all zero such that $$ A\log(n_1) + B\log(n_2) + C\log(n_3) = 0. $$ Actually, none of $A,B,C$ are zero, since this would imply that two of $n_1,n_2,n_3$ are rational powers of one another. Dividing by $C$ and renaming the coefficients, and exponentiating, we have $$ \tag{2}\label{2} n_3 = n_1^A n_2^B $$ for some nonzero rational $A,B$. Since $n_3 > 1$, we must have $(n_3,n_1n_2) > 1$. Let $p\mid (n_3,n_1n_2)$ and let $q$ be given by \eqref{1}. Then $$ \begin{aligned} \nu_p(n_3) &= A\nu_p(n_1) + B\nu_p(n_2), \\ \nu_q(n_3) &= A\nu_q(n_1) + B\nu_q(n_2). \end{aligned} $$ There are $O((\log N)^2)$ possible values for the pair $(\nu_p(n_3),\nu_q(n_3))$ with $\nu_p(n_3)\neq (0,0)$. For each pair, \eqref{1} implies that this system has a unique solution in $A$ and $B$. Since any element of $\mathcal{A}$ corresponds to a choice of $A$ and $B$ in \eqref{2}, and since any solution to \eqref{2} corresponds to at most one solution to the system above, the set $\mathcal{A}$ contains at most $O((\log N)^2)$ elements.

  • 1
    $\begingroup$ Nice, and a much stronger result, but I'm not sure that the Six Exponentials Theorem fits the OP's request for a solution "not requiring too much heavy tool." $\endgroup$ Commented Dec 18, 2023 at 22:06
  • 2
    $\begingroup$ @JoeSilverman I 100% agree with you. It's a bit of a sledge hammer. I happened to need this quantitative result for my own research, so I figured I'd post it here in case some future reader finds it useful. $\endgroup$ Commented Dec 19, 2023 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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