The Project Euler thread

[FFR4EVA_00]

level 1 get!

[iironiic]

Problem 356 will be accessible in 1 day, 9 hours, 5 minutes (Sat, 29 Oct 2011, 08:00 [America/New_York])
Current date/time on server: Fri, 28 Oct 2011, 03:55

Hahaha I'm excited!!

[FFR4EVA_00]

So Much Bullshit

[leonid]

(Quote post to avoid clicking so many buttons)
I don't like how this thread essentially gives out major hints for the last problems.
Can we stop giving hints and/or wrong attempts if a couple of posts are not enough?

hondaracer600, no offense but could you stop asking people to feed you with direct hints?? It defeats the whole purpose of project euler.

[leonid]

BAM!!

[iironiic]

Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!

[Reincarnate]

Problems like 356 are annoying because they're battles against the precision of your programming language... in huge ways

aka you need some other method to solve it because rounding errors will be the death of you no matter what.

Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.

[iironiic]

Originally Posted by Reincarnate

Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.

That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.

[Reincarnate]

Originally Posted by iironiic

That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.

There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.

[stargroup100]

Originally Posted by Reincarnate

There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.

Stupidly high is an understatement. You'd need several billion digits if you were to brute force it LOL.

in other words i cant solve this problem and it's pissing me the hell off

[Reincarnate]

leonid, you're a beast

[Reincarnate]

This was the code for my "naive" attempt (note: does not work because it requires more precision than we have access to, doing it this way. Still works great for smaller powers, though):

import os, sys
from math import sqrt, acos, cos, pi


def bigRoot(a,b,c):
    return (2 * sqrt(-(b - a*(a / 3.0))/3.0)) * cos(((acos((-((2*(a / 3.0)**2- b)*((a / 3.0)) + c)/2.0/ (sqrt(-(b - a*(a / 3.0))**3/27.0)))))/3.0)) - (a / 3.0)

def powRed(a,b,m):
    if b==1:
        return a
    if b%2==0:
        return powRed((a*a)%m,b/2,m)
    else:
        return (a*powRed((a*a)%m,(b-1)/2,m)) % m


sumTotal=0

for n in range(1,31):
    a, b, c  = -pow(2,n), 0, n     #corresponds to x^3+ax^2+bx+c 
    print "N=" + str(n) + ", biggest root = " + str(bigRoot(a,b,c))
    sumTotal=sumTotal+ int(powRed(bigRoot(a,b,c),987654321,10**8))

print "Last eight digits of power-sum: " + str(sumTotal % 10**8)

[iironiic]

Got #205 with pencil and paper. Took forever but at least I didn't have to sleep through my english class hahaha.

EDIT: Just got #53 with pencil and paper :)

[stargroup100]

The problems that I have found to be the most rewarding to solve with pencil/paper rather than coding are: ("*" following the number indicates a high difficulty, "#" following a number represents a fairly tedious problem in terms of manual work)

6, 9, 26*, 28, 29#, 33, 39, 69, 108, 138*#

I have obviously not looked at every problem between 1 and 108, but when I find more problems that can be done with pencil/paper I'll edit this.

[leonid]

Join #euler in irc.chatspike.net

[Reincarnate]

I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).

[iironiic]

Originally Posted by Reincarnate

I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).

I did the same thing. Felt lame as well but hey, at least we got the answer haha.

EDIT: Got #179 just now.

[Reincarnate]

stuck on 126 ffffuuuu

nvm got it

[Reincarnate]

Pumped out a few more today... 137 was a bit of a challenge, but the solution is an interesting one. I'm only on page 4/8 of total problems (when arranging them by # solved) and the questions are definitely getting tougher. Problems 338's been out since May 2011 and it still hasn't reached 100 solvers yet. 344 looks beastly, too.

Hit level 7, going to bed.

[x_lambourghini_x]

I tried, but because I can't do math for the life of me, I ragequit.