how many project Euler problems have you solved?

i have solved 15 of them so far, but they are getting harder.

i just solved #24
it turned out to be pretty simple but i have never written code that looked like this before
so that makes 16 for me

I may have solved one or two indirectly by writing sample code for these boards. However, this thread prompted me to join as well, and I'm going to try to solve the problems using the Haskell language, since I'd like to practice it a bit. But as of now my badge looks pretty unimpressive :P

Stephan van Hulst wrote:I'm going to try to solve the problems using the Haskell language, since I'd like to practice it a bit.

Yeah, that's what started me off - I'm doing them in Scala. Though I'm playing with F# at the moment as well, so might switch to that (or re-implement some of my old ones).

lol Stephan
dont worry, i believe in you

Scala seems pretty popular. i am probably too lazy to learn it though

Curse you Randall!

Here I was having a perfectly happy life and now I'm sucked in. Having solved my first two I'm hooked.

Bert

hee hee dont feel bad Bert, i am hooked also. it is kind of addictive

It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

I too am hooked. I'm working on problem 6. The first 4 presented no difficulties, but I had to mull over problem 5 for some time before the light bulb went on. Curses indeed!

Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

For no good reason, I always though having a pre-built list of primes was cheating. I wrote a few utilities that I do use, but all data is re-computed each time. I have a helper class that you can say "Build the first X prime numbers", and then you can say "get the next prime number"...maybe I should add "get the NEXT x prime numbers".

Like I said, it's my own, weird rule, but I think everyone has to do it their own way.

I have the same feeling. I also spent quite a bit of time on a general purpose prime number generator ("give me all up to N", "give me the first N", "give me the next N") etc.

There's one I completed that I feel a bit guilty about. I had an intuition that the answer probably followed a particular pattern. That gave me a lightning algorithm, and it turned out to be the right answer. But I still can't prove it has to follow that pattern.

It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

i wrote a "helper" class to find primes

it is not the fastest algorithm, but it is fast enough so far(i might improve it)
i also will probably overload the method like this
public boolean isPrime(int number)
public boolean isPrime(BigInteger number)

i noticed that BigInteger has a method isProbablyPrime() but i am not sure how useful it might be

Yeah, that won't cut it when you get onto some of the more computationally expensive questions. Mine uses a Sieve of Eratosthenes (either all in one if I know how high I need to go, or incremental if I don't). For problems where I have to work out if something is a prime number I generate them in advance and shove them in a HashSet for quick lookup.

Matthew, getting the correct answer is what matters most . i know what you mean though. i just finished solving #30
i had to set a limit for a loop and i used what seemed right even though i wasn't positive. it worked

Some colleagues and I did a lunchtime language club, and part of it was solving Euler problems in Ruby and Python. We'd do a few during the week, then get together and compare our solutions. Then the problems got harder and we got busier, and it all just petered out. I really would like to get to at least 100 someday.

I've mainly used Scala and some Haskell.

None.

Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

Haha, actually I made a utility class called Primes which determines if an integer is a prime number, does prime factorization, and some other stuff, because I have the feeling I'm going to need them a lot

I also made some Scala and Haskell prime number utilities, you can see them in this GitHub Gist.

(edit: oh, I see I didn't post the Haskell version there, those are only in Scala. But my Haskell version was very much like the second Scala version).

Stephan van Hulst wrote:

Bert Bates wrote:It seems to me that if I'm going to keep doing this I'm going to need some utility stuff, e.g. it strikes me that a big old ArrayList filled with prime numbers is going to come in handy :smile:

Haha, actually I made a utility class called Primes which determines if an integer is a prime number, does prime factorization, and some other stuff, because I have the feeling I'm going to need them a lot

I have an EulerUtils class with a dozen methods in. I like the idea of a utility class named Primes, except I also have a bunch of methods that work with series and collections.

I think I too might start learning Scala. Using Project Euler to learn a new language seems like a great idea. Do you feel it's been effective?

Yeah, I'd probably make a couple of other utility classes as well (or rather, Haskell files containing mathematical functions) when I need some more. I might make it all into a single file if I end up with just a small amount.

I think anything is effective to learn a new language. Most of the time, you just need to work on something, anything at all, to get a kickstart. Project Euler provides an entertaining way to do so.

I usually test my proficiency in a language by taking a game like Chess and writing a text based implementation for the command line, then I add a GUI, and LAN capabilities. If I can do those things in a readable, self-documenting way, I feel I understand most of the language.

Matthew Brown wrote:Yeah, that won't cut it when you get onto some of the more computationally expensive questions. Mine uses a Sieve of Eratosthenes (either all in one if I know how high I need to go, or incremental if I don't). For problems where I have to work out if something is a prime number I generate them in advance and shove them in a HashSet for quick lookup.

I have a nice sieve implementation for when I know how high to go. I can't quite crack the problem of an incremental sieve, though. In the first case, if k is the prime number whose multiples I am filtering out, I know I can stop sifting when k has a certain property in relation to the upper limit. If, instead, I need n prime numbers, I can't figure out how to know when my sifting is done.

IIRC, to find the next prime, I start at (largestPrimeFound + 2), and start testing it with all my known primes up to the sqrt of the number. In other words, if the largest i've found is 19, i'd test 21 to see if it is divisible by 2, then 3, at which point i'd quit since 21%3 == 0.
then i'd test 23 to see if it is divisible by 2, then 3, then quit since 5*5 > 23. since 23 has no divisors, it must be prime.

it now becomes my largestPrimeFound, and I can generate the next by starting at 25 (which fails after 3 tests).

I've never figured out my big-O notation on it, but I think it would be somehow related to whatever the distribution of primes is...[edit - according to my brief research, this would be log-n]

I think I also have methods that say "find the first X primes" and "find the first prime larger than X"

You guys must have overloaded the site. I can't get to it now.

fred rosenberger wrote:If the largest i've found is 19, i'd test 21 to see if it is divisible by 2, then 3, at which point i'd quit since 21%3 == 0.
then i'd test 23 to see if it is divisible by 2, then 3, then quit since 5*5 > 23. since 23 has no divisors, it must be prime.

Seems like we should be able to dispense with the divisible by 2 test since we already know we're getting an odd number.

My incremental sieve works by looking at the next chunk of 100 numbers, and using the usual sieve technique using the prime numbers I've already generated.

As an example, let's say I was looking for the 60th prime number. I'd do a sieve on 1-100. That gives me 25 prime numbers, so I know I need to keep going. So I look at 101-200 - but I just need to eliminate multiples of primes I've already found up to sqrt(200). I've now got 46 primes, so I look at the next 100. And so on, until I've got enough. So I'll (probably) generate more than I need, but not by much.

I've been stuck on #15 for a while. Mostly with Java, but I've been going over the same ones with Python as I learn that. I'm finding Python to be really friendly.

Matthew Brown wrote:My incremental sieve works by looking at the next chunk of 100 numbers, and using the usual sieve technique using the prime numbers I've already generated.

As an example, let's say I was looking for the 60th prime number. I'd do a sieve on 1-100. That gives me 25 prime numbers, so I know I need to keep going. So I look at 101-200 - but I just need to eliminate multiples of primes I've already found up to sqrt(200). I've now got 46 primes, so I look at the next 100. And so on, until I've got enough. So I'll (probably) generate more than I need, but not by much.

I'd suppose that it is possible to obtain some approximation of how many numbers you need to test to get first N primes (and indeed there is), so you could start with that and only do incremental search if the approximation was too low.

(I'd have to look the formula up. I'm not sure that would count as cheating - for me it is enough that I was able to figure out something like that should exist. It is actually much simpler than I expected (as many other math tricks), but still I don't think I'd be able to work that out on my own in the time I'd be willing to put into it.)

i have solved 18 of them now with 19 and 20 on the way.
don't feel bad Tim i haven't solved #15 yet either

15 isn't too hard, once you know the secret. it is relatively simple calculation. I can give a hint, if you want...

i must admit, i just skipped over #15
i am sure you are right it is not that hard
#31 is the one giving me a hard time right now

fred rosenberger wrote:15 isn't too hard, once you know the secret. it is relatively simple calculation. I can give a hint, if you want...

thanks, but I (think) I got the secret and have yet to apply it. I will let you know.

I have done all of them in order, but I have not worked on them for a while.

Since there has been some talk of prime numbers, I figured it'd be fun to make a fluent interface version of my Primes utility in Java. Try this line:
Overview Source

Stephan van Hulst wrote:Since there has been some talk of prime numbers, I figured it'd be fun to make a fluent interface version of my Primes utility in Java.

static Iterable<Integer> greaterThan(int value)
Returns all prime numbers greater than or equal to a specified value.

How is this possible?

Dennis Deems wrote:

static Iterable<Integer> greaterThan(int value)
Returns all prime numbers greater than or equal to a specified value.

How is this possible?

It doesn't actually return an infinite number of primes. It returns an iterator that will generate as many primes as it is asked to. So stick it in a for loop and it will run forever (or until you run out of memory). It's a sort of lazy generation.