Pesto wrote: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.

Most programs are small enough to be done with long in Java.

But what I did was picked up basic basic ruby. You can dl and install it in 2 minutes, it's that easy. And with basically my C knowledge changed syntactically, I was able to solve probably 70+ of them with Ruby... I didn't even know what a class was at that time.

I believe you can declare in C an "unsigned long long" which should be a 64 bits unsigned integer which should range from 0 to 18.446.744.073.709.551.615 (more than 1.8*10^19) if I'm correct which should be enough for most of the problems (but not always...)

Re: Project Euler

Posted: Tue Nov 04, 2008 2:38 pm UTC

by HenryGifford

I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?

Re: Project Euler

Posted: Tue Nov 04, 2008 3:04 pm UTC

by Baxter

Try to strip all of the problems down to the bare minimum required, can you isolate any cases that you're sure you don't need to test?

Try to define tight upper and lower bounds to all of the problems

If you're searching thought a list of numbers and one of the conditions is that the result must be a multiple of 20, you then have a dramatically reduced search space as you can generate multiples of 20 and test them for the rest of the conditions.

For the following conditions you should test in order of decreasing rarity for example if you also have to check if the numbers are a prime and if the numbers are odd you'd want to filter with your prime test first as it will lead to fewer numbers being pass to the function that tests if they're odd or not.

Re: Project Euler

Posted: Wed Nov 26, 2008 1:25 am UTC

by zed0

Any suggestions on a more elegant way to solve problem 16 in C++, apart from getting some bigNum library (I wanted to try it manually the first few times at least)?

(please don't look at this unless you've solved it yourself)

(defn natural [] (iterate #(+ % 1) 1)) (def primes ;;takes a sorted set of counters and a seq of numbers to filter ((fn sieve [in-counters checked] ;;first part of the cons is the first in said seq. hurray! (lazy-cons (first checked) ;;this bit takes the set of counters, and the unchecked seq (loop [counts in-counters unchecked (rest checked)] (let [count (first counts) [c p] count u (first unchecked)] ;;if first in seq = a counter, composite -> try next in seq (cond (= c u) (recur counts (rest unchecked)) ;;if the counter is smaller, increment it and try again (< c u) (recur (conj (disj counts count) [(+ c p) p]) unchecked) ;;if the counter is bigger, first in seq is prime (> c u) (sieve (conj counts [u u]) unchecked)))))) ;;feed it a set with 2's counter and a seq from 2 (sorted-set [2 2]) (rest (natural))))

;;the bit that actually gives the answer (reduce + (take-while #(> 2000000 %) primes))

it's rather slow, since it has none of the optimizations you'd normally use on this type of thing. i couldn't square the counters, because the comparator was throwing a fit if i gave it a long integer. (it gets up to 40000 or so with the squaring before it breaks, and it's considerably faster. what this means is that i need to build a better priority queue.)

Re: Project Euler

Posted: Fri Nov 28, 2008 6:00 pm UTC

by RoadieRich

HenryGifford wrote:I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?

1. Master generator expressions (f(x) for x in l if condition(x)) 2. Master generator functions (see below) 3. Build a library of useful functions. I have a module called primes, which has a sieve, an iteerative prime number generator, and various derivative functions.

def count2(start_at=0): """yield every other number, starting with start_at""" while True: yield start_at start_at += 2

For a long while, that generator was an integral part of my prime number generator.

(I then realized it was faster (and more efficient) to use a version of 6n+/-1, but that's an exercise for the reader.) w

Re: Project Euler

Posted: Fri Nov 28, 2008 6:56 pm UTC

by HenryGifford

RoadieRich wrote:

HenryGifford wrote:I'm attempting to do Project Euler in Python but I'm not quite a master of the language. (I'm good, but not amazing.) Any tips to start out?

1. Master generator expressions (f(x) for x in l if condition(x)) 2. Master generator functions (see below) 3. Build a library of useful functions. I have a module called primes, which has a sieve, an iteerative prime number generator, and various derivative functions.

primes :: [Integer] primes = 2:3:primes' where -- Every prime number other than 2 and 3 must be of the form 6k + 1 or -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as -- prime (6*0+5 == 5) to start the recursion. 1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]] primes' = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes' divides n p = n `mod` p == 0

main = print . sum . takeWhile (< 2000000) $ primes

$ ghc --make -O2 prob10.hs $ time ./prob10

Spoiler:

142913828922

real 0m2.528s user 0m2.512s sys 0m0.016s

Re: Project Euler

Posted: Fri Dec 19, 2008 5:56 pm UTC

by luke77

Has anyone done 34? I've written what seems to be a solid algorithm to solve it, but the only number I'm coming up with is the one they give, 145. At least in tests up to 5000000. Is there a special way to solve this?

Re: Project Euler

Posted: Fri Dec 19, 2008 6:23 pm UTC

by Xanthir

luke77 wrote:Has anyone done 34? I've written what seems to be a solid algorithm to solve it, but the only number I'm coming up with is the one they give, 145. At least in tests up to 5000000. Is there a special way to solve this?

No, it should be extremely straightforward. My algorithm is a 3-liner, and that's with no tricks - it's simply the way anyone would first think of solving it.

Do you have a function for breaking a number into its constituent digits? That should make this trivial.

Hint, if you need it:

Spoiler:

Obviously, there's no way you'll need to loop is below 10M. However, the answer is actually quite substantially less than this - it's below 100k.

Algorithm that will solve it correctly in Lisp (again, only if you need it):

while first<=sequencelength: last=first+1 while thesum<=1000000: shortenedseq=primes[first:last] thesum=sum(shortenedseq) if thesum in primesclone: newlen=last-first if newlen>=lenfinal: lenfinal=newlen answer=thesum last+=1 first+=1 return answer

The list of primes I'm passing in helped me solve an earlier problem correctly, so I think it's correct. Here is the code I used:

Spoiler:

def erat(lim): array =range(lim+1)

firstprime=2 multiplier=2 while firstprime<=(lim**.5+1):

while firstprime*multiplier<=(lim):

array[firstprime*multiplier]=0 multiplier+=1 firstprime=getNextPrime(array,firstprime) multiplier=2 answers=[] for i in array: if not i==0: answers.append (i)

return answers

Re: Project Euler

Posted: Mon Dec 22, 2008 12:40 am UTC

by jaap

luke77 wrote:Any hints on number 50? I keep getting 886591, using the following code:

Please use the code tags for your code - that's what they're for. It is impossible to read python when the indentation is stripped. That said, I don't immediately see a problem in your programs.

To help you find your problem, here are some facts you might want to try to verify. - The sum of the first 60 primes, 2 up to 281, is the prime 7699. - The only way to get a sum of some consecutive primes to be 886591 is by using the 31 primes from 28477 to 28711.

Re: Project Euler

Posted: Mon Dec 22, 2008 7:15 am UTC

by luke77

Hmm...I'm getting the same result as you for the first sixty primes. There must be something wrong with my function. I'll try rewriting tomorrow.

EDIT: Is the length of the entire list of primes to 1000000 78500?

Re: Project Euler

Posted: Mon Dec 22, 2008 5:37 pm UTC

by Berengal

I'm getting 78498 for my prime below 1000000, with the highest being 999983. I'm pretty sure it's correct (using the list in my sig).

Re: Project Euler

Posted: Mon Dec 22, 2008 7:01 pm UTC

by RoadieRich

Berengal wrote:I'm getting 78498 for my prime below 1000000, with the highest being 999983. I'm pretty sure it's correct (using the list in my sig).

I got exactly the same using my generator, so confirmation of correctness.

Re: Project Euler

Posted: Mon Dec 22, 2008 7:26 pm UTC

by Kag

I've been working on 222, and I'm sort of stuck.

I know how to calculate the minimum length of the pipe given a certain configuration of the balls, but I don't know which configuration would be the most efficient. Obviously brute forcing it isn't an option, since there are 21! possible orders. Any ideas?

Re: Project Euler

Posted: Mon Dec 22, 2008 11:39 pm UTC

by luke77

That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

last=first+20 while thesum<=1000000: shortenedseq=primes[first:last] thesum=sum(shortenedseq) if isPrime(thesum) : newlen=last-first if newlen>=lenfinal: lenfinal=newlen answer=thesum last+=1 first+=1 return answer

Re: Project Euler

Posted: Mon Dec 22, 2008 11:53 pm UTC

by jaap

luke77 wrote:That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

When thesum exceeds 100000 and it exits the inner loop, when will it enter the inner loop again?

Kag wrote:Obviously brute forcing it isn't an option, since there are 21! possible orders. Any ideas?

Try a smaller number of circles. Explore the problem and its answers. Extend that to original problem.

Re: Project Euler

Posted: Tue Dec 23, 2008 12:11 am UTC

by luke77

jaap wrote:

luke77 wrote:That's right, I was accidentally adding an extra 2 in there. So my list is correct, but I don't see where my code is in error. Does anyone see the problem in this function?

When thesum exceeds 100000 and it exits the inner loop, when will it enter the inner loop again?

When it exceeds 1000000 and exits the inner loop, 1 is added to "first" and then it reenters the inner loop as long as first is less than or equal to the length of the original sequence. So, in effect, it tests primes[1:21], then primes[1:22], primes[1:23],etc.until the sum is greater than 1000000, then tests primes[2:22], primes[2:23], ...

I start with sequences of length 20 simply because I know that the answer will have a sequence length greater than 20.

Re: Project Euler

Posted: Tue Dec 23, 2008 7:21 am UTC

by jaap

luke77 wrote:...until the sum is greater than 1000000, then tests primes[2:22], primes[2:23], ...

I know that is what you intended, but that is not what will happen. Think about the (sum<=100000) condition of the inner loop. What is the value of thesum when it reaches the start of that inner while loop the second time?

Re: Project Euler

Posted: Tue Dec 23, 2008 8:15 pm UTC

by AttackAttack

Haha, I love Project Euler, even though I haven't attempted any problems yet. I'm going to use Ruby to do it, but that means I have to learn Ruby, which is incredibly fun. Learning Ruby for that kind of thing is a lot easier than learning Python for it. To me, at least...

Re: Project Euler

Posted: Wed Dec 24, 2008 8:43 pm UTC

by Qoppa

I just got number 39 using Haskell! Hooray! My solution's rather verbose (15 lines), but it gets me the answer in ~0.4 seconds.

from Module import factorial g,l=0,0 for d in range(1,6000): #I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number.. for i in range(0,len(str(d))): g+=factorial(int(str(d)[i])) if g==d: l+=d print l

g,l=0,0 for i in range(0,len(str(145))): g+=factorial(int(str(145)[i])) if g==145: l+=145 print l

It prints 145. What's the deal??

Re: Project Euler

Posted: Wed Dec 31, 2008 1:37 am UTC

by spdqbr

@HenryGifford: The problem is that the value of g is not behaving like you think it is. Walk through by hand for d in range(1,4) and you should get it (or just print g and l for every iteration and it should become clear).

Also,

HenryGifford wrote:I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number..

You are correct, but you can figure out which number.

Spoiler:

What's the most you can add to the sum of the factorial of the digits of a number by adding a digit?

Re: Project Euler

Posted: Wed Dec 31, 2008 1:44 am UTC

by HenryGifford

spdqbr wrote:@HenryGifford: The problem is that the value of g is not behaving like you think it is. Walk through by hand for d in range(1,4) and you should get it (or just print g and l for every iteration and it should become clear).

Also,

HenryGifford wrote:I don't know why I'm using 6000... But the problem doesn't say how far to go up to, so I'm gonna assume that there aren't any above a specific number..

You are correct, but you can figure out which number.

Spoiler:

What's the most you can add to the sum of the factorial of the digits of a number by adding a digit?

Aha! Thanks, I've had that problem before, should have realized.

Re: Project Euler

Posted: Sun Jan 11, 2009 3:32 am UTC

by katkov

I tried to do a Sieve of Eratosthenes for Problem 10 and ended up with this

public class Prob10 { public static void main(String args[]) { final int NUM=2000000; int list[]= new int[NUM+1]; for(int i=0;i<=NUM;i++) { list[i]=i; } list[1]=0; for(int j=2;j<=NUM;j++) { if (list[j] != 0) { for(int k=j*2;k<=NUM; k+=j) { list[k]=0; } } } int total=0; for(int l=0; l<=NUM; l++) { total+=(int)list[l]; } System.out.println(total); } }

And it gives me 1179908154, and I tried it with 1 million instead of two and it gave me a negative number. I can't figure what I did wrong

Re: Project Euler

Posted: Sun Jan 11, 2009 3:52 am UTC

by Berengal

From a very brief glimpse at your code, I'd suggest changing total to a long.

Re: Project Euler

Posted: Sun Jan 11, 2009 5:10 am UTC

by katkov

Berengal wrote:From a very brief glimpse at your code, I'd suggest changing total to a long.

And that was the problem ok thanks

Re: Project Euler

Posted: Fri Jan 16, 2009 2:44 am UTC

by spdqbr

Problems 103, 105, and 106 have been kicking my ass for a loooooong time now. They deal with special sum sets, and my brute force solution just doesn't cut it.

Can anyone give a hint or point me in the right direction?

class Integer def factorial result = self (self-1).downto(1) { |n| result *= n } return result end end result_array = [] start = Time.now 3.upto 1_000_000 do |n| result = 0 n.to_s.split(//).each{ |d| #split the number and factor the digits result += d.to_i.factorial break if result > n } if result == n result_array << n puts n end #puts "Progress: " + n.to_s if n%50_000 == 0 end puts "------" puts Time.now - start puts "------" result_array.each do |i| puts i end

some dirty hacks inside, but I just can't figure out a result. 145 ist the only number I get as result

Re: Project Euler

Posted: Sat Jan 17, 2009 1:38 pm UTC

by jaap

DarkRat wrote:Problem 34:

0! = 1

Re: Project Euler

Posted: Sat Jan 17, 2009 1:57 pm UTC

by DarkRat

jaap wrote:

DarkRat wrote:Problem 34:

0! = 1

meh, thanks

Re: Project Euler

Posted: Sat Jan 17, 2009 4:47 pm UTC

by Kag

jaap wrote:Try a smaller number of circles. Explore the problem and its answers. Extend that to original problem.

Got it. Took me a while to write something to brute-force scaled down versions, but the problem is hilariously easy after that. I'd still like to write a solution that can solve this on its own, though.

Re: Project Euler

Posted: Thu Jan 29, 2009 4:22 am UTC

by spdqbr

Re my previous post, I've finally nailed down 106 (combinitorically, didn't even need code), and 105. 103 can't be far now! (sorry, I'm stoked )

Re: Project Euler

Posted: Thu Jan 29, 2009 6:33 am UTC

by stone915

Just found this and I'm working on problem 3. Here's my code:

getFactors :: Integer -> [Integer] -> [Integer] getFactors x [] = [] getFactors x (p1:ps) | (mod x p1) == 0 = p1 : (getFactors x ps) | otherwise = getFactors x ps

Anybody want to tell me what the runtime of it is? Because I think it's at least O(n^3), which is horrifying, especially for the number they gave us.

And it's had one of my processor cores maxed out for the past 10-15 minutes.

Re: Project Euler

Posted: Thu Jan 29, 2009 9:24 am UTC

by Berengal

Actually, you might want to start by defining all prime numbers and then start factorizing from there. The coolest prime definition I've seen is 'primes = nubBy (((>1) .) . gcd) [2..]' but it's not as efficient as the one I use (which is still a one-liner, if a little longer).

Keep a file containing various definitions, such as the list of primes, factorization, all divisors, power set etc. It'll be handy. E.g. when I got to problem 10 on my haskell run my answer was simply 'sum . takeWhile (<2*10^6) $ primes'