Problem 289

[cyclops]

Problem 289 (View Problem)

Hi,

I'm trying to rule out stupid bugs versus flawed algorithm. I suspect maybe my algorithm is based on a flawed premise because basically there are two sub-algorithms that verify each other's results in some cases (and I haven't found a case where they contradict each other). I get a high value L(3,3)=106882. I'll probably write a brute forcer for small numbers to try to find discrepancies, but in the meantime,

Could someone verify or deny L(11,2)=5539780352 (mod 10^10)?

Could help speed up the debugging process.

Thanks.

[harryh]

Yep, L(11,2)=5539780352 (mod 10^10) looks correct

[quilan]

This problem is the slowest people-solved grower that I can remember in a LONG time. 2 days later, 9 people solved.

[cyclops]

Thanks, harryh, that did help me narrow the search quite a bit and find my error. After some revisions, the program now gives L(3,3) = 104290 as expected. Unfortunately I'm finding my code to be a debugging nightmare (I know the algorithm isn't optimal, but I'm trying to milk it as much as possible before trying to find a new one), and although it feels a bit like cheating to ask, I'm wondering if

L(3,30) = 1420222126 (mod 10^10)
L(4,25) = 795488992 (mod 10^10)

are correct.

Regarding quilan's comment: Since I'm a relative newcomer here, I'm curious as to how the number of solvers over time for this problem compares with Pivotal Square Sums (261), and also Coresilience (245), for those who remember.

I must be masochistic because I'm really enjoying the difficulty of this problem.

[harryh]

Number of solvers after 24h, 48h, 72h, 96h, 120h for a few relatively recent problems with a small number of solutions :

#257 : 9, 17, 20, 25, 27
#261 : 8, 17, 25, 30, 35
#264 :10, 17, 21, 25, 37

From problem number #277 onwards, the fastest-20 list provides a pretty good indication...

[TripleM]

.. and although it feels a bit like cheating to ask, I'm wondering if

L(3,30) = 1420222126 (mod 10^10)
L(4,25) = 795488992 (mod 10^10)

are correct.

Since it appears this may be turning out to be one of the most difficult Euler problems yet (if not the hardest), I think it would be a good idea for once to not give away any test case confirmations at all. With so many people up at the top of the leaderboard these days a problem like this is great; the less hints the better.

(And I haven't solved it yet.)

[cyclops]

Since it appears this may be turning out to be one of the most difficult Euler problems yet (if not the hardest), I think it would be a good idea for once to not give away any test case confirmations at all. With so many people up at the top of the leaderboard these days a problem like this is great; the less hints the better.

(And I haven't solved it yet.)

You've persuaded me. I think I'll be happier if I don't get confirmation, to make the problem harder. But I'll leave what I wrote up unless a moderator thinks it should be taken down.

[niino]

For reference, I remember there had been no solvers in the first 4 hours at "Perfection Quotients", Problem 241 (View Problem).

[stijn263]

SirJective said: (Problem 177 (View Problem))

I was quite surprised that this problem is being solved so slowly, with my solution being the 17th, after four days.

If I recall it correctly, I had the 25th solution three days later..

Since it appears this may be turning out to be one of the most difficult Euler problems yet (if not the hardest), I think it would be a good idea for once to not give away any test case confirmations at all. With so many people up at the top of the leaderboard these days a problem like this is great; the less hints the better.

(And I haven't solved it yet.)

I agree. For these problems the development team discusses what test cases to give (usually a small case to help understanding the problem and a bigger one for the debugging) and in my opinion that should be enough

[juris.c]

I'm curious whether just this problem happened to be so hard or it is new tendency for Project Euler?
By the way are you going to release #300 in this season or after summer break?

[hk]

I'm curious whether just this problem happened to be so hard or it is new tendency for Project Euler?

The problems have a variety of difficulty. After a number of not so difficult problems we thought that it was time to publish a hard one.

By the way are you going to release #300 in this season or after summer break?

We have not decided yet.

[zwuupeape]

Yeah! I managed to get cyclop's incorrect results!

How hard was it to fix ?

[cyclops]

Yeah! I managed to get cyclop's incorrect results!

How hard was it to fix ?

For me it was tough to go from getting L(3,3) = 106882 to the correct L(6,10), but my method was both suboptimal (in terms of running time and memory) and overly complex. I'm currently unemployed, so I have time to type out long, convoluted and illegible code.

I don't think it's giving too much away to say that by the time I got L(3,3) = 106882, I was subjectively about 45% of the way to a final solution (in terms of work, and breakthroughs). Possibly 40% is more accurate considering how much debugging there was, due to cumbersome code. But I hope that's not discouraging, because you may be closer than you think!

[utomaya]

I am curios about the number of the solvers, why it is so few?

As someone mentioned above, problem 261 is a very hard problem, but when I solved it in about Nov/16(3 weeks after the problem was released), I was the 98th or 99th, and one or two days later, the 100th arrived. I must admit #261 is harder than #289, because the time I spent on 261 is more than on #289.

In recent problems, No matter how hard it is, 100th have come within 3 weeks. somethimes even faster, 100th has come within 2 weeks.

But #289 is almost 3 weeks after it was released. But only 42 solutions, it is not resonable (compared with other "hard" problems).

Is there something wrong?

[TripleM]

I must admit #261 is harder than #289, because the time I spent on 261 is more than on #289.

The difficulty of a problem isn't just about how long you yourself took I found 261 relatively easy, and still haven't solved 289. Clearly the difficult should be based on the number of solvers, and by that aspect 289 is indeed harder.

[quilan]

I am curious about the number of the solvers, why it is so few? ... Is there something wrong?

I'll be honest, I'm rather baffled by it. You can pretty much draw all 37 of the (2,2) scenarios by brute force on a piece of paper, and that should give all the information needed really... I didn't even blink for this one, whereas others had me stumped for a while.

[zwuupeape]

EDIT: Apparently not.

Damn, I've been probably spending too much time on this :\

How about L(4, 25) = 7683575736
L(4, 5) = 6792271756

?

[quilan]

Are these correct:

L(4, 25) = 7683575736 -- No
L(4, 5) = 6792271756 -- No

[quilan]

hrmm... did I blink & all the sudden 20 people solved it this weekend, with only zwuupeape commenting on it?

[zwuupeape]

I must say, pretty much the only reason I bothered to post my code there - probably the ugliest thing I ever wrote - is that this weird coincidence was bound to occur. Anyway thanks to cyclops and quilan for helping