The Project Euler thread

[hondaracer600]

Originally Posted by stargroup100

oh

then yes, yes they do

Were you on the 1.7 bill range?

[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

[hondaracer600]

Originally Posted by Reincarnate

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]

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

Originally Posted by Reincarnate

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

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

[Knut.Angstrom]

Do you know the definition of triangle numbered problem?

[iironiic]

Originally Posted by Knut.Angstrom

Do you know the definition of triangle numbered problem?

Anything of the form k(k+1)/2 for some k in the natural numbers:

1, 3, 6, 10, 15, 21, etc.

Also, got #216 and #218 (o: Thinking about #241 now.