Problem 241

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Problem 241

Post by JohnMorris »

Four hours, zero solvers. Yikes!
Image

genious999
Posts: 53
Joined: Mon Oct 20, 2008 10:48 pm

Re: I get the feeling problem 241 might be tricky...

Post by genious999 »

http://projecteuler.net/index.php?secti ... =eulerians
Googly has solved it.

But yes it does seem tricky :D

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: I get the feeling problem 241 might be tricky...

Post by daniel.is.fischer »

It was meant to be hard, but I expected some more. Let's see when the PARI one-liners roll in... :lol:
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

genious999
Posts: 53
Joined: Mon Oct 20, 2008 10:48 pm

Re: I get the feeling problem 241 might be tricky...

Post by genious999 »

Well a brute-force that checked a billion numbers a second wouldn't finish for about 31 years, so we might be waiting just a little while for those one-liners to finish. 8-)

User avatar
Tommy137
Posts: 238
Joined: Sun Feb 24, 2008 6:02 pm
Location: Cologne, Germany
Contact:

Re: I get the feeling problem 241 might be tricky...

Post by Tommy137 »

daniel.is.fischer wrote:It was meant to be hard, but I expected some more.

Maybe, we should rethink our definition of easy, medium and hard problems :D

Right now, more people solved the "medium" Problem 240 in one week than the "easy" Problem 239 in two weeks :?
Image

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 241

Post by quilan »

Yeah, this one is a complete doozy -- way harder than I thought it'd be. Time to start burning the afternoon oil to figure this one out.
ex ~100%'er... until the gf came along.
Image

helstreak
Posts: 19
Joined: Mon Jan 26, 2009 5:00 am

Re: Problem 241

Post by helstreak »

what was the inspiration for this problem? it's rather difficult....

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 241

Post by daniel.is.fischer »

Generalising perfect numbers. The limit is chosen to rule out brute force, so you have to think up a better algorithm (of course, brute-forcing to a smaller limit may be helpful for that). It is difficult, but after you've found a good algorithm, you probably think that it wasn't that difficult after all. Until then, just don't let it frighten you :)
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

gonzolino
Posts: 17
Joined: Thu Mar 12, 2009 4:17 pm
Location: Lyon, France
Contact:

Re: Problem 241

Post by gonzolino »

We can give you a hint : up to 10^60, the sum is :
1020831183124421008740176908439048405779898068335507463001800322
\o/

This problem is really amazing : in the thread, we find at least 3/4 very different approaches to solve it.

JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Re: Problem 241

Post by JohnMorris »

daniel.is.fischer wrote:It is difficult, but after you've found a good algorithm, you probably think that it wasn't that difficult after all. Until then, just don't let it frighten you :)
I eventually solved it, and I still think it was difficult!

Could I have my weekend back, please?
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 241

Post by daniel.is.fischer »

Congratulations.
Of course it's still difficult. But is it still as difficult in your eyes as it initially seemed?

Sorry, no refunds 8-)
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

JohnMorris
Posts: 64
Joined: Sun Dec 23, 2007 6:38 am

Re: Problem 241

Post by JohnMorris »

daniel.is.fischer wrote: Of course it's still difficult. But is it still as difficult in your eyes as it initially seemed?
Initially it seemed impossible, but now it's merely very, very difficult, so in that sense you're right.

Without going into details of my method, that "one minute" rule - that's really more of a guideline than a rule, isn't it?


Isn't it? :-)
Image

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 241

Post by quilan »

I find it vastly amusing that 4 days later I'm now only #27 to solve the problem. I think that just goes to show how difficult most of the user-base is also finding it. My after-thoughts now that I've solved it and can think back upon the various methods used are that it's -still- a really really hard problem. I know that I'll easily be able to squeek it under the minute rule (getting there from 71 seconds is pretty easy), but I think fully grokking the answers everyone's used (of which I was impressed, there's a number of intensely different methods) will take a long time indeed.

Edit: adding psyco.full() took it down to 50 seconds by itself. Well then.
ex ~100%'er... until the gf came along.
Image

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 241

Post by daniel.is.fischer »

Thumbo wrote:that's really more of a guideline than a rule, isn't it?
The rule is that algorithms exist, which when coded in a not too slow language and run on a not too high-end computer, solve the problem in less than a minute. Usually the tested languages include at least three of Assembler, C, Delphi, Haskell, Java, Python and the running times are very rarely above 5 seconds in any of the compiled languages.
But for the solver, it's just a guideline. If your solution is in an interpreted language and runs on a 6502-processor, I think for most problems it's impossible to get even near one minute. If on the other hand your solution in C running on a 16GHz quadcore takes hours, you know that your algorithm can be dramatically improved and it would be a good idea to think about improving your algorithm even before looking at the problem forum. If your ruby solution running on a 2GHz CPU takes two minutes, probably there are better algorithms, but yours isn't too bad.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 241

Post by daniel.is.fischer »

quilan wrote:I find it vastly amusing that 4 days later I'm now only #27 to solve the problem. I think that just goes to show how difficult most of the user-base is also finding it.
Yes, harder than we expected.
Not that we thought we'd have 100 solutions by now, but more like 40-50.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

User avatar
Sunhill
Posts: 9
Joined: Tue Apr 29, 2008 10:36 am
Location: Sydney, Australia
Contact:

Re: Problem 241

Post by Sunhill »

gonzolino wrote:We can give you a hint : up to 10^60, the sum is :
1020831183124421008740176908439048405779898068335507463001800322
Thanks for the hint. Does that mean the answer for this problem, n ≤ 1018, has around 20 digits? That probably rules me out of this one. I don't think my programming application will go that high.

But it does verify the "hunch" I had about 24, so I may persevere for the time being.

gonzolino
Posts: 17
Joined: Thu Mar 12, 2009 4:17 pm
Location: Lyon, France
Contact:

Re: Problem 241

Post by gonzolino »

Wow, there's indeed a problem (there are not so many solutions, so the result should have around 60 or 61 Digits ! I'll have a look at this in a few hours, cause there are not so many solutions;

I will give the right false-hint later !

EDIT :
OK, there was a problem in my copy paste !!! the real solution for 10^60 is :
1020831183421008740176908439048405779898068335507463001800322

And for 10^72 : 2 days on a biproc :-)
705079231534438250081370609999937550454994273445926545602155710484250242

Ans btw, I used pari-gp to handle with these numbers. Maple was enough for 10^18
Last edited by gonzolino on Thu Apr 23, 2009 9:14 am, edited 2 times in total.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 241

Post by quilan »

Sunhill wrote:Thanks for the hint. Does that mean the answer for this problem, n ≤ 1018, has around 20 digits? That probably rules me out of this one. I don't think my programming application will go that high.
You should have access to a programming language that can handle either BigInts or 64-bit integer types. There are many PE problems that fall outside of the realm of simple 32-bit answers. Heck, 1018 is ~60 bits itself.
ex ~100%'er... until the gf came along.
Image

helstreak
Posts: 19
Joined: Mon Jan 26, 2009 5:00 am

Re: Problem 241

Post by helstreak »

erg....i know how to do the problem but i can't seem to convert my algorithm to an actual program....maybe one day i'll get it :)

markr
Posts: 18
Joined: Sun Apr 02, 2006 6:19 am
Location: California, USA

Re: Problem 241

Post by markr »

How about a hint like a solution for 10^9 or the number of such numbers < 10^18?

Post Reply