Problem 012

[rayfil]

Thanks for the feedback. The PDF file has been corrected.

[geek69]

I just went to check out the corrected PDF, and I'm not seeing the cnt=1 line... Perhaps the new version didn't upload correctly?

[jaap]

I just went to check out the corrected PDF, and I'm not seeing the cnt=1 line... Perhaps the new version didn't upload correctly?

Now cnt is reset to zero inside the loop in all three code examples, but unfortunately the while condition test cnt and hence uses an uninitialised value the first time around.
Maybe they should be do{ }while() loops instead.

[rayfil]

I've reinstated the initialization of cnt before entering the loop for the first three examples (the 4th example had it already) to insure the "while" loop is entered properly. The cnt then has to be reinitialized to 0 for the first two examples and to 1 for the 3rd example at the top of the "while" loop. It does not have to be reinitialized for the last example because it is computed from Dn and Dn1.

[julian201]

I've been digging around but I can't seem to find a decent speed algorithm for problem 12. I don't really have much education, besides what I've taught myself... so go easy.

Trial division just simply does not work. I was wondering if there were any algorithms specific to factoring triangular numbers?

I was working on something to find prime factors, and all multiples, but I can't seem to implement the third step in it.
FYI, I only want the AMOUNT of factors for each number, not the actual numbers.

pseudocode for 'my' algorithm:

iterate through x=2 to sqrt(input)
if x is prime and input/x has no remainder, then increment the amount of factors, else continue

create variable of prime-factors-amount*2 size
reiterate through x=2 to sqrt(input)
fill variable with dividable primes and their maximum exponent

--step 3--: find all non-redundant combonations of each and every prime factor.

I'm not even sure if this will save me some time, but I do know finding prime factors is drastically faster than trial division.
Any ideas on how I could implement step 3 in C/C++? The first two work perfectly, I'm just not entirely sure how to do such a complex iteration. Maybe there is a better school of thought on the issue. All help is -greatly- appreciated!

[stijn263]

Let's say you have the primefactorisation of a number:

120 = 2^3 * 3^1 * 5^1

Then you can find the number of divisors of 120 by realizing that you can select a 2 {0,1,2,3} times, a 3 {0,1} times, etc:
so 120 has 4 * 2 * 2 = 16 different divisors.

[julian201]

OF COURSE!!!!!! AHHHHHHHHH!!!!!!! I wasn't considering the 0!! THANK YOU! I shall implement this IMMEDIATELY.

THANK YOU SO MUCH.

[daniel.is.fischer]

I'm impressed that you found that algorithm without much background. There are still some improvements possible for the general case and for special cases like triangle numbers. You can find them in the thread and overview for the problem after you've submitted your answer as an extra reward for good thinking. Keep it going

[chenhsi]

I thought that the formal name was triangular number, and not triangle number?

[Georg]

I thought that the formal name was triangular number, and not triangle number?

I agree.
http://en.wikipedia.org/w/index.php?tit ... edirect=no

[daniel.is.fischer]

Well, "triangular number" does fit better with "pentagonal number" etc, and neither wikipedia nor Mathworld even mention that they are also called "triangle numbers", so yes, the formal name is apparently "triangular number".
However, "triangle number" is widely used, too.

[MoHSalim]

I've been stuck on this one for a while. I have pretty newbie code and I fixed it up just a little but I can't figure out a good optimization. Is there a pattern I'm not seeing or something?

[hk]

Does this help?
1+2+3=6=3*2=(3*4)/2
1+2+3+4=10=2*5=(4*5)/2
1+2+3+4+5=15=3*5=(5*6)/2
1+2+3+4+5+6=21=3*7=(6*7)/2

[MoHSalim]

Not really.

long t = ((n*n)+n)/2; // triangle number

That's my formula I have had. My program works fine it is just too slow. I do notice a pattern of two odds and two even triangle numbers alternating. I'm also assuming that all the odd ones are divisible by 3 other than 1.

[elendiastarman]

1+2+3+4+5+6+7+8+9+10 = 55 which is not divisible by 3.

[hk]

Not really.

long t = ((n*n)+n)/2; // triangle number

That's my formula I have had. My program works fine it is just too slow. I do notice a pattern of two odds and two even triangle numbers alternating. I'm also assuming that all the odd ones are divisible by 3 other than 1.

But if you factor (n*n+n)/2 you get n*(n+1)/2.
Finding the divisors of n*(n+1)/2 is much easier than of (n*n+n)/2.

[MoHSalim]

Is that because my previous formula contained more variables? Even with the new formula the program does not finish running after a minute.

[TripleM]

Changing the formula and doesn't nothing else won't change anything; both formulas are equivalent.

But if I asked you to factorise 139*179, you'd find it a bit easier than if I asked you to factorise 24881, right?

[MacPr1mE]

Can anybody give me a proof, please, that the first triangular number with over 100 divisors is:
50400

[stijn263]

118800 has 120 divisors, but it's not a triangle number..

edit: 50400 has 108 divisors, but it's not a triangle number.. (50403 is)

Good luck