Flash Flash Revolution: Community Forums

Flash Flash Revolution: Community Forums (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)
-   -   The Project Euler thread (http://www.flashflashrevolution.com/vbz/showthread.php?t=120818)

hondaracer600 10-27-2011 08:31 PM

Re: THE project euler thread
 
Quote:

Originally Posted by stargroup100 (Post 3558138)
oh

then yes, yes they do

Were you on the 1.7 bill range?

FFR4EVA_00 10-27-2011 08:45 PM

Re: THE project euler thread
 
level 1 get!

iironiic 10-27-2011 09:56 PM

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 10-28-2011 11:20 AM

Re: THE project euler thread
 
So Much Bullshit

hondaracer600 10-28-2011 12:02 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3557949)

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 10-28-2011 01:36 PM

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 10-28-2011 01:46 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3558460)
[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 10-30-2011 03:06 AM

Re: THE project euler thread
 
BAM!!


iironiic 10-30-2011 09:38 AM

Re: THE project euler thread
 
Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!


Reincarnate 10-31-2011 09:11 AM

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 10-31-2011 12:24 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3559824)

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 10-31-2011 12:38 PM

Re: THE project euler thread
 
Quote:

Originally Posted by iironiic (Post 3559895)
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 10-31-2011 03:22 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Reincarnate (Post 3559900)
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 11-1-2011 11:11 AM

Re: THE project euler thread
 
leonid, you're a beast

Reincarnate 11-1-2011 11:48 AM

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):

Code:

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 11-1-2011 01:25 PM

Re: THE project euler thread
 
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 11-1-2011 04:07 PM

Re: THE project euler thread
 
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 11-1-2011 07:28 PM

Re: THE project euler thread
 
Join #euler in irc.chatspike.net

Knut.Angstrom 11-3-2011 01:36 PM

Re: THE project euler thread
 
Do you know the definition of triangle numbered problem?

iironiic 11-3-2011 01:45 PM

Re: THE project euler thread
 
Quote:

Originally Posted by Knut.Angstrom (Post 3561619)
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.


All times are GMT -5. The time now is 07:23 PM.

Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution