Page 4 of 11

Re: Project Euler

Posted: Fri Oct 31, 2008 7:31 am UTC
by angel.white
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.

http://www.ruby-lang.org/en/downloads/

Re: Project Euler

Posted: Fri Oct 31, 2008 9:10 am UTC
by Dongorath
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)

Spoiler:

Code: Select all

#include <iostream>
#include <vector>
using namespace std;

void longMult(int, vector<int> &);

int main()
{
   int power = 1000;
   int baseNum = 2;
   int total;
   vector<int> bigNum(1,1);

   for(int i=1; i<=power; ++i)
   {
      total = 0;
      cout << i << ": length = " << bigNum.size()+1 << " ";
      longMult(baseNum, bigNum);
      for(int j=bigNum.size()-1; j>=0; --j)
      {
         cout << bigNum.at(j);
         total += bigNum.at(j);
      }
      cout << ", total = " << total << endl;
   }
}

void longMult(int smallNum, vector<int> &bigNum)
{
   int carry = 0;
   for(int i=0; i<bigNum.size(); ++i)
   {
      bigNum.at(i)=(bigNum.at(i)*smallNum)+carry;
      carry = 0;
      if(bigNum.at(i)>=10)
      {
         if(i >= bigNum.size()-1)
         {
            bigNum.push_back(0);
         }
         carry = (bigNum.at(i)-(bigNum.at(i)%10))/10;
         bigNum.at(i) = bigNum.at(i)%10;
      }
   }
}

Re: Project Euler

Posted: Wed Nov 26, 2008 6:23 am UTC
by notallama
my solution for 10: (i was feeling crafty, so i used a lazy sieve)
Spoiler:

Code: Select all

(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.

Example generator:

Code: Select all

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.

Example generator:

Code: Select all

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

:shock:
...I'll work on that...

Re: Project Euler

Posted: Thu Dec 04, 2008 8:39 am UTC
by grom
Here is my haskell solution.
Spoiler:

Code: Select all

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):
Spoiler:

Code: Select all

(loop for i from 10 to 100000
    if (= i (apply '+ (mapcar 'factorial (number->digits i))))
    collect i)

factorial and number->digits aren't built in, but they're trivial to write.

Re: Project Euler

Posted: Fri Dec 19, 2008 8:01 pm UTC
by luke77
I think that's basically what I did, or tried to, although not as concisely. Here's my code in Python:

Spoiler:
def makeFact(bound):
#Return list of factorials, 0 through bound
facts=list()
facts.append(0)
for i in range(1,bound+1):
facts.append(fact(i))

return facts

def testInclude(upperbound):
#tests for curious numbers below upperbound

# first make a list of factorials 0 through 9, to prevent repeated function calls
facts=makeFact(9)

#We want to begin our search at 3 since 1 and 2 are excluded
testlist=[i for i in range(3,upperbound+1)]
answerlist=list()

for num in testlist:
thesum=0
for digit in str(num):
thesum=thesum+facts[int(digit)]
if thesum==num:
answerlist.append(num)
return answerlist



The only answer this returns is 145, and that's it...

Re: Project Euler

Posted: Fri Dec 19, 2008 9:20 pm UTC
by Xanthir
The factorial of 0 is 1. That's your problem.

Re: Project Euler

Posted: Sat Dec 20, 2008 1:38 am UTC
by luke77
Ahhh...thanks. Time to retake ninth grade math...

Re: Project Euler

Posted: Sun Dec 21, 2008 8:41 pm UTC
by luke77
Any hints on number 50? I keep getting 886591, using the following code:

Spoiler:
def findContig(primes):
first=0
last=0
lenfinal=0
answer=0
thesum=0
primesclone=primes[:]
sequencelength=len(primes)

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?

Code: Select all

def findContig(primes):
   first=0
   last=0
   lenfinal=0
   answer=0
   thesum=0
   primesclone=primes[1:]
   sequencelength=len(primes)
   
   while first<=sequencelength:
   
      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.

Re: Project Euler

Posted: Tue Dec 30, 2008 11:47 pm UTC
by HenryGifford
My problems are endless.
My code for problem 34

Code: Select all

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
It just comes up with 1. When I try it as simply:

Code: Select all

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

Code: Select all

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?

Re: Project Euler

Posted: Sat Jan 17, 2009 1:29 pm UTC
by DarkRat
Problem 34:

Code: Select all

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 :D

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 8) )

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:

Spoiler:

Code: Select all

getLargestPrime :: Integer -> Integer
getLargestPrime n = getPrime (reverse (getFactors n [2..n]))

getPrime :: [Integer] -> Integer
getPrime (p1:ps) | (length $ getFactors p1 ps) == 0 = p1
                 | otherwise = getPrime ps

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'