Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

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

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