# Does this sequence have this interesting property relating to the prime factorization of the index?

Define a sequence as $a_0 = 0$ and $a_n$ equals the number of divisors of $n$ (including 1 and $n$) that are greater than $a_{n-1}$. This is sequence A152188 in OEIS, by the way.

(For example, the first few terms are: 0, 1, 1, 1, 2, 1, 3, 1, 3, 1, 3, 1, 5, 1, 3, 2, 3, 1, 5, 1, 5, 2, 2, 1, 7).

Here are some basic results that I know to be true:

$a_n$ for prime $n$ equals $1$, but a value of $1$ does not imply primality (e.g., $a_9 = 1$ but $9$ is the square of a prime).

$a_n$ can never exceed $\lfloor n/2\rfloor$ for $n > 1$.

$a_n$ for even $n$ greater than $2$ can never equal $1$.

I have tried to prove that $a_n = 1$ implies that $n$ is either prime or has a prime factorization consisting entirely of $p^j$ for some prime $p$ and an integer $j$ (there is only one prime in the factorization). A computer-based test I ran found no counterexamples, and interestingly, $a_n = 1$ implies the primality of $n$ every time with the exception of a few numbers early on (up until I quit testing after looking at about 10 million terms).

Can anyone prove this property?

-

If $n$ is composite, it has at least two divisors $\ge \sqrt{n}$. Now $a_{n-1} < \tau(n-1) < \sqrt{n-1}$ (where $\tau$ is the number-of-divisors function) for all sufficiently large $n$: in fact for any $\epsilon > 0$, $\tau(n) \le n^\epsilon$ for sufficiently large $n$. So if $n$ is sufficiently large, $a_n = 1$ implies $n$ is prime. It appears from http://oeis.org/A035033 that $1260$ is the greatest $n$ such that $\tau(n) \ge \sqrt{n}$, but I don't have a reference to a rigourous proof of that.

-
Thanks for the help. Could you clarify why the inequalities you described allow you to say that if $n$ is sufficiently large, $a_n=1$ implies $n$ is prime? I don't clearly see how this follows. –  C. Williamson Aug 9 '12 at 14:49
@C.Williamson: If $n$ is the product of two positive integers $a,b$, the largest of $a$ and $b$ is at least $\sqrt{n}$, and therefore (if $a_{n-1} \le \sqrt{n-1}$) is counted in $a_n$. If $a_n = 1$ the only such pair is $n = 1 \times n$, which says $n$ is prime. –  Robert Israel Aug 9 '12 at 16:30
Got it. Thanks! I should have realized this the first time. –  C. Williamson Aug 10 '12 at 14:37

A number with prime factorization $2^{k_2}3^{k_3}5^{k_5}\cdots$ has $(k_2+1)(k_3+1)(k_5+1)\cdots$ divisors. For aid in finding the value of $n$ from which Robert's inequality $\tau(n)\lt\sqrt n$ holds, here are some values of $\sqrt{p^{k_p}}/(k_p+1)$:

$$\begin{array}{c|cc} p\backslash k_p&1&2&3&4&5&6\\ \hline 2 & 0.707107&0.666667&0.707107&0.800000&0.942809&1.142857\\ 3 & 0.866025&1.000000&1.299038&1.800000\\ 5 & 1.118034&1.666667&2.795085&5.000000\\ 7 & 1.322876&2.333333&4.630065&9.800000\\ 11 & 1.658312&3.666667&9.120718&24.200000\\ \end{array}$$

To violate the inequality, you need to form a product of entries, at most one from each row, that's less than $1$. The opportunities for that are clearly limited.

-
This is a good way to think about this. Thanks! –  C. Williamson Aug 10 '12 at 14:17
@C.Williamson: You're welcome! –  joriki Aug 10 '12 at 14:18
Just so you know, I went through all the combinations, and the maximum number that breaks the inequality is indeed 1260. –  C. Williamson Aug 14 '12 at 6:08
@C.Williamson: Thanks for letting me know :-) –  joriki Aug 14 '12 at 6:20