Flash Flash Revolution: Community Forums (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)

 FFR4EVA_00 10-19-2011 10:41 PM

for getting stargroup mad at people leaking answers EXCEPT NOT BECAUSE WE HAVE...

http://projecteuler.net/

what you do is simple:
1. make an account
2. open a problem
3. solve the shit out of it
4. rinse and repeat

a lot of the problems, ESPECIALLY later on, require you to find a general solution via programming and plug some ridiculously large parameters into them

anyway, i have completed:
1-13, 16, 18, 28, 33, 52, 67, 79, 108, 110, 157, 267, 355

and i am working on something...

 Zageron 10-19-2011 11:43 PM

I've completed 3 of the puzzles so far, mostly because I have very little time to complete them. I will be going in linear order from start to finish! Using C++ as my language because I'm taking a course on it right now.

Excellent idea ffr4eva.
When people run into problems they can post their questions here, just remember to hide your solutions in spoiler tags and try not to ever post the complete solution!

 YoshL 10-20-2011 12:54 AM

Quote:
 Originally Posted by Zageron (Post 3553814) I've completed 3 of the puzzles so far, mostly because I have very little time to complete them. I will be going in linear order from start to finish! Using C++ as my language because I'm taking a course on it right now. Excellent idea ffr4eva. When people run into problems they can post their questions here, just remember to hide your solutions in spoiler tags and try not to ever post the complete solution!

i have 1-25, 28 and 30
And i work with java

 reuben_tate 10-20-2011 06:09 AM

So far I've done 1,2,3,5 and 6. I just learned about the bigInteger type in Java so now I'll be using that (since the 'long' type isn't ****ing long enough -__-.)

 YoshL 10-20-2011 10:30 AM

Quote:
 Originally Posted by reuben_tate (Post 3553983) So far I've done 1,2,3,5 and 6. I just learned about the bigInteger type in Java so now I'll be using that (since the 'long' type isn't ****ing long enough -__-.)
hehe, i did all them without using the bigInteger type.

I used manual math with arrays of integers

 reuben_tate 10-20-2011 08:51 PM

Quote:
 Originally Posted by YOSHl (Post 3554031) arrays of integers
Sounds like how the bigInteger type would be implemented. I'd rather just use that, I find no point in implementing a new data structure if one is already implemented for me to use already. :razz:

 iironiic 10-20-2011 09:03 PM

This seems really interesting. I could try to do this on my free time to work on my computer skills.

 emerald000 10-20-2011 11:45 PM

I'm currently at 49, using mostly Maple. I have done a couple in C++ too, where speed mattered.

I should get back into it.

Friend key is 62306152188978_1d29510ddc0c52e8c33db3cdbaf399db for interested people.

 leonid 10-20-2011 11:47 PM

* Working on P83 *

I'm mostly using Ruby and C

My friend key: 1858629421787_a864c4e88f44e36b8023644c0f14493e

 iironiic 10-21-2011 12:24 AM

I just started today and got 1, 2, 3, 5, 6, 7, 9, 10, 16, 20, 25, 45, 48, and 52 solved. I'm using Mathematica here.

Friend Key: 76814575274714_b466b39d7ef7730e66d3da5b16df2525

 reuben_tate 10-21-2011 02:20 AM

By the way... Friend Key: 41335338220707_9d1fa87f00c010a47b494214e8b3416e ^_^

EDIT:
I managed to do a few today, and now I have 1-10 done. ^_^

Quote:
 remember to hide your solutions in spoiler tags and try not to ever post the complete solution!
I would, but I don't know how much code I could give before giving the answer away. =/

 Reincarnate 10-21-2011 09:39 AM

I was into this for a while but got bored. It's a lot of fun, though. Some of the later problems are very tricky.

 iironiic 10-21-2011 01:00 PM

@leonid: I got an answer to #80 but I don't understand why it's not the correct answer. Can you help me figure out the problem in my code?

Just to see if there is something wrong in my code, I tried using my program to help me determine some values. Let's define the digital sum of the first 100 digits of radical n to be f(n).

Are these values correct? I chose a few test numbers just to see if my program is telling me the right digital sum. It did tell me that f(2) = 475 which was given in the problem.

f(3) = 441
f(7) = 398
f(35) = 440
f(69) = 439
f(95) = 460

Any help would be appreciated. Thanks!

 emerald000 10-21-2011 01:35 PM

From what I can see, you seem to be rounding off your 100th decimal.

 iironiic 10-21-2011 02:47 PM

Quote:
 Originally Posted by emerald000 (Post 3554695) From what I can see, you seem to be rounding off your 100th decimal.
Well... in the case of radical 2, this is the string of digits I got from my program: {141421356237309504880...}. This is including that one digit to the left of that decimal point because the sum from that digit to the 99th decimal digit is the given 475. What confuses me is this phrase: "first one hundred decimal digits". Does this include or exclude that beginning digit? If it excludes it, the sum should've been 481.

I don't think it's a rounding error because the 100th decimal digit of radical 2 is 7, which would round the 99th decimal digit up. When I created that set of digits, 2 was the last element of that set, so that doesn't seem to be the problem in my program.

 emerald000 10-21-2011 03:17 PM

Let's take f(95). Its 100 digits are: (note my program counts backwards)

which gives a sum of 459. The 101st decimal is a 6, so if rounded up the 7, you would get to your answer of 460.

And yes the problem isn't clear, but thanks to the example, you can understand they mean to have 100 significant digits.

 Reincarnate 10-21-2011 07:20 PM

hmm maybe I will get back into this

seeing leonid ahead of me is making my competitive core act up (by that I mean he could kick my ass at this shit but idgaf)

heh solved problem 68 in excel

 iironiic 10-21-2011 08:37 PM

Quote:
 Originally Posted by emerald000 (Post 3554738) Let's take f(95). Its 100 digits are: (note my program counts backwards) which gives a sum of 459. The 101st decimal is a 6, so if rounded up the 7, you would get to your answer of 460. And yes the problem isn't clear, but thanks to the example, you can understand they mean to have 100 significant digits.
Thanks! I just got 80 and 69 now! :)

 fido123 10-21-2011 10:58 PM

I think I'm going to get started with this. Wanted to work on my programming skills. On my reading week and nobody else I know is so why not. Probably going to work in C or Perl.

 leonid 10-21-2011 11:25 PM

Problem 96 is solving 50 sudoku problems. I'm very tempted to cheat

 danny53x 10-21-2011 11:48 PM

How do I learn this stuff and become a cool programmer like you guys ; _;

 TC_Halogen 10-22-2011 03:16 AM

I'm interested in playing this but I have very little coding experience, haha.

 Reincarnate 10-22-2011 02:20 PM

Good way to learn imo

 stargroup100 10-23-2011 03:38 AM

Quote:
 Originally Posted by danny53x (Post 3555090) How do I learn this stuff and become a cool programmer like you guys ; _;
Project Euler is a set of problems that encourages the use of clever math to simplify programming problems. If you're not inherently good at math, this is gonna be really hard for you no matter how someone teaches you. (Except for the first few problems, which are pretty easy.)

If, on the other hand, you just want to learn programming, this is one way of starting out. At least it gives you a goal.

Man, I need to find more time to do this.

 foilman8805 10-23-2011 03:53 AM

Thanks OP for giving me something to do with my brain while I'm in between jobs. This is awesome. I'll be programming in MATLAB/Octave. I just did the first two problems as a bit of a warm up and it was a lot of fun.

Problem 1

Problem 2
Had to first write a function to calculate the numbers in the Fibonacci sequence given any input:

I then implemented that function in the script file below to find the solution:

 foilman8805 10-23-2011 04:11 AM

Interesting, I actually had to augment the source code in MATLAB in order to do Problem 3.

For some reason MATLAB arbitrarily sets a limit on prime factoring numbers larger than 2^32. Opened up the factor.m and changed it to 2^50, so this solution pretty much became a one-liner.

Problem 3

 Reincarnate 10-23-2011 11:23 AM

hit a wall with this problem :|

 Reshiram 10-23-2011 01:33 PM

I'm not gonna use programs. :3

Problem 1:

 stargroup100 10-23-2011 02:04 PM

Upon first glance, that problem looks pretty trivial. But since Rubix is having trouble with it, it must be far from that. LOL

I'll take a crack at it.

 stargroup100 10-23-2011 02:18 PM

After taking a look at the problem, here's what I have so far. (I'm sure you already figured out this much, it's all the obvious stuff.)

Problem 355:

I'll edit with more content once I figure out more. BRB FOOD LOL

 dag12 10-23-2011 03:27 PM

Sounds like you could just write a script for euler's totient function and then run a for loop or something >.>
Though I'm sure there's a more elegant way of doing it.

Also, any way to check answers without registering?

 Reincarnate 10-23-2011 03:28 PM

Quote:
 Originally Posted by dag12 (Post 3555944) Sounds like you could just write a script for euler's totient function and then run a for loop or something >.> Though I'm sure there's a more elegant way of doing it. Also, any way to check answers without registering?
tried this :<

and no you have to register

 stargroup100 10-23-2011 04:11 PM

UGH

okay this problem is seriously impossible tackling it the way I'm doing it unless there's some beautiful optimization trick

this is not working

 Reincarnate 10-23-2011 04:24 PM

getting close but still off

the way I am tackling it is actually very similar to what you posed above (raising primes to powers) but figuring out where to fix things is tricky

 iironiic 10-23-2011 04:38 PM

Should 99 be in your sorted mainlist for Co(100)?

I'm thinking about an approach right now, but I haven't come up with anything yet.

 Reincarnate 10-23-2011 04:42 PM

Quote:
 Originally Posted by iironiic (Post 3555968) Should 99 be in your sorted mainlist for Co(100)? I'm thinking about an approach right now, but I haven't come up with anything yet.

 Reincarnate 10-23-2011 05:36 PM

Hm somehow it's one off, wtf

 LongGone 10-23-2011 05:51 PM

Quote:
 Originally Posted by stargroup100 (Post 3555927) Problem 355:

 stargroup100 10-23-2011 05:56 PM

 Reincarnate 10-23-2011 06:00 PM

can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)

 stargroup100 10-23-2011 06:03 PM

I'm trying to find the error as well

 LongGone 10-23-2011 07:00 PM

Quote:
 Originally Posted by Reincarnate (Post 3556009) can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)

 stargroup100 10-23-2011 07:10 PM

edit2: ok I was being stupid

EDIT: Rubix, your answer might be wrong but it looks pretty close :D

 Reincarnate 10-23-2011 07:13 PM

A step-by-step runthrough of the Co(100) process:

 stargroup100 10-23-2011 07:21 PM

 Reincarnate 10-23-2011 07:24 PM

It's not adding just the largest possible number -- here, it's adding all possible numbers from 2 to (N-1) and checking how it affects the total after removing non-coprimes

 LongGone 10-23-2011 07:37 PM

 stargroup100 10-23-2011 07:40 PM

FFFF YOU ARE RIGHT

im dumb

 Reincarnate 10-23-2011 07:51 PM

.ok apparently my problem is that it risks getting caught in local optima. when it detects a better sum, it may be adding a number (and keeping it) that winds up not being a part of the final solution (or prevents another number from doing the same). Going from 1 to n gives me a diff number from n to 1.

 stargroup100 10-23-2011 07:56 PM

that's what I was trying to say lol

 Reincarnate 10-23-2011 07:59 PM

ah ok misunderstood what you meant

 stargroup100 10-23-2011 08:12 PM

what the hell I went back to look at the problems I already solved in project euler and I cannot for the life of me remember how I did these LOL

all I remember is that I did most of these with pencil/paper

 stargroup100 10-23-2011 08:37 PM

Quote:
 Originally Posted by Reincarnate (Post 3556096) Maybe something like this (building off SG's idea) stuff
not quite

0 <= x < sqrt(n) list: [(1), 2, 3, 5]
sqrt(n) <= x < n/2 list: [7, 11, 13]
n/2 <= x list: [17, 19, 23, 29]

however, but my idea doesn't take into account longgone's new input, the fact that some of the primes from the first group might stand by themselves. however, if you combine your method with mine it should account for both cases pretty well.

 FFR4EVA_00 10-23-2011 09:37 PM

psst

 stargroup100 10-23-2011 10:02 PM

Thanks to lurker and LG I can fix up my method a bit.

 Reincarnate 10-23-2011 10:15 PM

I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant

 cry4eternity 10-23-2011 10:26 PM

I just found this on Friday. Solved 1-22 as well as 67 now :p. This is actually pretty fun.

 stargroup100 10-23-2011 10:43 PM

Quote:
 Originally Posted by Reincarnate (Post 3556158) I'm trying to find something that doesn't require bruteforce (most of the problems I've solved don't require it) -- this problem is bugging the hell out of me because I can't figure out anything more elegant
feelin ya bro

but it's possible this is along the lines of what they want. after all, they ARE programming problems.

 FFR4EVA_00 10-23-2011 11:45 PM

i'm gonna go ahead and drop a gigantic hint for 354 since the upper bound is so insane i have no chance of programming it correctly:

 stargroup100 10-24-2011 12:49 AM

Right now I'm trying to figure out methods to significantly reduce the number of calculations needed to solve this, whether it's skipping possible subsets or finding a totally new method.

However, it's getting late and I'm getting sleepy, difficult to focus. I'll work more on this tomorrow.

 FFR4EVA_00 10-24-2011 07:27 AM

i'm seriously advocating that the quickest method would be starting at the set for Co(100) and drawing each Co(n+1) from Co(n)

 FFR4EVA_00 10-24-2011 11:26 AM

it's predictable though
basically it comes down to an iterative process
i think the hardest part would be how to arrange the arrays for optimal speed
i was thinking that you would basically set it up like this:
[a_2, a_3, a_5, a_7, ..., a_p]
p is the largest prime below n, and the a_i are not necessarily distinct, so that when you actually wanted to find Co(n) you'd remove duplicates and add 1

 FFR4EVA_00 10-24-2011 02:29 PM

 FFR4EVA_00 10-24-2011 02:50 PM

like i said: the set doesn't have to be distinct in this arrangement
i could easily just leave empty spaces but hey, programming doesn't really like those
and 16 only has one factor i have no idea what you're talking about
what's going on with 21 is this: if a < b < c, then ac+b > ab+c
i just threw in the snippet about testing 20 because i figured a program would try it

 LongGone 10-24-2011 04:26 PM

 FFR4EVA_00 10-24-2011 04:58 PM

longgone is correct on 1 and 2
here's what you're confused about if i am right:

Quote:
 [a_2, a_3, a_5, a_7, ..., a_p] p is the largest prime below n, and the a_i are not necessarily distinct, so that when you actually wanted to find Co(n) you'd remove duplicates and add 1
Quote:
 20 gets a bit more complex 20 drags in 16 and 15, but 15 is also a multiple of 3 it quickly becomes apparent that the only thing one could do with the 3 is use 9 20+9 < 16+15, don't insert 20 : [16, 15, 15, 7, 11, 13, 17, 19] 21+5 > 15+7, insert [16, 21, 5, 21, 11, 13, 17, 19] 20 < 16+5, don't attempt

 Knut.Angstrom 10-24-2011 05:18 PM

Quote:
 Originally Posted by Reincarnate (Post 3556057) A step-by-step runthrough of the Co(100) process:
Your sum 1355 is not correct since you use 99 instead of 88 giving 1356

 Knut.Angstrom 10-24-2011 05:24 PM

1+64+81+25+49+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89+97+
(95-25-19)+(91-49-13)+(88-64-11) =1356

 fido123 10-24-2011 05:25 PM

Worked on this for a little bit one night. Did 1, 2, and 6 all in C:

Question 1:

Question 2:

Question 6:

Easy stuff so far but I'm not really all that knowledgeable about math at all so I'm not sure how far I'll get with this lol.

 FFR4EVA_00 10-24-2011 05:28 PM

Quote:
 Originally Posted by Reincarnate (Post 3556421) Okay but what about needing to retrieve something lost? For instance, the solution to Co(100) includes a 17, which gets removed back in Co(51)

Quote:
 Originally Posted by Reincarnate (Post 3556421) Also some numbers will have more than 1 unique prime factor
i heard whispers that this is true but i am trying to rigorously disprove it

 FFR4EVA_00 10-24-2011 05:56 PM

yeah, i never said what those were, i'm sorry
a_p is just the number that is divisible by p in whatever set we're looking at (since we're supposed to be looking at coprime sets there is exactly one a_p for every p but not all a_p are unique)
the reason why i'm duplicating the terms is that i think it will be easier for a computer to traverse

 LongGone 10-24-2011 06:18 PM

Quote:
 Originally Posted by Reincarnate (Post 3556421) Also some numbers will have more than 1 unique prime factors (e.g. 30 -> unique primes 2, 3, and 5)

 Reincarnate 10-24-2011 06:22 PM

Quote:
 Originally Posted by LongGone (Post 3556451)
I think this is a reasonable assumption to make

 FFR4EVA_00 10-24-2011 07:04 PM

@Reincarnate- that is correct, yes
now i'm messing around with a brute-force solution of sorts though, NOTHING like what i was doing before

 FFR4EVA_00 10-24-2011 08:42 PM

 Reincarnate 10-24-2011 09:19 PM

congrats FFR4, nicely done

 stargroup100 10-25-2011 01:44 AM

http://img268.imageshack.us/img268/5532/eulero.jpg

I got 0 eulerian points for this. mad

 iironiic 10-25-2011 09:53 AM

Got #71 with pencil and paper xD

EDIT: Nice FFREva!

 FFR4EVA_00 10-25-2011 10:41 AM

http://projecteuler.net/eulerians
"For the twelve most recent problems the difference, d, in the length of time to solve the problem (in minutes) between each member and the slowest in the table is calculated and log2(max(d,2)) points are awarded."
so every time someone solves the problem, the points of everyone who already solved it go up
in other words cosmovibe has 8 points now

 Reincarnate 10-25-2011 11:58 AM

All times are GMT -5. The time now is 02:28 PM.