MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a sequence $N_k$ of numbers whose growth I wish to determine, or at least approximate nicely. When I look at the ratios of consecutive members, I find some interesting simplifications occurring. Part of this can be explained by how I generate these numbers, but I am still surprised at how smooth these numbers are. Is there a good explanation for this? Also, any references which might point to material related to this sequence, or talks about the growth of the $N_k$ or fractions $N_k/P_k$, would be appreciated.

Given $n$ I am trying to figure out how "bad" a linear approximation is to the number of totients of n in an interval. MathOverflow 88877 Bound the error in estimating a relative totient function covers some general theory, but I am focussing on the case n is the $k$th primorial $P_k$. I generate differences between consecutive totients, and use that to compare the actual number of totients in $(0,x]$ with the predicted number $x\phi(P_k)/P_k$. I actually am computing the numerator $N_k$ of a fraction: $N_k/P_k$ will turn out to be the maximum difference over all $x \in (0,P_k)$ between the actual count in $(0, x] to the expected value .

I compute this in a loop by adding multiples of $\phi(P_k)$ and subtracting $P_k$ in each iteration, so I expect all values, including the maximum, to be multiples of $\gcd(P_k,\phi(P_k))$. Even after factoring that out, I still find the result to be smooth. I now list $N_k$ and the "leftover factors" that result after removing those common to $P_k$ and $\phi(P_k)$: $$ \begin{eqnarray*} k & N_k & \textrm{leftover factors} \\ 1 & 1 & 1 \\ 2 & 4 & 2 \\ 3 & 28 & 2,7 \\ 4 & 318 & 53 \\ 5 & 5820 & 2,97 \\ 6 & 106530 & 53,67 \\ 7 & 2776560 & 2,2,2,23,503 \\ 8 & 83991240 & 2,2,3,181,1289 \\ 9 & 3216557520 & 2,2,2,3,11,31,397 \\ \end{eqnarray*}$$

$N_k$ is $a*\phi(P_k)- b * P_k$ for some $a \lt P_k$ and $b \lt \phi(P_k)$, and one expects $b/a$ often to be near $\phi(P_k)/P_k$. However, I am still surprised by the smoothness of $N_k$ for $k \gt 5$. (The appearance of $53$ twice also interests me.) Is this to be expected, perhaps as a consequence of Guy's Strong law of Small Numbers?

Gerhard "Large Numbers Made From Small" Paseman, 2014.01.29

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.