Project Euler
Moderators: phlip, Moderators General, Prelates
Project Euler
Has anyone here done much with Project Euler? There's some really neat stuff you can waste your time with on there, and after you complete a problem you open up a forum topic on that problem and can see other implementations, hopefully learning more about your language or another language and about more efficient algorithms than yours.
By the way, 18% genius! >.> I secretly hope someone here isn't 100% genius... But I wouldn't doubt it.
By the way, 18% genius! >.> I secretly hope someone here isn't 100% genius... But I wouldn't doubt it.
 Torn Apart By Dingos
 Posts: 817
 Joined: Thu Aug 03, 2006 2:27 am UTC
 musicinmybrain
 Posts: 96
 Joined: Sun Dec 31, 2006 2:50 am UTC
 Location: Greensboro, NC
Yeah, Project Euler is a lot of fun. I'm at 49% in Python. I still sit down and do a problem now and then; it's kind of relaxing, and a nice brain exercise.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < <  ] > + >  > + > > + [ < ] <  ] > > . > >    . + + + + + + + . . + + + . > . < <  . > . + + + .       .         . > + . > + + .
Well, since I'm away from my own computer and am without any programming tools besides Notepad, I figured I couldn't start these challenges until I got home. Or couldn't I?
I wrote all of my Python code in Notepad, then uploaded it onto the Anarchy Golf server, which always shows the output of your program whether it solves the challenges or not, and has an amazing number of programming languages supported, making it an ad hoc interpreter.
That was probably one of the cooler things I've ever done on the Internet.
I wrote all of my Python code in Notepad, then uploaded it onto the Anarchy Golf server, which always shows the output of your program whether it solves the challenges or not, and has an amazing number of programming languages supported, making it an ad hoc interpreter.
That was probably one of the cooler things I've ever done on the Internet.
 adlaiff6
 Posts: 274
 Joined: Fri Nov 10, 2006 6:08 am UTC
 Location: Wouldn't you rather know how fast I'm going?
 Contact:
I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.
So I'm only 1% genius.
So I'm only 1% genius.
3.14159265... wrote:What about quantization? we DO live in a integer world?
crp wrote:oh, i thought you meant the entire funtion was f(n) = (1)^n
i's like girls u crazy
 musicinmybrain
 Posts: 96
 Joined: Sun Dec 31, 2006 2:50 am UTC
 Location: Greensboro, NC
adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.
So I'm only 1% genius.
I assume they would be much easier for a mathematician (maybe even trivial, if you're welleducated and clever enough mathematically, particularly in number theory) and somewhat easier for a very experienced programmer.
However, you do realize the beginning ones are simple brute force problems and you have to use more math and come up with better algorithms as you go on?
If they're all really a waste of your time, bully for you.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < <  ] > + >  > + > > + [ < ] <  ] > > . > >    . + + + + + + + . . + + + . > . < <  . > . + + + .       .         . > + . > + + .
adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.
So I'm only 1% genius.
The first ones are cake. They aren't all easy.
SargeZT wrote:Oh dear no, I love penguins. They're my favorite animal ever besides cows.
The reason I would kill penguins would be, no one ever, ever fucking kills penguins.
 musicinmybrain
 Posts: 96
 Joined: Sun Dec 31, 2006 2:50 am UTC
 Location: Greensboro, NC
So I just hit 50%. Does that make me a halfwit? I've got half a mind to make more awful puns, but I'll refrain.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < <  ] > + >  > + > > + [ < ] <  ] > > . > >    . + + + + + + + . . + + + . > . < <  . > . + + + .       .         . > + . > + + .
 adlaiff6
 Posts: 274
 Joined: Fri Nov 10, 2006 6:08 am UTC
 Location: Wouldn't you rather know how fast I'm going?
 Contact:
musicinmybrain wrote:adlaiff6 wrote:I sat down and did two problems in C last night, then I realized they were all too easy and it was a waste of my time.
So I'm only 1% genius.
I assume they would be much easier for a mathematician (maybe even trivial, if you're welleducated and clever enough mathematically, particularly in number theory) and somewhat easier for a very experienced programmer.
However, you do realize the beginning ones are simple brute force problems and you have to use more math and come up with better algorithms as you go on?
If they're all really a waste of your time, bully for you.
Well, I like to advertise myself as a combination mathematician and theoretical computer scientist, so you're on the right track.
I did look at the last ones, and they all either seem to be either a mathematical trick, or a reasonably simple programming paradigm, like backtracking or dynamic programming.
I dunno. I think it was more a "this is a waste of my time; I have other things I should be programming if I'm going to be programming with the time I have" problem than a "man these problems suck" problem. Don't get me wrong, there were some cool problems, I just don't really see the point. Maybe I'll get more bored over the summer. Probably not though.
3.14159265... wrote:What about quantization? we DO live in a integer world?
crp wrote:oh, i thought you meant the entire funtion was f(n) = (1)^n
i's like girls u crazy
 FiddleMath
 Posts: 245
 Joined: Wed Oct 11, 2006 7:46 am UTC
 Location: Madison, WI
 Contact:
adlaiff6 wrote:I dunno. I think it was more a "this is a waste of my time; I have other things I should be programming if I'm going to be programming with the time I have" problem than a "man these problems suck" problem. Don't get me wrong, there were some cool problems, I just don't really see the point. Maybe I'll get more bored over the summer. Probably not though.
Which is actually why I stopped playing on TopCoder, after a while. Once I learned the languages I was using, well enough to be slightly competitive, I wanted to actually make stuff.

 Posts: 52
 Joined: Sat Mar 10, 2007 4:42 am UTC
I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.
Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?
Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?
 musicinmybrain
 Posts: 96
 Joined: Sun Dec 31, 2006 2:50 am UTC
 Location: Greensboro, NC
themuffinking wrote:I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.
Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?
Your length is right, so maybe you're throwing away some possibilities.
Project Euler wrote:Once the chain starts the terms are allowed to go above one million.
Is that what you're missing, perhaps?
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < <  ] > + >  > + > > + [ < ] <  ] > > . > >    . + + + + + + + . . + + + . > . < <  . > . + + + .       .         . > + . > + + .

 Posts: 39
 Joined: Wed Apr 25, 2007 1:35 am UTC
 Location: Illinois
 Contact:
themuffinking wrote:I want to kill problem #14 with fire. It's about finding the maximum cycle length in the collatz conjecture scenario with a starting point under a million.
Every single time, I get 910107 with 475 cycles as the maximum. Every time. I checked it, that's how many cycles there are. In fact, I checked a random sample of 45 different numbers, all of which are correct in their cycle lengths. Why? Why does it mock me?
I get 837799. Don't have my own source handy, but its pretty much the same as this solution, in ruby
def next_num(n)
n % 2 == 0 ? n / 2 : 3 * n + 1
end
sequences = {}
max_sequence_start = 0
max_sequence_length = 0
sequence_length = 0
sequence_number = 0
1.upto(999999) do num
sequence_length = 1
sequence_number = num
while sequence_number > 1
unless sequences[sequence_number]
sequence_number = next_num(sequence_number)
sequence_length += 1
else
sequence_length += (sequences[sequence_number]  1)
break
end
end
sequences[num] = sequence_length
if sequence_length > max_sequence_length
max_sequence_start = num
max_sequence_length = sequence_length
end
end
puts "Solution: #{max_sequence_start} = #{max_sequence_length}"
 musicinmybrain
 Posts: 96
 Joined: Sun Dec 31, 2006 2:50 am UTC
 Location: Greensboro, NC
johnw188 wrote:I get ######. Don't have my own source handy, but its pretty much the same as this solution, in ruby
I was trying to avoid posting solutions, but since you did, I'll confirm it and post my Python code. Can we agree not to post spoilers for other problems, though? I like that spoilers aren't really out there anywhere for Project Euler. Can't stop you, of course, if you disagree.
Code: Select all
starter = 1
term = 1
count = 0
hashes = {1:0}
this_sequence = []
best_starter = 1
while starter < 1000000:
this_sequence.append(term)
if term in hashes:
hashes.update(dict(zip(this_sequence, xrange(len(this_sequence)  1 + hashes[term], hashes[term]  1, 1))))
if hashes[starter] > hashes[best_starter]:
best_starter = starter
while starter in hashes:
starter += 1
term = starter
this_sequence = []
elif term & 1: # if odd
term = 3 * term + 1
else:
term >>= 1
print best_starter
Runs in 23 seconds on my 1.9 GHz P4; there's surely a more efficient way, but it works.
+ + + + + + + + [ > + + + + [ > + + > + + + > + + + > + < < < <  ] > + >  > + > > + [ < ] <  ] > > . > >    . + + + + + + + . . + + + . > . < <  . > . + + + .       .         . > + . > + + .
 Agent Anderson
 Posts: 25
 Joined: Mon May 21, 2007 11:44 am UTC
Project Euler
Hi all
I've just discovered Project Euler and have been neglecting work to get some problems done...
I've gotten stuck on number 10; here's my code:
The answer I get
is not accepted by the website.
Can anyone see where I've gone wrong?
I've just discovered Project Euler and have been neglecting work to get some problems done...
I've gotten stuck on number 10; here's my code:
Spoiler:
The answer I get
Spoiler:
is not accepted by the website.
Can anyone see where I've gone wrong?
Re: Project Euler
To get the correct answer, you need to change exactly one character in the primes function.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Project Euler
Didn't we already have a project euler thread? Or did we just hijack other threads?
Anyway, my solution for problem 10:
Anyway, my solution for problem 10:
Code: Select all
sum . takeWhile (<2000000) $ primes
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Re: Project Euler
shrdlu wrote:To get the correct answer, you need to change exactly one character in the primes function.
Got it. Now I just need to figure out why it worked...
Spoiler:
Re: Project Euler
Here's my solution in J:
Not that it's really very helpful.
http://www.jsoftware.com
Code: Select all
+/ i. &. (p:^:_1) x: 2e6
Not that it's really very helpful.
http://www.jsoftware.com
Thus spake Cartofel.
And yea, there were great rollings of eyes, and shakings of heads.
And yea, there were great rollings of eyes, and shakings of heads.
Spoiler:
 Zamfir
 I built a novelty castle, the irony was lost on some.
 Posts: 7594
 Joined: Wed Aug 27, 2008 2:43 pm UTC
 Location: Nederland
Re: Project Euler
I've seen a few of those J entries in project Euler, but there seems to be absolutely no point to the language except for making oneliners for Project Euler. Am I missing something, or those PE entries not representative?
Re: Project Euler
Well... J is quite efficient (owing in part to the compactness of the code etc.). But you can do almost all of the things you could do with, say, C++, and perhaps those too, if you write a DLL.
If you want a few examples of things people have done with J (in many, many fewer lines than it would take in another language), look at http://www.jsoftware.com/jwiki/Showcase .
If you want a few examples of things people have done with J (in many, many fewer lines than it would take in another language), look at http://www.jsoftware.com/jwiki/Showcase .
Thus spake Cartofel.
And yea, there were great rollings of eyes, and shakings of heads.
And yea, there were great rollings of eyes, and shakings of heads.
Spoiler:
Re: Project Euler
Here's my C solution to number 10:
Spoiler:
Sandry wrote:Bless you, Briareos.
Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.
Re: Project Euler
Zamfir wrote:I've seen a few of those J entries in project Euler, but there seems to be absolutely no point to the language except for making oneliners for Project Euler.
J is based on APL, which is a formulabased programming language that's still used by IBM big iron. The bitch of APL is that it uses a nonascii character set.
Here's conway's game of life in APL:
J basically removes the special character set.
 thoughtfully
 Posts: 2253
 Joined: Thu Nov 01, 2007 12:25 am UTC
 Location: Minneapolis, MN
 Contact:
Re: Project Euler
[tongueincheek]
Haven't you read the unix fortunes? APL is the butt of every third joke, it seems sometimes. Goodnaturedly, of course.
A lot of people might say that the bitch of APL is that its more of a writeonly language than PERL
Which isn't to say that it can't be useful or fun. Very useful, if you are using a 300 baud teletype
[/tongueincheek]
Haven't you read the unix fortunes? APL is the butt of every third joke, it seems sometimes. Goodnaturedly, of course.
Unix fortune database wrote:'Tis the dream of every programmer,
ere his life is done
to write three lines of APL
and make the damn thing run.
A lot of people might say that the bitch of APL is that its more of a writeonly language than PERL
Which isn't to say that it can't be useful or fun. Very useful, if you are using a 300 baud teletype
[/tongueincheek]
Re: Project Euler
One problem I seem to be running into a lot is overflow. I'm solving most of the problems using C. Are there any good tricks to avoiding overflow?
If it helps, one problem I ran into trouble with was number 14.
If it helps, one problem I ran into trouble with was number 14.
Re: Project Euler
I've done quite a bit of brute forcing so far, probably not in the Euler spirit, but I'm just learning....
I use the BigInteger class in java.
I use the BigInteger class in java.
Re: Project Euler
I had thought about implementing something like that, but I'll see what I come up with on a per problem basis.
I'm pretty happy that I solved number 9 with close to the optimal solution.
I'm pretty happy that I solved number 9 with close to the optimal solution.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Project Euler
Compensating for overflow in certain problems: Modular exponentiation.
Also, longs are good for most problems. Unsigned longs can be twice as big, which means they'll be good for twice the number of problems.*
*Yes, I know it's a fallacy.
Also, longs are good for most problems. Unsigned longs can be twice as big, which means they'll be good for twice the number of problems.*
*Yes, I know it's a fallacy.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Re: Project Euler
Berengal wrote:Also, longs are good for most problems. Unsigned longs can be twice as big
Java has the nice property that the sizes of int and long are specified by the language. This is not so by C and C++, where the size of int and long depend on the compiler, which in turn depends on which hardware it was written for.
Pesto, on many C implementations int and long are the same size. You may be able to use the 'long long' type instead. Write a program to print out sizeof(long) and sizeof(long long) to see what's up in your case. Note that the long long type is part of the C99 standard, and if you are running a C compiler in C89 conforming mode then it won't recognise it.
Re: Project Euler
jaap wrote:This is not so by C and C++, where the size of int and long depend on the compiler, which in turn depends on which hardware it was written for.
That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.
Re: Project Euler
mrkite wrote:That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.
it's C99, not POSIX, that gave us that.
Code: Select all
factorial = product . enumFromTo 1
isPrime n = factorial (n  1) `mod` n == n  1
Re: Project Euler
While we're on the subject, can anyone give a few hints as to a quick test for semiprimality (exactly 2, not necessarily distinct factors)?
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.
Galileo
Galileo
Re: Project Euler
Seeing as that's what cryptography is based on, I'm going to guess the answer is no.
I'm fairly sure my current version of gcc doesn't support C99. Hell, I only learned about C99 a week or two ago.
I am, howdoyousayinthiscountry, out of the loop.
hotaru wrote:mrkite wrote:That's why POSIX gave us stdint.h You get uint16_t, uint32_t, and uint64_t and know exactly how many bits they take up. I never use int/short/long anymore.
it's C99, not POSIX, that gave us that.
I'm fairly sure my current version of gcc doesn't support C99. Hell, I only learned about C99 a week or two ago.
I am, howdoyousayinthiscountry, out of the loop.

 Posts: 1459
 Joined: Fri Apr 20, 2007 3:27 pm UTC
 Location: The Tower of Flints. (Also known as: England.)
Re: Project Euler
spdqbr wrote:While we're on the subject, can anyone give a few hints as to a quick test for semiprimality (exactly 2, not necessarily distinct factors)?
Fermat's method works well if N has a factor near sqrt(N). Might be worth a try.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
dubsola
dubsola
Re: Project Euler
Pesto wrote:I'm fairly sure my current version of gcc doesn't support C99. Hell, I only learned about C99 a week or two ago.
gcc 3+ supports C99 but it needs to be in c99 mode. However, stdint.h has been a part of the GNU C library since 1997.
Re: Project Euler
Speaking of solutions to problem 10, here's what I used in Python:
Only been using Python for a week or two, and haven't had the time to properly learn it, but I was able to write this on my own. And only with a few syntax errors.
To actually get the solution, I just used sum(psieve(2000000)). Well, okay, first I used a stupid brute force method. This sieve algorithm cut down the run time from 100 to 1.5 seconds. Any improvements to the above are welcome.
Spoiler:
Only been using Python for a week or two, and haven't had the time to properly learn it, but I was able to write this on my own. And only with a few syntax errors.
To actually get the solution, I just used sum(psieve(2000000)). Well, okay, first I used a stupid brute force method. This sieve algorithm cut down the run time from 100 to 1.5 seconds. Any improvements to the above are welcome.
Re: Project Euler
why is my sieve so slow? the one above me takes 0.0940001010895 seconds to run, for n = 100,000 whereas mine takes 85.8440001011:
Code: Select all
import time
def prsieve(N):
'Returns all primes <= N in list prim'
prim = []
prim = range(2,N+1)
n = 0
p = 0
while p <= N**.5:
p = prim[n]
for x in prim:
if x%p == 0 and x != p:
prim.remove(x)
n += 1
return prim
t = time.time()
prsieve(100000)
print time.time()  t
Who is online
Users browsing this forum: No registered users and 8 guests