# Project Euler, anyone? (for all the programmers out there)



## Rinfiyks (Nov 22, 2010)

So has anyone ever been on Project Euler? If so, how often do you use it? How many have you solved? I've been doing 1 a day for a month now.

If not, basically, it's a website of over 300 mathematical problems designed to require a computer (mostly) and modest programming skills to solve. The first few are really easy, then they start to get challenging, requiring a well thought out algorithm to solve efficiently.
I recommend it to anyone who's learning a new language, and especially for all the enthusiastic mathematicians 

And of course, no spoilers please


----------



## ahmedkl (Nov 22, 2010)

I forgot my user name their and i solved like 7-8 problems there  , its too much mathematics oriented and i need to revise some stuff before i start again . What about you?


----------



## StachuK1992 (Nov 22, 2010)

I haven't participated in a while.
I think we could possibly have a little competition here, and keep track of who does how many. 

I'm going to make a new account and start from the beginning. (2 so far!)

-statue


----------



## Johannes91 (Nov 22, 2010)

It's been an on/off project since 2007 for me. I was briefly at 100% back when there were just ~210 problems but I've really fallen behind now.

I'm really happy that they've started using Combinatorial Game Theory (problems 301 and 310), it's one of my favourite areas of mathematics. Hopefully they'll add some harder CGT puzzles soon.


----------



## Rinfiyks (Nov 22, 2010)

ahmedkl said:


> I forgot my user name their and i solved like 7-8 problems there  , its too much mathematics oriented and i need to revise some stuff before i start again . What about you?


I've done 29 so far, trying to do them all in order 



StachuK1992 said:


> I think we could possibly have a little competition here, and keep track of who does how many.


You're on 



Johannes91 said:


> It's been an on/off project since 2007 for me. I was briefly at 100% back when there were just ~210 problems but I've really fallen behind now.


That's pretty impressive. How long does it usually take to do one of the harder problems? I've not tried any above 100 yet.


----------



## Johannes91 (Nov 22, 2010)

Rinfiyks said:


> How long does it usually take to do one of the harder problems? I've not tried any above 100 yet.


The ones that required some background knowledge I didn't have took literally days to solve, much of which was just reading books/Wikipedia. One of the most difficult for me was problem 182.

Note that newer problems aren't always harder than older ones. After the first 100-150 or so, they've roughly followed a pattern easy, medium, hard, medium, ...


----------



## TheBB (Nov 22, 2010)

I used to do it, but I got tired. There's so little variety. Just searching for numbers with random menial properties that nobody cares about.


----------



## Mr.Toad (Nov 22, 2010)

I like to solve those problems in my spare time. I solved 43 so far. Johannes91, could you recommend me any interesting book about algorithm design?


----------



## Laura O (Nov 22, 2010)

I solved about 50 problems 2 or 3 years ago. My part-time job was so boring I had to do something meaningful.


----------



## Johannes91 (Nov 24, 2010)

Mr.Toad said:


> Johannes91, could you recommend me any interesting book about algorithm design?


It's important to be familiar with the most fundamental algorithms and data structures, and _Introduction to Algorithms_ does a good job at covering those (there are similar books that could be just as good or better, but I haven't read them). However, it doesn't say much about designing your own algorithms. I've read a few books that try to do that but I wouldn't recommend any of them; most of the advice is just obvious common sense and learning by doing is a better way to learn, at least for me.


----------



## rahulkadukar (Apr 14, 2011)

Hi,

I was solving Problem no 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I have written the solution below, can someone check and tell me where I am going wrong.


```
<?php
function p($a){$c=-$a;for($x=1;$x<=sqrt($a);$x++){
    if(fmod($a,$x)==0)
    {$c+=$x;
    if($a/$x!=$x)    
     $c+=($a/$x);
    }}return $c;}

$c=0;$int=0;
for($a=1;$a<=$_GET[n];$a++){$b=p($a);if($b>$a){$sum_of_abundants[$a]=true;$x[$c]=$a;$c++;}}

  for($i=0;$i<count($x);$i++)
    for($j=0;$j<=$i;$j++)
      $sum_of_abundants[$x[$i]+$x[$j]]=true;

$total = 0;
for($a=1;$a<=$_GET[n];$a++)
if($sum_of_abundants[$a]!=1)
$total+=$a;

echo $total;
?>
```


----------



## qqwref (Apr 14, 2011)

Your general approach should work, but your indentation/spacing is pretty bad, so I'm not even gonna try to figure out the details of whether each thing works as it's supposed to or not. What specifically goes wrong with your program? Did you test each part to find out which one's broken?


----------



## rahulkadukar (Apr 15, 2011)

```
<?php
function p($a)
	{
		$c=-$a;
		
		for($x=1;$x<=sqrt($a);$x++)
			{
				if(fmod($a,$x)==0)
					{	
						$c+=$x;
						if($a/$x!=$x)    
							$c+=($a/$x);
					}
			}
		return $c;
	}

$c=0;$int=0;

for($a=1;$a<=$_GET[n];$a++)
	{
		$b=p($a);
		if($b>=$a)
		{
			$sum_of_abundants[$a]=true;
			$x[$c]=$a;
			$c++;
		}
	}

  for($i=0;$i<count($x);$i++)
    for($j=0;$j<=$i;$j++)
      $sum_of_abundants[$x[$i]+$x[$j]]=true;

$total = 0;

for($a=1;$a<=$_GET[n];$a++)
	if($sum_of_abundants[$a]!=1)
		$total+=$a;

echo $total;
?>
```


----------



## Rinfiyks (Apr 15, 2011)

I don't understand PHP. Try explaining in words exactly how you're trying to solve it? Usually you'll realise a mistake half way through explaining


----------



## Stefan (Apr 15, 2011)

Seems wrong to include single abundant numbers in *sum*_of_abundants.



Rinfiyks said:


> I don't understand PHP.


 
Well, he doesn't really use any. If you don't understand that code, you likely can't program at all. That code actually could be understood even by someone who can't program at all but knows English and basic math.

Edit: solved it


----------



## Stefan (Apr 15, 2011)

Btw, your p-function to compute the sums of proper divisors works and surprisingly that's how pretty much everybody in the after-solving thread did it, but I prefer to just precompute them *upwards*, similar to the sieve of Eratosthenes:

```
# Spread each [U][B]n[/B][/U]umber onto its proper [U][B]m[/B][/U]ultiples
for ( n=1; n<29000; n++ )
  for ( m=2*n; m<29000; m+=n )
    sumOfProperDivisors[m] += n;
```
Simpler and faster than searching for divisors and needing complicating optimizations.


----------



## Rinfiyks (Apr 16, 2011)

Stefan said:


> Well, he doesn't really use any. If you don't understand that code, you likely can't program at all. That code actually could be understood even by someone who can't program at all but knows English and basic math.


Well I didn't try. There are no meaningful variable names (except sum_of_abundants) or functions, it looks like quite an ugly and confusing programming language, especially with no spacing. I couldn't understand that in under a minute.

But, I don't at all take kindly to being told I can't program, so I'll try the first bit 


Spoiler





```
<?php
function p($a)
    {
        $c=-$a;
        
        for($x=1;$x<=sqrt($a);$x++)
            {
                if(fmod($a,$x)==0)
                    {    
                        $c+=$x;
                        if($a/$x!=$x)    
                            $c+=($a/$x);
                    }
            }
        return $c;
    }
```
*<?* I don't know what this means. *PHP* I guess means he's writing in PHP.
*function p($a)*
I suppose p is the name of the function. I don't know what *$* is. I think a is a parameter. *{ }* for containing stuff.
*$c=-$a;* maybe *$* declares an integer? But a has already been declared...
*for($x=1;$x<=sqrt($a);$x++)* x from 1 to the square root of a inclusive. Still confused about these dollar signs
*if(fmod($a,$x)==0)* fmod? I guess this means the modulo operator. Checks if x is a divisor of a, I suppose.
*$c+=$x;* c, which is -a, is added x.
*if($a/$x!=$x) $c+=($a/$x);* != means not equal to? Then this statement expains why the x loop goes up just to square root of a.
*return $c;* I expected something like return (c > 0);, but okay.


It looks like you're right Stefan. I was just put off by glancing at the code box, and especially by seeing a spaghetti of letters and symbols without spacing.


Now I have a question myself. Can anyone solve problem 51 quickly? I have a time-consuming method drawn out in my head that's bound to take a long time to run. Is there a clever 1 second solution?


----------



## y3k9 (Apr 16, 2011)

I have a euler account, however I haven't been on it in a while nor have I been on here in while. =3

I only know python, java, and a bit of c++.






As you'll see in my widget ^^, I've solved 23 problems. I now I'm a bit nooby but it's still good considering im in sixth grade. =P

P.S. PHP bbcode? When and why was that put in there?


----------



## Stefan (Apr 16, 2011)

Rinfiyks said:


> it looks like quite an ugly and confusing programming language



Don't judge the whole language based on a single program written in it 

The "$" prefix just means it's a variable (see sigil). And yeah, his p-function is just pretty much the standard way to find divisors of a number, adapted to add them.



Rinfiyks said:


> Can anyone solve problem 51 quickly? [...] Is there a clever 1 second solution?



I just solved it, takes 0.094 seconds (Java, straightforward implementation).

Edit: 6 seconds with a straightforward 14 lines Perl program (more like 10 lines, the last four are just closing brackets). I suspect more clever regex usage is possible, but I didn't get it to work. Can anybody? I want something like
*while ( '11112222' =~ /somethingcleverhere/g ) { print "somethinghere\n" }*
to print all triple-patterns:
****12222
**1*2222
*1**2222
1***2222
1111***2
1111**2*
1111*2**
11112****
(not necessarily in that order)


----------



## Owen (Apr 16, 2011)

I like PHP.


----------

