Project Euler...

[A.J]

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]

That looks fun! I'm on question two now

[A.J]

@DtY - nice! but a small warning, these questions are addicting

k, I might have a bruteforce solution for #247, but it reall won't finish <1min...hmm, maybe I should integrate ...

[Cyril]

Ah, got it in an hour. Runs in about 1 second. Nice problem! Hopefully this doesn't give anything away:


1.

Spoiler:

Recursion is the basic approach.

2.

Spoiler:

No integration is needed to find the square. Solve y-dy = 1/(x-dx) for y=x.

[DtY]

Hmm.. I'm having trouble with question ten.. If I run it with ten, it gets seventeen as the question says it should, but using 2'000'000, the answer it gives me is wrong

Without posting my source, can someone give me vague hints as to why it might not be working? I'll attach the output
The beginning is unimportant, it's just to let me know how much is left then => 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]

@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 ). 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]

I'm doing it in Ruby, so size doesn't matter

I'm using the Sieve of Eratosthenes (the first one described) to store them in an array, then to get the sum primes.sum Sum is just a simple method I wrote:

Ruby:

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?

Ruby:

0.upto sieve.length.sqrt.ceil do |z|

(int.sqrt is another method I wrote as an alias to Math.sqrt(int))

[A.J]

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)

[DtY]

The part that actually decides which ones are good is:

Ruby:

sieve = sieve.select {|x| x%primes[-1] != 0 }

Where primes[-1] is the next prime number to remove multiples of

[chili5]

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]

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]

@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

@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

[chili5]

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<=20;i++) {                 if (nNum % i == 0) {                     nCount++;                 } else {                     break;                 }             }             if (nCount == 20) {                 System.out.println(nNum);             } else {                 nCount = 0;                 nNum++;             }         }

[A.J]

I currently have 188 solved, out of which 16 are out of the last 25.

[Shah-Cuber]

Hello CompSci

I have currently registered as a new member, and I am static about your discussion so far regarding Project Euler.
I am a grade 10 student - Python program (mainly), though I also program in C++, Java, and Mathematica.
Though I have registered just now, I have visited this site for a quite a long time, and know/heard many of you.
Today is also a good day, because i also received my SIN (Sir Isaac Newton Physics Contest) results, which has also made me very hyper in addition to my insomnia (joking) over the past several days -_-
I too enjoy doing Project Euler questions, and my username is the same there as it is here. I have learned a lot through doing such questions, and find it very beneficial if one enjoys a challenge and deep mathematical concepts. I have also recently started doing some fun SPOJ questions, and find it as addicting as Project Euler. I also recommend that if your bored as i am (usually). However, currently, i have been bombarded with loads of homework, and find little time to program anymore. Robotics is also one of my interests, and our school team (more like 5 people, who never sleep >_>) 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
Now back to boredom >_>