The Project Euler thread

[hondaracer600]

Re: THE project euler thread

oh

then yes, yes they do

Were you on the 1.7 bill range?

[FFR4EVA_00]

Re: THE project euler thread

level 1 get!

[iironiic]

Re: THE project euler thread

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]

Re: THE project euler thread

So Much Bullshit

[hondaracer600]

Re: THE project euler thread

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.

I keep getting 1726269243. Which is wrong. High or low? there are 4 numbers that are giving me grief, and I can't figure out what to do.

[leonid]

Re: THE project euler thread

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

[hondaracer600]

Re: THE project euler thread

[spoiler]

Again, it's collision testing. What I did, after creating my list of viable pq^a candidates, was a lazy "greedy" approach of just arranging my list of prime composites by the value they add (pq^a-p-q^b), and then, for a given q, take the composite that contributed the most value.

Obviously, this results in a few p-collisions.
So, it would appear you're still not sure what to do in the event of p-collisions?
Well, I'll tell you.
Alright. This is where my "manual" work came in. When I had a p-collision between two composites, I looked at their q values. For a shared p, one composite will have a bigger q than the other. You want to modify the one with a lower q.
You're wondering how to modify it, aren't you?
Quite literally, I looked at the value that the composite prime contributed for that composite of lower q, and I hardcoded it into an if-statement. If the value a composite is about to add to my list equals that, then don't add it. It'll find the next-best pq^a naturally. If you're dealing with the smallest prime p above sqrt(200k), then just remove the worse of the duplicates in terms of value added. I did this like 10 times or so and eventually my list was optimized without any p-collisions.

That's why I did it manually -- it was easier to just kick out the conflicting primes instead of coding and testing a collision subroutine.

That's what I do. Not correctly apparently. FUUUUU. thanks again.

[leonid]

Re: THE project euler thread

BAM!!

[iironiic]

Re: THE project euler thread

Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!

[Reincarnate]

Re: THE project euler thread

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]

Re: THE project euler thread

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]

Re: THE project euler thread

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]

Re: THE project euler thread

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]

Re: THE project euler thread

leonid, you're a beast

[Reincarnate]

Re: THE project euler thread

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)