We can improve your code in many areas.
First, a baseline on my laptop. Run time for N=70
is 16.4 seconds.
t(n)
is only called inside dt(n)
, so we can avoid the extra function call and remove t(n)
and move the calculation inside of dt(n)
.
While doing so, we can see the calculation is actually being performed \$t(n)+1\$ times! We should save the result of the calculation in a local variable tn
:
def dt(n):
tn = n * (n+1) // 2
count = 0
for i in range(1, tn+1):
if tn % i == 0:
count += 1
return count
Time for N=70
drops to 4.5 seconds.
Counting factors from 1
to tn
seems like it does a lot of extra work. We can automatically include 1
and tn
as factors, so we could start our count a 2 (assuming tn>1
), and only count the factors between 2
and tn-1
. But the largest possible factor below tn
is tn/2
, so we can cut that range in half.
def dt(n):
tn = n * (n+1) // 2
if tn == 1:
return 1
count = 2
for i in range(2,tn//2+1):
if tn % i == 0:
count += 1
return count
Computes N=70
in 2.1 seconds.
Our factors come in pairs. 1
matches tn
, 2
would match tn//2
if tn
is even, 3
would match tn//3
, and so on. We could count by 2
for every pair, and only count up to \$sqrt(tn)\$. Of course, we need to take into account the possibility of t(n)
being a perfect square; t(8) = 36 = 6*6
, so 6
should only count for 1 factor, not 2.
def dt(n):
tn = n * (n+1) // 2
if tn == 1:
return 1
sqrt_tn = int(math.sqrt(tn))
count = 2
for i in range(2, sqrt_tn+1):
if tn % i == 0:
count += 2
if sqrt_tn * sqrt_tn == tn:
count -= 1
return count
List comprehension can reduce the loop a little bit, too.
def dt(n):
tn = n * (n+1) // 2
if tn == 1:
return 1
sqrt_tn = int(math.sqrt(tn))
count = 2 + sum(2 for i in range(2, sqrt_tn+1) if tn % i == 0)
if sqrt_tn * sqrt_tn == tn:
count -= 1
return count
Computes N=70
in 0.3 seconds.
How many times are we calling dt(n)
for any given value of n
? Does the same value get returned each time? If so, why recalculate it? functools.lru_cache
can do the caching for us:
@functools.lru_cache(maxsize=None)
def dt(n):
tn = n * (n+1) // 2
if tn == 1:
return 1
sqrt_tn = int(math.sqrt(tn))
count = 2 + sum(2 for i in range(2, sqrt_tn+1) if tn % i == 0)
if sqrt_tn * sqrt_tn == tn:
count -= 1
return count
Computes N=70
in 0.09 seconds.
Let's turn our attention to tr(n)
.
triples = [(i, j, k) for i in range(n)
for j in range(n)
for k in range(n)
if 1 <= i < j < k <= n and dt(i) > dt(j) > dt(k)]
If 1 <= i < j < k <= n
, why start i
at 0, j
at 0, and k
at 0? j
should start at i+1
and k
at j+1
. And k
should actually reach n
, not n-1
which is a bug.
def tr(n):
triplesnum = 0
triples = [(i, j, k) for i in range(1, n-1)
for j in range(i+1, n)
for k in range(j+1, n+1) # n+1: Bug fix
if 1 <= i < j < k <= n and dt(i) > dt(j) > dt(k)]
for i in triples:
triplesnum += 1
return triplesnum
Computes N=70
in 0.07 seconds.
Why generate the tuple(i, j, k)
when we only count its existence? Why generate an array only to count every element in it?
def tr(n):
return sum(1 for i in range(1, n-1)
for j in range(i+1, n)
for k in range(j+1, n+1)
if dt(i) > dt(j) > dt(k))
Computes N=70
in 0.05 seconds.
Looks like a 328x speed-up, using just loops, list comprehensions and functions ... just by looking to avoid repeated work and overhead ... oh, and the @lru_cache decorator.
Unfortunately, N=700
now takes 16 seconds. So these incremental speedups aren't going to take you to \$Tr(60 000 000)\$ anytime in the near future.
Oh, one last optimization. Why loop over all the possible values of k
when dt(i) > dt(j)
is False
?
def tr(n):
return sum(1 for i in range(1, n-1)
for j in range(i+1, n) if dt(i) > dt(j)
for k in range(j+1, n+1) if dt(j) > dt(k))
That brings N=700
down to 5.9 seconds. We now reach 16 seconds at N=1000
. 60 million is still in the far, far future.
triplesnum += 1
more than \$10^{18}\$ times, taking hundreds of years. So this can't be the way to do it. \$\endgroup\$