-1

I have been writing in python for only few months now, so please don't be too harsh on me. But I've wrote this code and I don't know how I can make it faster.

n = 2
ListOfTriangles = []
ListOfDivisors = []
term = 0

for x in range(1,100001):
    x = (n*(n-1))/2
    ListOfTriangles.append(int(x))
    n += 1

for y in range(1,100001):
    Tri = ListOfTriangles[term]
    for i in range(1,Tri+1):
        if(Tri%i==0):
            ListOfDivisors.append(i)
    if len(ListOfDivisors) >= 500:
        print("---------------------------------------------------")
        print(len(ListOfDivisors))
        print(ListOfDivisors)
        print(ListOfTriangles[term])
        print("---------------------------------------------------")
        break
    print(ListOfTriangles[term]," - ",len(ListOfDivisors)," - ",(term/100000)*(10**2),"%")
    ListOfDivisors = []
    term += 1

Basically what I have done if you can't tell by this mess, is that i created a list with Triangular Numbers and then put this list through loop that list all factors for each number found in the list and then stop when it finds number that meats the requirement of number having over 500 factors.

PusiaPaker
  • 3
  • 1
  • 1
    Have you profiled your code to try to see where the bottlenecks are? This [question](https://stackoverflow.com/questions/582336/how-can-you-profile-a-python-script) has lots of answers you may find useful to get you started. – import random Mar 25 '20 at 03:13
  • Try generating triangle numbers *on the fly*, instead of all at once, using a `while` loop, until you find one with over 500 factors. Note that all you need is the count of the factors - you don't need to save the factors themselves. Also, you can use a shortcut when finding the number of factors - every non-square number has an even number of factors - there's a direct correspondence between those less than the square root and those greater (which means you only have to count up to the square root of each number when finding their factors). – Green Cloak Guy Mar 25 '20 at 03:14
  • It's a bit primitive, because Rockstar is a primitive language, but [here's a working solution to Problem 12 in Rockstar](https://github.com/Superbird11/rockstar-euler/blob/master/euler/12/euler12.boring.rock), annotated in pseudocode, that I wrote a little while ago. – Green Cloak Guy Mar 25 '20 at 03:14

1 Answers1

0

One idea applicable to this problem is as follows:

The n'th triangular number t[n] is given by n * (n + 1) / 2. Note that the only common divisor of n and n + 1 is 1. Let divs[n] denote the number of divisors of n. Then,

  • for even n, we have divs[t[n]] = divs[n//2] * divs[n+1] - 1
  • for odd n, we have divs[t[n]] = divs[n] * divs[(n+1)/2] - 1

We can precompute the number of divisors for each number from 1 to n in O(n^2) time (this can be improved asymptotically), and use the formula above to compute the number of divisors for the corresponding triangular number. With numpy, we have:

import numpy as np
# pick a number of elements for divisor computation 
n = 20_000

# store number of divisors of n; O(n^2), can be optimized asymptotically
divs = np.zeros(n+1, dtype=int)
for i in range(1,n+2):
  # i divides every number in the sequence i, 2i, 3i... (up to n)
  divs[i:n+2:i] += 1

# store number of divisors of n'th triangular number
divs_tri = np.zeros(n, dtype=int)
# treat evens and odds separately
evens = np.arange(0, n, 2) # e.g. [0, 2, 4...]
odds  = np.arange(1, n, 2) # e.g. [1, 3, 5...]
# with even k, k/2 and k+1 are coprime; -1 accounts for 1 being a factor of both
divs_tri[evens] = divs[evens//2] * divs[evens+1] - 1
# with odd k, k and (k+1)/2 are coprime; -1 accounts for 1 being a factor of both
divs_tri[odds]  = divs[odds] * divs[(odds+1)//2] - 1

# index of first triangular number with at least 500 divisors
k = (divs_tri >= 500).argmax()

# compute the value of k'th triangular number
ans = k * (k + 1) // 2
hilberts_drinking_problem
  • 11,322
  • 3
  • 22
  • 51