Is this excercise doable without a computer? Triangular Number with n divisors

Question

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

from https://projecteuler.net/problem=12

$n$th triangular number=$\frac{n(n+1)}{2}$

(little Gauss)

Algorithm to find number of divisors:

from https://www.geeksforgeeks.org/total-number-divisors-given-number/

# Python3 program for finding  
# number of divisor 

# program for finding  
# no. of divisors 
def divCount(n): 

    # sieve method for 
    # prime calculation 
    hh = [1] * (n + 1); 

    p=2; 
    while((p * p) < n): 
        if (hh[p] == 1): 
            for i in range((p * 2),n,p): 
                hh[i] = 0; 
        p+=1; 

    # Traversing through  
    # all prime numbers 
    total = 1; 
    for p in range(2,n+1): 
        if (hh[p] == 1): 

            # calculate number of divisor 
            # with formula total div =  
            # (p1+1) * (p2+1) *.....* (pn+1) 
            # where n = (a1^p1)*(a2^p2)....  
            # *(an^pn) ai being prime divisor 
            # for n and pi are their respective  
            # power in factorization 
            count = 0; 
            if (n % p == 0): 
                while (n % p == 0): 
                    n = int(n / p); 
                    count+=1; 
                total *=(count + 1); 

    return total; 


# Driver Code 
n = 24; 
print(divCount(n)); 

# This code is contributed by mits 

Is the task doable without a computer, in reasonable time?

If so, what's the "magic" trick?

Answer 1

I believe this problem can be solved without computers. If $T(n)$ is the n-th triangular number, then we know that $$T(n)=1+2+3+...+n=\sum^n_{i=1}=\frac{n(n+1)}{2}$$

Let’s assume that we know the prime factorizations of both $n$ and $n+1$, and we’ll write

$$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}...p_s^{e_s}\text{ and }n+1=q_1^{f_1}q_2^{f_2}q_3^{f_3}...q_t^{f_t}$$ Notice that $n$ and $n+1$ cannot share any prime factors (as they are consecutive numbers), and so we know that all the $p_i$ and $q_i$ are distinct primes. Also, one and only one of $n$ and $n+1$ are divisible by $2$. The exponents $e_i$ and $f_i$ are therefore the only things we really need to consider in order to determine the number of divisors of $T(n)$. The fact that $T(n)=\frac{n(n+1)}{2}$ means that we’ll need to neglect a single power of two in the factorization of $n$ or $n+1$ (remember, only one is even). Let’s assume, without loss of generality, that $n$ is even and that $p_1=2$. Then, some quick combinatorics tell us that the total number of factors of $T(n)$ will be $$(e_1+1)(e_2+1)...(e_s+1)(f_1+1)(f_2+1)...(f_t+1)=e_1\Pi^s_{i=2}(e_i+1)\Pi^t_{i=1}(f_i+1)$$

Even better, as we’re increasing our triangular numbers looking for the first one to satisfy the property in question, we only need to calculate the factorization of $n+1$ (as we already know that factorization of $n$, as it was previously $n+1$). This should decrease the run time substantially.