----------------------------------- A.J Sun May 31, 2009 12:52 am Project Euler... ----------------------------------- I have 2 HUGE summatives due in 2 days...what a time to get hooked on project euler... I wanted to inquire about the latest question on there : http://projecteuler.net/index.php?section=problems&id=247 I have only got 154 problems solved, but I am trying to increase my 'performance' (i.e. the # of questions solved in the last 25 problems, Currently, it is 15/25). This particular question is very interesting. I have a couple of ideas on how to start, but not anything elegant yet. Anyone have any thoughts about this problem? ----------------------------------- DtY Sun May 31, 2009 2:55 am RE:Project Euler... ----------------------------------- That looks fun! I'm on question two now :) ----------------------------------- A.J Sun May 31, 2009 10:42 am RE:Project Euler... ----------------------------------- @DtY - nice! but a small warning, these questions are addicting :P k, I might have a bruteforce solution for #247, but it reall won't finish marks the answer, then after that all the prime numbers it found. [edit] Oops, I guess it didn't like my extensionless filename ----------------------------------- A.J Sun May 31, 2009 4:07 pm RE:Project Euler... ----------------------------------- @DtY - The hardest part of this question is actually generating the primes below 2000000 and to store their sum (well, that's pretty much the whole question :lol:). For generating the primes, try looking at prime sieving (sieving primes from all the numbers from 1->2000000). There a lot of efficient sieves that can with run at astounding speeds. Now, long long should suffice in storing the sum. As for why your program works for 10 and not 2000000, well maybe it omits some of the bigger primes? How are you generating the primes and how are you storing their sum? ----------------------------------- DtY Sun May 31, 2009 4:13 pm RE:Project Euler... ----------------------------------- I'm doing it in Ruby, so size doesn't matter I'm using the primes.sum Sum is just a simple method I wrote: class Array def sum s = 0 self.each {|x| s += x } return s end end the only thing I can think of that might be the problem is this line, is this the right number of times to iterate? 0.upto sieve.length.sqrt.ceil do |z| (int.sqrt is another method I wrote as an alias to Math.sqrt(int)) ----------------------------------- A.J Sun May 31, 2009 4:23 pm RE:Project Euler... ----------------------------------- Eratosthenes should be fast enough. For sieving, it suffices to go up till the floor(sqrt(number)). However, for the 'cancelling out the multiples of smaller primes', you have to iterate up to the number. In other words: [code] For (i : 2 -> floor(sqrt(number)), increment by 1 ) if i is Prime then For (j : i^2 -> number, increment by i) j is not a Prime (i.e. set Prime[j] = false) [/code] ----------------------------------- DtY Sun May 31, 2009 5:05 pm RE:Project Euler... ----------------------------------- The part that actually decides which ones are good is: sieve = sieve.select {|x| x%primes Where primes[-1] is the next prime number to remove multiples of ----------------------------------- chili5 Sun May 31, 2009 7:41 pm RE:Project Euler... ----------------------------------- I've started to get really hooked to this as well, bad time to get hooked on this, with summatives due in a week. :-s Seeing other people's solutions in the forum is really interesting. :) The primes ones are really easy, and Eratosthenes is usually always fast enough. A lot of the first few questions seem to involve using the BigDecimal class in Java. ----------------------------------- Cyril Sun May 31, 2009 7:42 pm RE:Project Euler... ----------------------------------- I find that it's convenient to write a quick program to write a bunch of primes to a file. When you come across a problem that requires primes (too often?), you can just read from the file, which is much faster than generating them every time. ----------------------------------- A.J Sun May 31, 2009 10:18 pm RE:Project Euler... ----------------------------------- @DtY - I am not familiar with Ruby, so I can't help you there. @chili5 - welcome to the world of questions-that-drive-you-mad :D @Cyril - well, generating the primes only takes a couple of seconds, so it isn't that bad. And besides, the new questions nowadays almost never have primes in them :D ----------------------------------- chili5 Mon Jun 01, 2009 5:23 am RE:Project Euler... ----------------------------------- I wonder why there isn't any more prime questions, primes are fun. I supposed all the good questions have been done already though. A.J, how many problems have you got done? Woot, I got question 5. My code (very inefficient) ran in 29 seconds. :) [CODE] int nCount = 0; int nNum = 1; while (nCount != 20) { for (int i=1;i_>) went to the world championships this year, with somewhat good results. Regarding your question on #242, though i haven't done it yet (too busy), i believe some simple recursion should do the trick. I am still working on #245 (Coresilience), and find it somewhat difficult because i am following a very stingy brute force, using sieve to calculate values of phi(n), and so far ... it is very slow and inefficient, and takes approximately 2 min just to calculate up to 10^8, any suggestion would be helpful, and hope i can help too if anyone has any questions, though Cyril is really the expert, and has helped me through some problems, and vice versa ;) If you have read through this whole introduction ... give yourself a pat on the back :D Now back to boredom >_> ----------------------------------- saltpro15 Mon Jun 01, 2009 4:46 pm RE:Project Euler... ----------------------------------- Shah-Cuber, I'm addicted to SPOJ as well:D my user ID there is dr3w. Our school is actually forming a robotics team next year, what contests do you do?/what is it all about? ----------------------------------- Shah-Cuber Mon Jun 01, 2009 5:03 pm Re: Project Euler... ----------------------------------- saltpro15, Our school had two robotics divisions: VEX robotics & FTC robotics I was mainly in the FTC robotics (programmer/builder) along with 4 other people, 3 grade 12's and 1 grade 11, even though we started out with like 20 or so >_> (people eventually quit) For regionals we placed 2nd overall and won alliance round, and moved on to the world championships in Atlanta, where we placed 20th among 150 or so competitors world - wide. For more information about the game and the organization itself, you can visit http://www.firstroboticscanada.org/site/node/928 . Hopefully we will meet you next year if your doing FTC or VEX, though we had numerous difficulties, it proved to be a very fun and educational experience ... though I have grown a hatred towards RobotC >_> Good Luck ! ----------------------------------- A.J Mon Jun 01, 2009 5:49 pm RE:Project Euler... ----------------------------------- @ Shah-Cuber - Here's you official welcome to compsci.ca: Welcome to compsci.ca :D! Its nice to know that you are participating in project euler and SPOJ too, as they really help you in gaining more knowledge in math and CS alike. And I was talking about #247 (the last question), not #242. And as for #245, try doing #243 first, as it is a slightly easier version of #245. ----------------------------------- Shah-Cuber Mon Jun 01, 2009 8:02 pm Re: Project Euler... ----------------------------------- Thanks A.J :) Sorry, I must've misread >_> @ A.J - I have also noticed that you are now 12th in Canada ! wow O__O, congratulations ! I must've been gone Project Euler for a long time >_>, well, hopefully within the next week or so (after my work is done) i will start doing some more questions :D ----------------------------------- A.J Mon Jun 01, 2009 9:35 pm RE:Project Euler... ----------------------------------- thanks, I have been working my ass of on them for the last month or two (pardon my language). ----------------------------------- A.J Wed Jun 03, 2009 8:16 pm RE:Project Euler... ----------------------------------- Ok, I solved the question. I used priority queues, as I found that the enumerating the squares got a lot faster. The runtime was about 3.976 seconds, which isn't that bad, but certainly could be faster. Ok, right now I have 199 solved. I must try catching to people like Shah-Cuber and Cyril by the end of summer. I am going to the Canada/USA MathCamp, so I'll try coding there. I am going to train a lot this summer on SPOJ, Project Euler, random Olympiads, etc...as I want to try making it to IOI next year. Some of my friends who are reading this post might actually be surprised, since being emo I never want to achieve anything in my life, but this is the reason why: the probability that IOI will EVER take place in the city that you live in out of ALL THE OTHER places in this WORLD while you are in grade 12 (i.e. in you programming peak) is actually very VERY VERY slim. So, I am preparing. ----------------------------------- Shah-Cuber Wed Jun 03, 2009 8:53 pm Re: Project Euler... ----------------------------------- Congratulations :) 1 more till level 5!!! .. than you will see your progress slow down >_> ----------------------------------- A.J Wed Jun 03, 2009 11:41 pm RE:Project Euler... ----------------------------------- Yeah, I know...but I didn't finish some of the extremely trivial ones, so I might finish them and then maybe get stuck for a long while :P ----------------------------------- A.J Fri Jun 05, 2009 7:47 pm RE:Project Euler... ----------------------------------- # 248 is out! Ok, this seems easy, but...the numbers get annoying. I am trying to be the top ten to finish it ----------------------------------- Cyril Sat Jun 06, 2009 12:30 am RE:Project Euler... ----------------------------------- Wow, A.J. ...your progress is astounding. I don't think 248 is as easy as it seems. It seems like the approach is something like the one for 221- reduce it to a factoring problem in a specific way such that you generate the numbers in order. ----------------------------------- A.J Sat Jun 06, 2009 10:35 am RE:Project Euler... ----------------------------------- Thanks Cyril. I realised that I didn't finish a lot of the easier problems, so I managed to finish them. Now, however, I won't be going anywhere...except for maybe trying to solve #248 :lol: PS: damn it, while I was sleeping, there already has been 26 people to have solved #248....oh well, so much for top ten :( ----------------------------------- A.J Sat Jun 06, 2009 2:24 pm RE:Project Euler... ----------------------------------- ok, since I haven't been paying attention to school that much, because I was doing project euler practically 24/7, my mom sort of banned me from doing project euler for a while...I can spend time on it, but only for a small limited amount of time.... EDIT: Yes. I managed to finish #210 (Obtuse Angled Triangles) when my mom wasn't home :P. Tied for 5th. ----------------------------------- saltpro15 Sat Jun 06, 2009 8:08 pm RE:Project Euler... ----------------------------------- I think A.J. may have an addictive personality :p stay away from rubik's cubes! and fallout 3, really addictive... anyways, enough off topic! time to start some project euler ----------------------------------- A.J Sat Jun 06, 2009 8:27 pm RE:Project Euler... ----------------------------------- what do you mean by addictive personality? cause I am certainly not addictive... ----------------------------------- Shah-Cuber Sat Jun 06, 2009 8:37 pm Re: Project Euler... ----------------------------------- Finishing my homework, I got bored, and noticing i'm falling behind in my Eulering, decided to do #228 (Minkowski Sums), very simple O(n) algorithm, and soon i will get catch up to you guys again (I hope). Now i'm gonna look at #222(Sphere Packing) ... hope to finish it before midnight if i can. A.J, your progress is truly astounding. Good Luck to you too saltpro15 :) I am proud that i have gotten one after such a long time >_> ----------------------------------- A.J Sat Jun 06, 2009 11:06 pm RE:Project Euler... ----------------------------------- Nice Shah-Cuber! ----------------------------------- Shah-Cuber Sat Jun 06, 2009 11:10 pm Re: Project Euler... ----------------------------------- Thanks Just got #222 with brute force, i know, i didn't see the pattern, but it was a horrible run time. One of my worst last minute-programming before midnight ever ... ----------------------------------- A.J Sat Jun 06, 2009 11:18 pm RE:Project Euler... ----------------------------------- I just finished #201. I found a very elegant solution to it (well, it isn't elegant, just that it is cool :D) Congrats Shah-Cuber :D. I used Haskell to do #222. My program ran in 3 questions... And Brian, I noticed that you too are writing the Waterloo Local ACM contest. Nice! ----------------------------------- T.O Tue Jun 09, 2009 12:14 pm RE:Project Euler... ----------------------------------- what is this ----------------------------------- A.J Tue Jun 09, 2009 1:19 pm RE:Project Euler... ----------------------------------- "Waterloo's ACM International Collegiate Programming Contest Team will be chosen according to the results of these contests. All UW students are welcome - come to learn, come for fun, or come to win. Detailed announcement " ----------------------------------- bbi5291 Tue Jun 09, 2009 4:28 pm Re: RE:Project Euler... ----------------------------------- Aww. The DMCI people who went to the second round with you seemed to be astounded by your skills- I thought you'd "have a seat reserved". I can see how chemistry really depends on conditions... Yes, MIT was a dream for me as well, but I think it has more or less crushed itself. Oh well. Apparently they doesn't look at your SAT essay...? And, nice- 219 is totally doable with pencil/paper, but I only realized how small the problem was after I started coding. Wow, I generally assume that nobody ever talks about me because I'm overshadowed by Schneider. :P What I have heard is that MIT doesn't look at the writing part at all, which includes the essay. So effectively your score is out of 1600. Why is everyone so obsessed with entrance to MIT ? I mean, don't get me wrong, it is one of the top universities, but, realistically, i don't find it beneficial, unless everyone here is gonna major in some CS program. Well, extrapolating from others' experiences, I should have no problem getting into UW. It is definitely an excellent university and the computer science program is one of the best in the world, rivalling or surpassing that of MIT. And I don't like the USA in general, either, especially the idea of living there (I'd like to think that Obama can change something, but absolute power corrupts absolutely). However, MIT is a challenge, whereas relative to my standpoint UW is not. Also, as Analysis Mode hinted, the social climate is very different at elite American schools than it is at the most elite of Canadian schools. But even if I was somehow prevented from attending MIT, I would still like very much to be admitted. Because I see a lot of smart people doing amazing things before, during, and after their studies at MIT (Schneider is an example at least for the "before" part, and one of the mentors at the CCPO made IChO in grade 9, finished undergrad in 2 years, and is at MIT for grad school now), and I would like nothing else but to be their equal. And if I am truly their equal, MIT should accept me as well. ("MIT" may be replaced by "Stanford", "Caltech", "Princeton", whatever.) ----------------------------------- Shah-Cuber Tue Jun 09, 2009 5:23 pm Re: Project Euler... ----------------------------------- (I'd like to think that Obama can change something, but absolute power corrupts absolutely) Agreed ... ----------------------------------- A.J Tue Jun 09, 2009 5:39 pm RE:Project Euler... ----------------------------------- I am sorry to announce that I am officially stopping Project Euler (for about 1 month). I have to start studying for my exams (I mean REALLY start). So, I tried to go out with a bang...and failed :vi:. I solved 5 questions today (which is nothing compared to Shah-Cuber's 10-questions-in-a-day record :shock:), but it does leave Cyril and Shah-Cuber a high target to reach : 236. The questions I finished today were actually pretty trivial: #194 - some math, but then just computation #203 - .......bash #215 - cool, and a bit challenging, DP #217 - easy DP #228 - one insight needed...then becomes trivial So, it is with a heavy heart that I bid my dear friend Euler farewell... (P.S: oh who am I kidding....there are 3 questions that I will try squeezing in during exams, namely #143, #200 and #227 :P) ----------------------------------- saltpro15 Tue Jun 09, 2009 7:56 pm RE:Project Euler... ----------------------------------- A.J. how do you have time to do all those? I have only solved #5 so far, as I have no free time to work on them, though I'd like to... :( ----------------------------------- Shah-Cuber Tue Jun 09, 2009 8:08 pm Re: Project Euler... ----------------------------------- I'm not sure how to put this ... ummm ... YOU GOT #198(Ambiguous Numbers) ?!?!?!?!?!? How ?!? Inconceivable ?!?! Impossible ?!? than again ... you are you ... haha I still believe your performance on project Euler is truly astounding, and now you are beating me by 10 questions! Considering the fact that only 2 days ago, we were tied >_> But i figured, you will never quit Eulering, simply because it is very addictive ... no one can escape .... it is inevitable ... Good luck on the exams :) I'm studying too ... Hint for #227: I just created transition matrix, and solved a system of linear equation :) Good luck! hmmm ... maybe this is my chance on revenge ? #219 here i come (as Cyril recommended) :) ----------------------------------- A.J Tue Jun 09, 2009 8:08 pm RE:Project Euler... ----------------------------------- I don't have time to do all those...that's the point I am trying to make (shoots self in the head)....damn, there really needs to be an 'emo'ticon here :lol: #198 isn't that hard, Shah-Cuber. Here's a hint: When you write down the list of all rational numbers with denominator _> ----------------------------------- A.J Tue Jun 09, 2009 8:42 pm RE:Project Euler... ----------------------------------- #219 is one of those problems that doesn't require a program. But it can also be done using a program. I used the recurrence to find the first 10 numbers in the sequence, then I tried noticing a pattern, and then extrapolate the required term from the sequence continuing this pattern. I think the DP 'step' you had is probably the same as the recurrence I found. ----------------------------------- Analysis Mode Tue Jun 09, 2009 10:18 pm Re: Project Euler... ----------------------------------- @A.J.: I don't do Project Euler. I need to get in top 10 in Canada on SPOJ and then I'll consider it. Then again, I have to study for the Canadian Biology Olympiad, practice for CCC, study for Reach, etc. over the break. SPOJ is more practical practice for CCC. Lots of good problems. @Cyril: No, I'm not aiming for MIT. I'll be going into pre-med at whatever university I attend, and MIT pre-med just doesn't appeal to me as much as other universities. And not to mention having to take Physical Education as a mandatory course. Oh, and there aren't any hot girls at MIT either, so that's another no-no (just kidding, if any of you happens to be a hot girl from MIT) To all: I would suggest you read this: http://www.theamericanscholar.org/the-disadvantages-of-an-elite-education/; It's a lengthy article by a former Yale professor about the learning environment and mentality American schools provide with their students. ----------------------------------- A.J Tue Jun 09, 2009 10:27 pm RE:Project Euler... ----------------------------------- yeah, I should really start SPOJ.....and I also have to practice for CCC (somehow) and Reach (somehow)... ----------------------------------- Shah-Cuber Sun Jun 14, 2009 1:29 pm Re: Project Euler... ----------------------------------- The post is starting to become outdated ... so i'll say some things that have been going on, on Project Euler, the past few days. First of all, congratulations to A.J for now becoming #1 in Canada in such a fast time, in such short days, while having exams and projects due. This is very impressive, and kinda scary (He is above Schneider), but i suspect his too busy at the moment to do anything. Also surprisingly, all of us (Cyril, A.J, and I), did Chess AI's for our final ISU projects ... I handed mine in friday. I used alphabeta pruning/minmax, and i believe A.J did the same, but Cyril implemented heuristics. Also, A.J's is 3D while mine and Cyril's are not, (i had basically two days to do it, so not enough time), and all of the languages used between us is different. I used Java, Cyril used VB, and A.J used C++, so i just said that, cause i thought it was interesting and awkward that all of us did Chess AI. Besides that, question #249 and #250 have been added ... possible DP, i'll work on them in the week to come ... maybe not, because i have exams coming up. Currently i'm working on #214 (Totient Chains), hopefully i'll get it by the end of today. What else ... hmm, i think thats it, anyways good luck to all! Happy Eulering :) ----------------------------------- A.J Sun Jun 14, 2009 2:02 pm RE:Project Euler... ----------------------------------- Thanks Cyril And btw, the 3D chess our group handed in this year, sadly, didn't include AI (I didn't have time). However, the chess game I made last year did include AI =). I am going to continue the AI at summer and I am going to add it to our current 3D chess program. ----------------------------------- Cyril Tue Jun 16, 2009 3:56 am RE:Project Euler... ----------------------------------- Gaaaaaaah. It's 4:55 am. I hear birds. I see dawn. After 2 hours of frantic debugging, I am now the 106th solver of #248. To my dismay, there were much nicer methods posted on the forum. Must... stop... ----------------------------------- bbi5291 Tue Jun 16, 2009 8:00 am Re: Project Euler... ----------------------------------- To all: I would suggest you read this: I should point out that my understanding of this article is that those students adversely affected by an elite education are usually the hoop-jumper type. I think less than 5% of all students accepted to elite American schools really fit my definition of "intellectual", and those schools are probably not the best environments for them. But for those who really are intellectuals, schools like MIT provide an encouraging social environment that is somewhat lacking from many Canadian schools, and have state-of-the-art facilities for research and that sort of thing... ----------------------------------- Shah-Cuber Tue Jun 16, 2009 12:06 pm Re: Project Euler... ----------------------------------- Easiest programming exam ever :D Now only two more left ... ----------------------------------- Shah-Cuber Tue Jun 16, 2009 12:12 pm Re: Project Euler... ----------------------------------- Whoa ... just checked Project Euler statistics ... Not only is A.J #1 now (congratulations), but Cyril is catching up fast ... uhoh, well i'll start doing some questions right now, since i just came out of my exam, i'm crammed with knowledge (noob knowledge that is). Must savor the everlasting pleasure of being 1 rank away from Schneider, before Cyril takes it away >_> ----------------------------------- Shah-Cuber Tue Jun 16, 2009 1:14 pm Re: Project Euler... ----------------------------------- Yay, got #214 (Totient Chains), sieved phi values up to 40000000, then recursively calculated the size of the chains :D Not bad, Now i'm attempting #245 (Coresilience) again ... though it fails after 1 < n ----------------------------------- saltpro15 Sun Jun 21, 2009 4:36 pm RE:Project Euler... ----------------------------------- Shocked indeed. That's ridiculous edit : I'm a little bamboozled, why is my solution for the very simple Euler #9 failing? #include using namespace std; int main() { ofstream fout ("euler9.txt"); int a = 0; int b = 0; int c = 0; for (int i = 0; i < 1000; i++) { a+= 1; b+= 1; c+= 1; if ((a * a) + (b * b) == (c * c) && a + b + c == 1000) { fout