wood burning stoves*
The moose likes Meaningless Drivel and the fly likes how many project Euler problems have you solved? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "how many project Euler problems have you solved?" Watch "how many project Euler problems have you solved?" New topic
Author

how many project Euler problems have you solved?

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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


SCJP
Visit my download page
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11170
    
  16



There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

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

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

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).
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

lol Stephan
dont worry, i believe in you
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

Scala seems pretty popular. i am probably too lazy to learn it though
Bert Bates
author
Sheriff

Joined: Oct 14, 2002
Posts: 8805
    
    5
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


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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

Joined: Oct 14, 2002
Posts: 8805
    
    5
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:
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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!
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11170
    
  16

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.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

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.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

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.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2841
    
  11



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.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14074
    
  16

I've mainly used Scala and some Haskell.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Jelle Klap
Bartender

Joined: Mar 10, 2008
Posts: 1756
    
    7

None.


Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

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
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14074
    
  16

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).
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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?
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3605
    
  14

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.
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11170
    
  16

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"
Tim McGuire
Ranch Hand

Joined: Apr 30, 2003
Posts: 820

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

Joined: Mar 12, 2011
Posts: 808
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.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

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.
Tim McGuire
Ranch Hand

Joined: Apr 30, 2003
Posts: 820



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.
Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3606
    
  60

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.)
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4340
    
    2

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
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11170
    
  16

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

Joined: Oct 21, 2000
Posts: 4340
    
    2

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
Tim McGuire
Ranch Hand

Joined: Apr 30, 2003
Posts: 820

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.
Dave Trower
Ranch Hand

Joined: Feb 12, 2003
Posts: 86

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

Joined: Sep 20, 2010
Posts: 3605
    
  14

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
dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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?
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

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.
 
permaculture playing cards
 
subject: how many project Euler problems have you solved?
 
Similar Threads
sendind SOAP request
DUMP SIGNAL EXCEPTION 11
How to display error message
Populating a list Html
Problem: SQL Exception