Project Euler, what am I doing wrong?

Ramses de Norre · 2009-12-09 15:48:10

Hi

I am working on problems from project euler and I am a little stuck here. I really don't see an error in my program but my solution seems to be wrong.

I don't want you guys to solve the problem in another way or to hold my hand, I just want to make progress but after some hours it seems that I need some feedback. Maybe I'm overlooking something...

The problem it is about is problem 21:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

And this is what I've got (Haskell)

main = 
  print (sum[ x | x <- [1..9999], spd (spd x) == x])

--_Proper_ divisors so divisors 1 == []
divisors :: Integer -> [Integer]
divisors 0 = []
divisors 1 = []
divisors n = [ x | x <- [1..n-1], n `mod` x == 0]

--Sum of Proper Divisors
spd :: Integer -> Integer
spd n = sum (divisors n)

Does anyone see a flaw in my reasoning?

When I run the list comprehension from my main and manually test the numbers I get, they all are amicable numbers. And I don't see how I could miss some of them as I am really defining them exactly like in the problem...

I hope someone can shed some light because I am probably making some stupid mistake.

brisbin33 · 2009-12-09 16:54:06

do we know what the answer's supposed to be?

after reading the start of your post (just the start i swear), i came up with an only syntactical different solution.

printsums = sum [ x | x <- [1..9999], d (d x) == x ]

d n = sum . proper $ n

proper 0 = []
proper 1 = []
proper n = [ x | x <- [ 1..n-1 ], n `mod` x == 0 ]

i get 40284.

lswest · 2009-12-09 18:30:06

I just checked it on Project Euler, and it's not accepted as the right answer. So chances are the method you both are using is wrong. I know I started the problem but never finished it (in Python), and, as far as I can tell, I'm doing the same thing as you are. I'm probably not going to be much help, but my only thoughts on the matter are: Have you had a look at the proper divisors? I suggest having that array be printed out, and then figuring out the proper divisors for one or two easy terms that you can easily figure out by hand, and compare them. If they look correct, then make sure that the rest of the problem apply to the two sets you've got (the one by hand and the other via the script), and figure out if there's anything in there that shouldn't be. I'd offer more help if I could, but this is all I'm capable of offering (besides offering to put my python script up here too if you're interested).

Hope that helps a bit,
Lswest

AlecSchueler · 2009-12-09 18:31:21

brisbin, that's not that answer. I'd post it here but I don't want to spoil it for anyone. I'll say that you're a bit too high though. Maybe you're just including each n in your sum or some silly mistake like that.

(I don't know enough Haskell to say what's going wrong without taking more of a look at the code sorry)

Last edited by AlecSchueler (2009-12-09 18:33:49)

Procyon · 2009-12-09 18:44:56

If d(a) = b and d(b) = a, where a ≠ b

Ramses de Norre · 2009-12-09 19:13:24

@brisbin: I got the same result.

@Proycon: *facepalm*... I kind of suspected I was overlooking something like this...

lswest · 2009-12-09 19:16:43

Ramses de Norre wrote:

@brisbin: I got the same result.
@Proycon: *facepalm*... I kind of suspected I was overlooking something like this...

Don't worry, I overlooked that too I actually solved the problem now because of this thread, since I was doing it in python to figure out where you guys were going wrong...and I wasn't checking that a != b in my original script. I take it that procyon's answer solved this thread for you? Or do you have any further questions?

Ramses de Norre · 2009-12-09 19:24:18

Yup, I solved it now
It took one little modification of my first list comprehension.

Arch Linux

#1 2009-12-09 15:48:10

Project Euler, what am I doing wrong?

#2 2009-12-09 16:54:06

Re: Project Euler, what am I doing wrong?

#3 2009-12-09 18:30:06

Re: Project Euler, what am I doing wrong?

#4 2009-12-09 18:31:21

Re: Project Euler, what am I doing wrong?

#5 2009-12-09 18:44:56

Re: Project Euler, what am I doing wrong?

#6 2009-12-09 19:13:24

Re: Project Euler, what am I doing wrong?

#7 2009-12-09 19:16:43

Re: Project Euler, what am I doing wrong?

#8 2009-12-09 19:24:18

Re: Project Euler, what am I doing wrong?

Board footer