Problem 012

[cheesecakenl]

Hi,

I am having a bit of trouble solving this one. Here is some pseudo code using the 1+2+3=6=3*4/2 principle. Atleast I think but
it keeps getting me the wrong answer.

I guess there is something wrong with my assumption "if the n/2 and n+1 values are co-prime they will have the same number of dividers and you can just multiply them to get the number of dividers for the corresponding triangle number n(n+1)/2 "

Code: Select all

n = 1
while div < 501
	val1 = n/2
	val2 = n+1

	if coprime(val1,val2)
		nr = getNumberOfDiv(val1)
		div = nr * nr 
	
	n++

Results:
Triangle number: 258840
Divisors: 576 (24x24)

[Lord_Farin]

What about n = 24? 12 has more divisors than 25 (6 vs. 3). Still, you are not too far off. Try to think in prime factorisations.

[cheesecakenl]

I solved it. According to the pdf there is some optimization available in calculating the number of divisors.

Expand

D(28) = 2² * 7¹ = (2+1) * (1+1) = 3 * 2 = 6
Using the sieve I can get a list of all prime factors for 28. Except I don't know how to get from D(28) to the (2+1) * (1+1) part.

Can anyone PM this ?

[rayfil]

PM sent.

[FF_Daniel]

Can somebody please send me a pm with the area of the result? A diffrence of one million is no problem!

[dufoli]

Hello,

I have produce a code in python but it seems that I do a mistake because I do not get result ok message.

EDIT: ok found small mistake

[kavcict]

Hi,

I'm currently having a speed problem with my Python code. My code has three different functions. The first one gives me the triangle sum of a given number, the second functions gives me how many divisors this numbers has, the last one solves the problem. The code works fine with small numbers, but with numbers greater the 100 the code slows down. I've read all post in this topic, but i can't find a solution to my problem.

Can anybody help me?

[PurpleBlu3s]

Hi,

I'm currently having a speed problem with my Python code. My code has three different functions. The first one gives me the triangle sum of a given number, the second functions gives me how many divisors this numbers has, the last one solves the problem. The code works fine with small numbers, but with numbers greater the 100 the code slows down. I've read all post in this topic, but i can't find a solution to my problem.

Can anybody help me?

It sounds like you need to look at your algorithm for getting divisors and try and see how you can make it more efficient.

[kavcict]

It sounds like you need to look at your algorithm for getting divisors and try and see how you can make it more efficient.

I've check the divisor algorithm and found a solution to my problem I will try to tweak the code to go a little bit faster.

Python
Mac OS X Lion 2.66 GHz Intel Core 2 Duo, 15sec
Windows 7 2.33GHz Intel Core 2 Quad, 8 sec

[extremeblueness]

Okay. So here's my problem:

After fixing my program's speed, I got the number within half a minute.

However, when I input the number, it says that its not the answer.

Properties of my number:

-576 divisors
-index of more than 16000

Also, I checked my data with a triangle number calculator and a divisors calculator. My data was confirmed.

Any ideas as to why its not accepting my answer?

[hk]

Okay. So here's my problem:

After fixing my program's speed, I got the number within half a minute.

However, when I input the number, it says that its not the answer.

Properties of my number:

-576 divisors
-index of more than 16000

Also, I checked my data with a triangle number calculator and a divisors calculator. My data was confirmed.

Any ideas as to why its not accepting my answer?

the index is too high.

[extremeblueness]

In that case, I'm left with this question: why isn't my program calculating correctly for one or more numbers? The triangle numbers are right, so there must be something wrong with the divisors method. But I can't figure out what it might be. The thing is, its a brute force method, so it SHOULDN'T calculate incorrectly when it calculates correctly for the vast majority of numbers.

edit: never mind. I was just randomly disabling parts of my code, and for some reason, fixed it when i took something out. I still can't figure out why disabling that part worked.

[youssef]

Hi, i'm not really stuck , but i was trying to make a programm to calculate the number of factors of a given integer n, but it doesn't work : it seems to enter an infinite loop or something like that: I was hoping you gus could help me figure out what is wrong with my programm, so here is the code (don't be harsh on me, i've only started learning python two days ago):

Edit: Code removed by moderator -- please read the big red box at the top of the forum.

PS: English isn't my native language, so I 'm sorry for the mistakes

[thundre]

If you have two while loops nested, the outer condition is only checked when the inner loop exits. In your case, your inner condition will never be false, so the inner loop becomes infinite.

I also question whether you even need two nested loops for your purpose. I think one would be enough.

[thefloppyfish]

Im really confused, am I supposed to be finding unique divisors as shown in the example or can one divisor be used multiple times. For example for 36 would it have 9 divisors [1, 2, 3, 4, 6, 9, 12, 18, 36] or 12 divisors [1, 2^2, 3^2, 4, 6^2, 9, 12, 18, 36]?

[MuthuVeerappanR]

36 would have 9 divisors..

[hk]

If you're still stuck with this problem you might look at :number of divisors or number of divisors

[sriramrajan]

My answer has 112 divisors / factors and is the first one in the series but was declared wrong.

The previous one with 28 factors is 73536 is the 383^rd in the list:

73536 , Factors: [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192, 383, 766, 1149, 1532, 2298, 3064, 4596, 6128, 9192, 12256, 18384, 24512, 36768, 73536] , #Factors: 28

What does prime factors have to do with this problem? Here's my program listing the first 10 triangular numbers:
1 , Factors: [1] , #Factors: 1
3 , Factors: [1, 3] , #Factors: 2
6 , Factors: [1, 2, 3, 6] , #Factors: 4
10 , Factors: [1, 2, 5, 10] , #Factors: 4
15 , Factors: [1, 3, 5, 15] , #Factors: 4
21 , Factors: [1, 3, 7, 21] , #Factors: 4
28 , Factors: [1, 2, 4, 7, 14, 28] , #Factors: 6
36 , Factors: [1, 2, 3, 4, 6, 9, 12, 18, 36] , #Factors: 9
45 , Factors: [1, 3, 5, 9, 15, 45] , #Factors: 6
55 , Factors: [1, 5, 11, 55] , #Factors: 4
....

The maximum value is for 437580 with 144 factors and is the 944^th triangle number among the first 1000 triangle numbers

Any idea if I have missed anything here ?

[jaap]

My answer has 112 divisors / factors and is the first one in the series but was declared wrong.

The question is not asking for the first one with 112 divisors, but for

... the first triangle number to have over five hundred divisors?

[sriramrajan]

Thanks. My bad, I read it as a hundred divisors.. missing the five!!! Sorry.