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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.