0
$\begingroup$

Find the number of $n < 100$ such that the nth triangular number has the same number of positive factors as $n.$

What I did: We know that the nth triangular number is $\frac{n(n+1)}{2}$ and I represented n with its general prime factorization $$n = p_1^{e_1} + p_1^{e_2} + ... + p_k^{e_k}$$ which means that it has $$(e_1 + 1)(e_2+1)...(e_k+1)~\text{factors}.$$ How would I proceed from here?

Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ You have to know 1) the formula for the $n$th triangular number, and 2) the formula for the number of "factors" of $n$, in terms of the prime factorization of $n$. But what exactly does "factors" mean? $12$ has six "divisors", three prime factors if you count with multiplicity, two prime factors if you don't. So which do you mean by "factors"? $\endgroup$ Oct 11, 2020 at 5:09
  • $\begingroup$ I have clarified in my edits $\endgroup$
    – Michael Li
    Oct 11, 2020 at 5:17

1 Answer 1

1
$\begingroup$

Let $n = p_1^{k_1} \cdots p_m^{k_m}$ be the prime factorization of $n$. It has $$(k_1+1)\cdots(k_m+1) \tag{$*$}$$ factors.

Note that $n+1$ and $n$ share no prime factors. So the prime factorization $n+1 = q_1^{l_1} \cdots q_{m'}^{l_{m'}}$ consists of primes $q_i$ that are distinct from the other primes $p_i$.

In particular, $n(n+1) = p_1^{k_1} \cdots p_m^{k_m} q_1^{l_1} \cdots q_{m'}^{l_{m'}}$ is the prime factorization of $n(n+1)$.

  • If $n$ is even, then, $p_1 = 2$ and thus the number of factors of $n(n-1)/2$ is $k_1 (k_2+1) \cdots (k_m+1) (l_1+1) \cdots (l_{m'}+1)$. Equating this to ($*$) yields $k_1+1 = k_1 (l_1+1) \cdots (l_{m'}+1)$ which is only possible if $k_1=1$ and $m'=1$ and $l_1=1$ all hold, i.e. $n+1$ is prime and $n$ is not divisible by $4$.
  • If $n$ is odd, then $q_1=2$, and thus the number of factors of $n(n-1)/2$ is $(k_1+1)\cdots(k_m+1)l_1 (l_2+1) \cdots (l_{m'}+1)$. Equating this to ($*$) forces $l_1=1$ and $m'=1$, i.e. $n+1 = 2$ or $n=1$.

In summary, the solutions (besides $n=1$) are any even $n$ that is not divisible by $4$ and such that $n+1$ is prime.

$\endgroup$
3
  • $\begingroup$ Also $T(6) = 21$ has the same number of divisors as $6$ has. For even $n$ the condition becomes "$k_1 = 1$ and $n+1$ is prime", or "$n+1$ is a prime $\equiv 3 \pmod{4}$". $\endgroup$ Oct 11, 2020 at 12:45
  • $\begingroup$ @DanielFischer Thanks for catching my error $\endgroup$
    – angryavian
    Oct 11, 2020 at 18:26
  • $\begingroup$ @GerryMyerson Thanks for catching my error $\endgroup$
    – angryavian
    Oct 11, 2020 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .