Jump to content

Highly divisible triangular number - Python

If you have never heard of https://projecteuler.net , you should check it out. They have a whole list of very interesting mathematical problems for you to solve.

I am having trouble with one of those problems, this one: https://projecteuler.net/problem=12

My code has been written and I understand how the problem should be solved, my solution is probably not the most efficient one though, but there is something going on with my program that I do understand.

For some reason it does not what it has to do, and I still think my code is correct, I atleast can not see what is causing the errors.

 

Here is my code:

def hasover500divisors(n):    divisors = 0    for i in range(1, n + 1):        if n % i == 0:            divisors += 1    if divisors < 501:        return False    else:        return True    def getvalue(n):    return (n * (n + 1)) / 2n = 1while hasover500divisors(getvalue(n)) == False:    n += 1firstnumbervalue = (n * (n + 1)) / 2print(firstnumbervalue)

And here is the error log:

Traceback (most recent call last):  File "D:\Coding\Python\eclipse\highly-divisible-triangular-number\main\highlydivisibletriangularnumber.py", line 23, in <module>    while hasover500divisors(nvalue) == False:  File "D:\Coding\Python\eclipse\highly-divisible-triangular-number\main\highlydivisibletriangularnumber.py", line 9, in hasover500divisors    for i in range(1, n + 1):TypeError: 'float' object cannot be interpreted as an integer

Could someone explain me what goes wrong?

 

Also, as I have noticed, my debugging skills are definitely not superb yet, could someone suggest me some ways to improve them? 

 

Thank you very much.

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

for error , just to a modulus calculation to be sure the object is an integer

 

 

 

 

python debugging = print everything everytime and do one number by hand, then run the program for that and see where tis wrong

"Unofficially Official" Leading Scientific Research and Development Officer of the Official Star Citizen LTT Conglomerate | Reaper Squad, Idris Captain | 1x Aurora LN


Game developer, AI researcher, Developing the UOLTT mobile apps


G SIX [My Mac Pro G5 CaseMod Thread]

Link to comment
Share on other sites

Link to post
Share on other sites

for error , just to a modulus calculation to be sure the object is an integer

 

I am sorry, but what do you mean by this? I am using the modulus operator in line 10.. Not sure what your suggestion was though

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Try using " range(int(a)) " and range(int(a), len( B)) .

 

Your error is : 'float' object cannot be interpreted as an integer

You simply have an object that you haven't defined as an integer,or isn't an integer.A float object is simply a decimal floating point.

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

def getvalue(n):    return (n * (n + 1)) / 2

the /2 division makes it so that the return value of the function is a float, and when you then use that value in the range operator i becomes float too, and you can't use modulus on floats

a solution is to use the integer division operator //, which is fine because n*(n+1) is always even, so dividing it by two gives a whole number

Link to comment
Share on other sites

Link to post
Share on other sites

I am sorry, but what do you mean by this? I am using the modulus operator in line 10.. Not sure what your suggestion was though

sorry brain fuck. also not that fluent in py anymore

 

getvalue(n) will return you a float when n.../2 is not an int. so you need to make sure that is an integer, and then all will be ok

"Unofficially Official" Leading Scientific Research and Development Officer of the Official Star Citizen LTT Conglomerate | Reaper Squad, Idris Captain | 1x Aurora LN


Game developer, AI researcher, Developing the UOLTT mobile apps


G SIX [My Mac Pro G5 CaseMod Thread]

Link to comment
Share on other sites

Link to post
Share on other sites

Oh, also : 

"In Python 2 the / operator returns an integer if both operands are integers - rounding the result down if necessary. So 3/2 would be 1 in Python 2. In Python 3 this behavior has been changed, so that / always returns a float even if both operands are integers. So 3/2 would be 1.5 and 4/2 would be 2.0."

 

The divison by 2 returns a float,but you're trying to use it as an int.

Replace the "/" with a "//",as @Ciccioo said.

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to comment
Share on other sites

Link to post
Share on other sites

Others seem to have solved the error so here's a hint on the solution

 

1) Instead of calculating (n * (n + 1)) // 2 every time, just keep a running sum and add the new number every loop.

 

2) Only check for factors up to sqrt(n) and each time you find 1, count it as 2 factors.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

the /2 division makes it so that the return value of the function is a float, and when you then use that value in the range operator i becomes float too, and you can't use modulus on floats

a solution is to use the integer division operator //, which is fine because n*(n+1) is always even, so dividing it by two gives a whole number

Aha, I did not know this. I just started with Python a few days ago and I thought I could do some Project Euler challenges to become more familiar with the language. I had never read that / returns a float though. Good to know I now know. :)

Thank you.

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Others seem to have solved the error so here's a hint on the solution

 

1) Instead of calculating (n * (n + 1)) // 2 every time, just keep a running sum and add the new number every loop.

 

2) Only check for factors up to sqrt(n) and each time you find 1, count it as 2 factors.

 

What do you mean by "keep a running sum"?

 

Does hint 2 work? That seems a pretty cool hack, could you explain more about it?

 

Thank you.

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

What do you mean by "keep a running sum"?

Does hint 2 work? That seems a pretty cool hack, could you explain more about it?

Thank you.

A triangle number as you've figured out is the sum from 1 to x. The running sum would just be keeping track of the total sum as you count up through the loop instead of calculating it every time using that formula. Something like:
sum = 1counter = 1while not hasover500divisors(sum):    counter += 1    sum += counter
It might not be a huge performance boost but since the solution is a fairly large number it may speed things up a little over hundreds of millions of loops.

Hint 2 uses the fact that for every factor f of the number n, n / f is also a factor. So if you only go up to sqrt(n) and count by 2s it takes care of the n / f factors without actually having to find them since 1 factor will be < sqrt(n) and the matching factor will be > sqrt(n).

The only thing to watch out for is that there will be an off by 1 error if n is a perfect square, but triangle numbers have the property that they are never perfect squares so that's not a problem in this case.

Edit: and by never perfect squares I mean besides the ones that are...like 36. But it doesn't matter here.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

the /2 division makes it so that the return value of the function is a float, and when you then use that value in the range operator i becomes float too, and you can't use modulus on floats

a solution is to use the integer division operator //, which is fine because n*(n+1) is always even, so dividing it by two gives a whole number

 

I implemented the integer division operator. But when I now try to execute the program it is stuck in a never ending loop, I suspect. I do not get any response. I exited out of it with ctrl + c and it said this:

Traceback (most recent call last):  File "main.py", line 21, in <module>    while hasover500divisors(getvalue(n)) == False:  File "main.py", line 9, in hasover500divisors    if n % i == 0:KeyboardInterrupt

This is my current code:

def hasover500divisors(n):    divisors = 0    for i in range(1, n + 1):        if n % i == 0:            divisors += 1    if divisors < 501:        return False    else:        return Truedef getvalue(n):    return (n * (n + 1)) // 2     n = 1    while hasover500divisors(getvalue(n)) == False:    n += 1     firstnumbervalue = getvalue(n)     print(firstnumbervalue)

I am sorry @fizzlesticks , I did not implement your second hint yet..

Edit: The file is called differently because I changed to an other pc with Manjaro installed on it, I just created a new file and put the code in it. :)

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

It's not never ending, it's just really slow. Try adding some print statements to see. That's where hint 2 comes in.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

It's not never ending, it's just really slow. Try adding some print statements to see. That's where hint 2 comes in.

How long should it be running? I believe it is running for almost half an hour..

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

How long should it be running? I believe it is running for almost half an hour..

 

It is still running..

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

It is still running..

Your original solution will take months or even years to finish. With hint 2 my program takes about 5 seconds.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

Your original solution will take months or even years to finish. With hint 2 my program takes about 5 seconds.

Good. I'll get working on implementing hint two. But not every sqrt(n) gives an integer, if I cast it into an integer will that cause any problems?

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Good. I'll get working on implementing hint two. But not every sqrt(n) gives an integer, if I cast it into an integer will that cause any problems?

Nope, casting to an int is exactly what you need to do.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

Nope, casting to an int is exactly what you need to do.

 

That is brilliant. It works and it is correct. Thank you very much, without you I would have waited months before it came up with the correct solution :P

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Your original solution will take months or even years to finish. With hint 2 my program takes about 5 seconds.

i tried to do it for curiosity, and your method takes only a quarter of a second in js

Link to comment
Share on other sites

Link to post
Share on other sites

i tried to do it for curiosity, and your method takes only a quarter of a second in js

Ya, simple math isn't really Python's strong point.

1474412270.2748842

Link to comment
Share on other sites

Link to post
Share on other sites

i tried to do it for curiosity, and your method takes only a quarter of a second in js

That is really interesting. I have another project which takes a long time calculating in Python, I will see if it takes less time in another language, maybe js.

Thank you.

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

That is really interesting. I have another project which takes a long time calculating in Python, I will see if it takes less time in another language, maybe js.

Thank you.

yeah, give it a try

i did a couple more experiments after i posted here on the forum, and goddamn i couldn't write a c++ program significantly faster than the js script. it was actually like 4x slower if i compiled it with -O0

also, fizzlesticks' method takes 7 seconds to run in js... on my phone. 1.2ghz snapdragon 400, on internet explorer

at this point i just believe that js is actually very fast if you don't use all of its object-weirdness

Link to comment
Share on other sites

Link to post
Share on other sites

yeah, give it a try

i did a couple more experiments after i posted here on the forum, and goddamn i couldn't write a c++ program significantly faster than the js script. it was actually like 4x slower if i compiled it with -O0

also, fizzlesticks' method takes 7 seconds to run in js... on my phone. 1.2ghz snapdragon 400, on internet explorer

at this point i just believe that js is actually very fast if you don't use all of its object-weirdness

 

This is indeed very interesting. In my test the Javascript code is 47.5 times faster than my Python code! (<-- using @fizzlesticks ' hint on both of them)

That is pretty incredible.

 

 

 

Could you share your Javascript code? As I just started scripting with JS a few weeks ago I am interested in seeing some good code, so I can learn from it. (I assume your code is 'good code', may I assume that?)

window.onload = function() {	var timeBefore = new Date().getTime();	var n = 1;	while (hasover500divisors(getvalue(n)) == false)		n++;	var timeAfter = new Date().getTime();	var firstnumbervalue = getvalue(n);	document.getElementById('value').textContent = firstnumbervalue;	var timeDifference = timeAfter - timeBefore + "ms";	document.getElementById('time').textContent = timeDifference;}function hasover500divisors(n) {	divisors = 0;	for (var i = 1; i < Math.sqrt(n) + 1; i++) {		if (n % i == 0)			divisors += 2; 	}	if (divisors < 501)		return false;	else		return true;}function getvalue(n) {	return (n * (n + 1)) / 2;}
# Highly divisible triangular numbers - Project Euler problem 12# author: maeb# 2014from math import sqrtfrom time import timedef hasover500divisors(n):    divisors = 0    for i in range(1, (int)(sqrt(n) + 1)):        if n % i == 0:            divisors += 2    if divisors < 501:        return False    else:        return Truedef getvalue(n):    return (n * (n + 1)) // 2timebefore = time()     n = 1    while hasover500divisors(getvalue(n)) == False:    n += 1timeelapsed = time() - timebeforefirstnumbervalue = getvalue(n)print("The first triangular number to have over 500 divisors : " + str(n))print("Its value : " + str(firstnumbervalue))print(str(timeelapsed) + "s")# The first triangular number to have over 500 divisors : 12375# Its value : 76576500

Learning

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×