Project Euler 378: Count ordered triplets whose triangular numbers have decreasing number of factors Project Euler problem 378 says:


  Let \$T(n)\$ be the \$n\$th triangle number, so \$T(n) = {n (n+1) \over 2}\$.
  
  Let \$\mathit{dT}(n)\$ be the number of divisors of \$T(n)\$.
  E.g.: \$T(7) = 28\$ and \$\mathit{dT}(7) = 6\$.
  
  Let \$\mathit{Tr}(n)\$ be the number of triples \$(i, j, k)\$ such that \$1 ≤ i &lt; j &lt; k ≤ n\$ and \$\mathit{dT}(i) &gt; \mathit{dT}(j) &gt; \mathit{dT}(k)\$.
  \$\mathit{Tr}(20) = 14\$, \$\mathit{Tr}(100) = 5772\$ and \$\mathit{Tr}(1000) = 11174776\$.
  
  Find \$\mathit{Tr}(60\,000\,000)\$.
  Give the last 18 digits of your answer.


This is my attempt at solving it:

def t(n):
    tri_num = (n * (n+1))//2
    return tri_num

#finding nth triangle numbers

def dt(n):
    count = 0
    for i in range(1,t(n)+1):
        if t(n)%i == 0:
            count += 1
    return count

#finding nth triangle numbers' total number of dividers


def factors(n):
    factors = []
    for i in range(1,t(n)+1):
        if t(n)%i == 0:
            factors.append(i)
    return factors
#finding nth triangle number's dividers

def tr(n):
    triplesnum = 0
    triples = [(i, j, k) for i in range(n) for j in range(n) for k in range(n) if 1 &lt;= i &lt; j &lt; k &lt;= n and dt(i) &gt; dt(j) &gt; dt(k)]
    for i in triples:
        triplesnum += 1
    return triplesnum
while True:
    n = int(input("N =???"))
    print("triples number",tr(n))

#solution


I am new to python; I only know at most the loops,list comprehension, functions, and some class.  I am sure this problem can be solved more simply.

Although I see this code as a success considering my knowledge, it works too slowly for me after 3-digit values of n.

Is there an improvement I can make with my current knowledge?  If not, what should I be learning about next?

Note: I know some of the code is not necessary, but I used them as a testing material in the further functions.
I am new to python; I only know at most the loops,list comprehension,
  functions, and some class. I am sure this problem can be solved more
  simply.
  
  ...
  
  Is there an improvement I can make with my current knowledge? If not,
  what should I be learning about next?


Loops and arrays are all you really need to solve almost any Project Euler challenge. The only exceptions are the ones which also require reading an input file. The point of PE is not to push your knowledge of language features, but to push your mathematical skills and knowledge of data structures and algorithms.

I would advise you to solve at least 40 of the first 50 challenges before you start looking at challenges beyond 100, because the early challenges introduce key techniques which you will use many times in later challenges. Trying to solve #378 before #12 is simply doing things in the wrong order.

The most important of the key techniques is dynamic programming. So many PE problems can only be solved in a reasonable time by exploiting shared structure. In this challenge, for example, you use the "number of divisors" function \$d(n)\$. The structure of this function can be summed up as $$\begin{align}
d(p^a) &amp;= a+1&amp;\qquad \textrm{when }p\textrm{ is prime} \\
d(mn) &amp;=d(m)d(n)&amp;\qquad \textrm{when }\gcd(m,n)=1
\end{align}$$
Exploiting that structure by adapting the sieve of Eratosphenes will allow you to calculate an array containing dt(n) for every \$1 \le n \le 60000000\$ in less than a minute.

Similarly, exploiting the structure of \$1 ≤ i &lt; j &lt; k ≤ n\$ and \$\mathit{dT}(i) &gt; \mathit{dT}(j) &gt; \mathit{dT}(k)\$ will allow you to reduce the current \$O(n^3)\$ runtime of that accumulation phase to \$O(nw)\$ where \$w = \max \{dT(i) : 1 \le i \le n\}\$. That's enough to solve the problem in about 40 minutes, using only basic data structures.

To solve the problem in under two minutes you will need an advanced data structure, but that's more than enough spoiler. Solve the problem at all and you'll get access to the forum thread where people explain their solutions.