Problem 241

[JohnMorris]

Four hours, zero solvers. Yikes!

[genious999]

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

But yes it does seem tricky

[daniel.is.fischer]

It was meant to be hard, but I expected some more. Let's see when the PARI one-liners roll in...

[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.

[Tommy137]

It was meant to be hard, but I expected some more.

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

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

[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.

[helstreak]

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

[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

[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]

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?

[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

[JohnMorris]

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?

[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.

[daniel.is.fischer]

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.

[daniel.is.fischer]

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.

[Sunhill]

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 ≤ 10¹⁸, 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]

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

[quilan]

Thanks for the hint. Does that mean the answer for this problem, n ≤ 10¹⁸, 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, 10¹⁸ is ~60 bits itself.

[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]

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