Problem 012

[MacPr1mE]

Sorry, I'm a little bit confused. ;D
The biggest even divisor of a number cannot be bigger that the number's sqare root, right?

Well, what about 554400? Is it the first triangular number with over 100 divisors?

[stijn263]

The biggest even divisor of a number cannot be bigger that the number's sqare root, right?

36 has square root of 6, yet the biggest even divisor is 36 (or 18 in some definitions)

Well, what about 554400? Is it the first triangular number with over 100 divisors?

554400 is not a triangle number

edit: 50403 is a triangle number because:
50403 = 1 + 2 + 3 + .... + 316 + 317

[MacPr1mE]

lol, I don't know what's wrong with me.
The n-th triangular number can be definded as (n² + n) / 2, can't it?

OK, last try for today:
384, is it the first triangular number with over 100 divisors?

[stijn263]

The n-th triangular number can be definded as (n² + n) / 2, can't it?

Yes

384, is it the first triangle number...?

For which n do you get (n² + n) / 2 = 384...?

Also, 384 has only 16 divisors..

[MacPr1mE]

Well, now I've fixed some in my code and it works. When I computerd the example given in Problem 12, it's the right answer. But when I tried to run my programm with bigger numbers, there's no result within 10 minutes.

[markgobbin]

The reason i post this is I had an interesting bug in my program that messed up my triangle numbers - it started as 3 and then in sequence it adds 4,5,6 etc. instead of 3,4,5,6... But it produced the result that 37346400 (it's not even a triangle number!) also has 576 divisors, even though they are different factors it was a coincidence and made me think the answer was wrong

my program is slightly cheaty but runs in 3 or 4 seconds. the number of primes i calculated was quite arbitrary... but you can guesstimate, if the number is the smallest number required then it's gonna have smaller primes in it. I just chose 500 primes and put them in an array. but for lack of a better mathematical way, technically you need everything below the square root of the number tested but this seems too many since you need the smallest possible primes to make up the number - someone should have a go at proving this but i'll just comment that if you have 9 unique prime factors then each is used once = (1+1)^n, and 2^9 = 512 factors. If you use fewer primes they need higher exponents to get the 500 factors out, which increases size of the number a bit. So to get the smallest number for this, it seems approx. the first 9 prime numbers seems like a good ballpark estimate of what's needed

but the proof would interest me because it's like - in theory, it's possible to have, say the 100th prime multiplied by 2*3*5*7*11*13*17*19 (or alternatively - p^1 * 2^249, lols), giving the 500 factors but - this would make the number larger than whatever small numbers we want, and is unlikely. so how would you prove this?

[TyrReich]

In order to get the prime factors I'm using a slightly modified Sieve of Eratosthenes. My algorithm has worked correctly for the previous problems but this time I'm occasionally getting duplicate prime numbers back. It happens very rarely as far as I can tell but it could be a sign of deeper problems.

For example, my output for the first 5 triangle numbers is:

Code: Select all

1: 1
3: 3 1
6: 3 2 2
10: 5 2
15: 5 3 3

I can't figure out why it would repeat the lowest prime factors for only 6 and 15. Not that it matters for this problem, but I also can't figure out why it reports 1 as a prime factor for only 1 and 3 either. This is the implementation of the sieve I used. The only thing I changed for the sieve was simply to check if the prime number was a factor of the number I passed into it. I don't see how this could affect its accuracy. I tried not to post any info that wasn't already posted in this thread. If I have I apologize and will edit it asap.

EDIT: I cheated by storing the prime factors in a set instead of a vector.

[TripleM]

If you want to PM me your code I can give you a hint as to what is wrong.

[matthewden]

I am using Python for this problem, and my code ran for 5,864,873.358 milliseconds... I counted.... jk, i used a timer, but still, that's 97 [frac]3,4[/frac] minutes!!!! I got the wrong answer, too .

I have it starting with

i*(i+1)/2

where i is the sum of the natural numbers 1 through n, and doing

Code: Select all

while numFactors of (i*(i+1))/2 <= 500

incrementing the length of i by 1.
...
Coming back a little later, I realize that my function called "numFactors" may be wrong! I use it counts the number of factors of a variable, n. In my definition, when n = 10, it will return 1, 2, and 5 as the factors of 10, or a total of 3 different factors. When n = 20, it will return 1, 2, 4, 5, and 10, or a total of 5 different factors.

Am I using the correct concept, or should "numFactors" return 4 when n = 10 (1,2,5,10) and 6 when n = 20 (1,2,4,5,10,20)?

[hk]

The problem description gives this for the divisors of the first 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

So for 10 it gives 1,2,5,10 that is 4 divisors.
What you are calculating is the number of proper divisors.

[agoston.fung]

Hi!

Guys, I'm going crazy, please help someone! I wrote my algorithm and I know it is slow and I could make it better with a better divisor calculating function, but my brute force slowly but gave me a result which appears to be incorrect and I don't know what's wrong.

Could anyone please check 31351321 for me, whether it is a triangle number and how many divisors it has?

Thank you!

Aston

[hk]

Yep it is a trianglenumber and it has 8 divisors.

[agoston.fung]

Yep it is a trianglenumber and it has 8 divisors.

Oh, cheers mate! Now I got the right solution. Many thanks!!!

[Seahawk]

Well I have been getting medium good at project euler and I put off problem 12 for a while. Now I understand how to do it but I don't understand how to do it efficiently. I know the answer is in the millions or ten millions but mine was only at 100k after about a minute. I don't know what isn't going fast enough so could somebody put me on the right path? Here is the code:

Expand

[code]
SNIP[/code]

[Lord_Farin]

Two general things:
1: Don't open new topics on problems for which there already exists one.
2: Pay attention to the obvious text in red before posting code. Now please edit it out.

As for Problem 12, you might want to think about more efficient ways to generate the triangle numbers (ie. not by filtering through all numbers).

[Kelakhai]

Just to be sure...
There is a way to find the answer with programs that don't last one hour of brute force search ?
I did it for a problem earlier but I feel like I'm going to wait for days with this one...

[hk]

Just to be sure...
There is a way to find the answer with programs that don't last one hour of brute force search ?

Yes, there is.

[Kelakhai]

Thanks, I'll keep searching.
But it's been a long time since I learn algorithmic and maths.
Damn this one's a pain

---

Solved with a 778 seconds brute force lookup.
I'm not proud of it...

[rayfil]

Solved with a 778 seconds brute force lookup.

Great! Now you can study the PDF and learn how you can get it down below 10 ms. The simple math you will learn from it will be useful to solve other problems more efficiently.

[Kelakhai]

AWWWWWW
Just red the PDF...

Yikes, that's a math thingie I've never been before...
Seems logic I had a hard time on it...
Thanks Rayfil... I got many things more to learn !