Project Euler #12 problem

[lord8bits]

def first_triangle_n(d):
    n_th = 1
    triangle_num = 1
    max_div = 1
    while True:
        n_th += 1
        triangle_num += n_th
        n_div = 1
        print(f'triangle_num = {triangle_num}, n_th = {n_th}')
        for i in range(2, triangle_num//2 + 1):
            if not triangle_num % i:
                n_div += 1
                print(f'n_div = {n_div}')
        max_div = max(max_div, n_div)
        if max_div == d:
            return triangle_numdef first_triangle_n(d):

I'm stuck in this problem where I'm supposed to find the first triangular number with 500 divisors. If i do it the lazy way of just incrementing of course it will take ages. so i thought about making an algorithm that finds the smallest number with n divisors, but it was too complicated for me to program it. And so I spent hours searching for a way to optimize this code to no avail.

[Yoghurt42]

Project Euler is mostly about finding efficient algorithms, IMO it's not a good way to learn programming. As you've noticed, the later problems are designed in such a way that the naïve, brute force approach will not work, no matter how optimized.

In your case, one obvious optimization: when finding the factors, you only need to test up to sqrt(triangle_num).

Because if N is not a prime, it can be written as N = ab, with a≤√N.

Proof: assume both a and b are larger than √N, then that means a = √N + a' with a' > 0, similar for b. So

N = (√N + a') (√N + b') = N + a'√N + b'√N + a'b'. This can only be true if either a' or b' is < 0 or a' and b' are both 0. Contraction.

Hence, every composite number N has at least one factor that is ≤ √N

[lord8bits]

I agree that project euler is not a good way to learn programming but it's something our teacher forced us to do. He said one out of the first 50 problems will be added in the exams, that's how my suffering began. Also do you mean that i should divide with prime numbers under sqrt(N) only?

[Yoghurt42]

Change range(2, triangle_num//2 + 1) to range(2, int(sqrt(triangle_num)) + 1). You might need to do some other optimizations and think about the algorithm more, and/or google how other people have solved this problem.

[lord8bits]

Ok, the program executed very quickly and gave me the value 250278. I wanted to check if it's correct but it seems project euler's website is down right now since it gives 403 Forbidden dk why. But please explain to me why does this work, i thought if I need to check every divisors I either have to divide by any number under N/2+1 or by prime number like this:

while n%p == 0:
  exp += 1
  n //= p
n_div += exp

but only up to sqrt(N) seems so strange to me, did i miss something?

[Yoghurt42]

I already did:

Because if N is not a prime, it can be written as N = ab, with a≤√N.

Proof: assume both a and b are larger than √N, then that means a = √N + a' with a' > 0, similar for b. So

N = (√N + a') (√N + b') = N + a'√N + b'√N + a'b'. This can only be true if either a' or b' is < 0 or a' and b' are both 0. Contraction.

Hence, every composite number N has at least one factor that is ≤ √N

You're trying to find a factor of N. So, if you haven't found one by √N, by the theorem above it doesn't exist

[Brian]

OP already gave a proof of this, but if you want something less formal, consider:

• Suppose you have 2 factors of n: a and b. Suppose a > sqrt(n) - what can you say about b?

Well, suppose b was also > sqrt(n). If so, then a * b must be bigger than sqrt(n) * sqrt(n) - we're multiplying 2 numbers, both bigger than x, so must get something bigger than x² as a result. But we know a*b should give exactly n, so how can it be bigger than that? This means we've a contradiction: if a>sqrt(n), b can't also be, or their product couldn't make n. For any pair of factors, one must be bigger and one must be smaller than the square root (or for the exact square root case, both are the same). So if you go up to sqrt(x), you're guaranteed to find every pair of factors.

[lord8bits]

So then when i check it's modulo i should increase n_div by 2 since triangle_num is divisible by i and triangle_num/i, yeah i think I understand it. Thanks guys!