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

Question

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?

Answer 1

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.

Answer 2

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.