View Full Version : Math Related Python Problem

Lster

March 21st, 2008, 11:28 AM

Hi

Firstly, thanks to those who recommended I learned Python - I love the language more every time I find out another of it's features. I've already started using it for solving Project Euler problems but I'm having a few problems with one of the challenges that I believe is probably related to my lack of knowledge.

I'm trying to solve this puzzle:

http://projecteuler.net/index.php?section=problems&id=183

Now I played around with it all and came to a solution. However, Project Euler states:

For example, ΣD(N) for 5 ≤ N ≤ 100 is 2438.

And I get 3690, instead. I've checked Python documentation again and again and I can't see any errors. I did find this page, though:

http://erl.nfshost.com/wordpress/2008/02/29/euler-183/

Which shows the method I am attempting... Could anyone give me any pointers on why it isn't working? Just a nudge in the right direction would be appreciated! :)

Here's my code:

...

Thanks,

Lster

dvase

March 21st, 2008, 02:50 PM

I would check to make sure that python is doing floating point arithmetic where required. I'm just a beginning python programmer myself, but I have had problems in the past with python assuming integer arithmetic when I really needed floating point calculations. When declaring a variable and giving it a value (e.g. t in your code), declaring it as "t = 0.0" seems to tell python that it is floating point number not an integer.

Martin Witte

March 21st, 2008, 10:26 PM

I'm not too sure what's going wrong. Your D function seems to work, I've tried to write the problem like this

def D ( x ):

while x % 2 == 0:

x /= 2

while x % 5 == 0:

x /= 5

if x == 1:

return -1

return 1

def M(N):

Pmax = 0

retval = (0, 0)

for k in range(1, N + 1):

r = N/float(k)

P = r**k

if P > Pmax:

Pmax = P

retval = (N**k, k**k)

return retval

sum = 0

for N in range(5, 101):

m = M(N)

d = D(m[1]) * N

sum += d

print sum

also with a wrong result...

Lster

March 21st, 2008, 11:24 PM

dvase, that's a very good point but I have already tried that and I still can't get it to work. Any ideas?

Thanks,

Lster

Lster

March 21st, 2008, 11:30 PM

Martin Witte, I can't see anything wrong with your code, myself. Anyone spot any mistakes? I am really stumped!

Wybiral

March 22nd, 2008, 12:18 AM

Do we have a version in any other language (other than mathematica) that does work so I can compare them?

KnightWhoSaysNi

March 22nd, 2008, 01:14 AM

The code below works for the example (the only difference is simplifying the fraction before the terminating test). But the floating-point division and the GCD function both overflow when used on the actual problem size.

I guess the brute-force method could be fixed by comparing the P(n) using integers and calculating GCD non-recursively. However a more mathematical solution may be in order.

def Pmax(n):

pmax=0

for k in range(1,n):

num=n**k

denom=k**k

p=(float)(num)/(float)(denom)

if p>pmax:

pmax=p

pmax_num=num

pmax_denom=denom

return (pmax_num,pmax_denom)

def gcd(n,d):

if d==0: return n

return gcd(d,n % d)

def Terminating(x):

(n,d)=x

g=gcd(n,d)

d /= g

while d % 2 == 0:

d /= 2

while d % 5 == 0:

d /= 5

if d == 1:

return True

return False

def D(n):

if Terminating(Pmax(n)):

return -n

else:

return n

sumd=0

for n in range(5,101):

sumd += D(n)

print sumd

pmasiar

March 22nd, 2008, 03:12 AM

OP:

Are you aware that "n / a" returns integer, if both n and a are integers? It's old Python wart, will be removed in Py3K, due this september.

Wybiral

March 22nd, 2008, 03:57 AM

You should be able to fix the floating-point problem with the Decimal class.

My version of KnightWhoSaysNi's implementation:

from decimal import Decimal

def pmax(n):

pm = 0

for k in xrange(1, n):

num = n ** k

denom = k ** k

p = Decimal(num) / Decimal(denom)

if p > pm:

pm = p

result = (num, denom)

return result

def gcd(n, d):

while d:

n, d = d, n % d

return n

def isterminating(x):

n, d = x

d /= gcd(n, d)

while d % 2 == 0:

d /= 2

while d % 5 == 0:

d /= 5

return -1 if d == 1 else 1

print sum(n * isterminating(pmax(n)) for n in xrange(5, 101))

But if you try to solve the 5-1000 version with this, well, I hope you have a lot of time to wait for it :)

Lster

March 22nd, 2008, 03:51 PM

Well, I've coded a hybrid that I think is faster still (using the calculus insight in that blog). It becomes slower and slower, still, and taking into account it's avergae speed depreciation, it will take almost an hour.

I'm on 43% right now...

...

Jessehk

March 22nd, 2008, 04:04 PM

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

:)

Lster

March 22nd, 2008, 04:12 PM

I was thinking about that too. When I do solve it, I can see how others have kept speed acceptable!

63% now...

Wybiral

March 22nd, 2008, 04:41 PM

Have you tried 185 (http://projecteuler.net/index.php?section=problems&id=185) yet? That one has been my favorite so far :)

Lster

March 22nd, 2008, 05:15 PM

I had a small try and can solve the smaller one with optimized brute force (that sounds like somewhat of an oxymoron). Have you managed to complete it? :)

Wybiral

March 22nd, 2008, 05:30 PM

I had a small try and can solve the smaller one with optimized brute force (that sounds like somewhat of an oxymoron). Have you managed to complete it? :)

Yeah, but even mine was somewhat brute (there's some theory behind it though). The C version solves it in a second or two, the Python one is a bit slower (lots of tight looping, it might benefit from psyco or something, but I haven't got around to trying that yet). I can send it to you if you'd like.

Lster

March 22nd, 2008, 05:56 PM

I'd love to see a solution to it! I'm guessing you use brute force searching but exclude some values you know can't be in those positions. Also, on each string, you can do checks to see if it is a possible candidate.

Those were the first two things I noticed... I'd be interested to see what you have found! :)

... 98%!

Lster

March 22nd, 2008, 06:05 PM

Done!

It was... [Now removed!]! (The answer is white to hide it from those who don't want to see!)

Wybiral

March 22nd, 2008, 06:17 PM

I'd love to see a solution to it! I'm guessing you use brute force searching but exclude some values you know can't be in those positions.

Actually, mine doesn't exclude anything (I didn't try too hard, but it looked like the 0 correct one was the only rule that could be used to deduce anything). Well, you'll see... I PM'd it to you.

Powered by vBulletin® Version 4.2.2 Copyright © 2015 vBulletin Solutions, Inc. All rights reserved.