name mode size
src 040000
README.md 100644 6 kb
README.md
# Project euler exercises and Solutions ## Instructions To compile these programs you need to install first the go programming language environment. You can find the instructions on the language official web page. Then you need to setup a environment variable export GOPATH=$HOME/work/goeuler And then you need to complie the programs by executing, for example for the exercise one , the following command go build ex1 Hopefully it will create a ex1 executable file on the *goeuler* folder. ## Exercises #### Multiples of 5 or 3 less than 1000 To find the sum of multiples of 5 or less than 1000 you need to iterate over all the first 1000 elements and check for the rest of the integer division so it is basically to check the following condition (i % 3 == 0 || i % 5 ==0) If this condition holds then we need to add the *i* value to the *sum* counter, so in a nutshell the procedure is as follows sum := 0 for i:=0; i< limit; i++ { if(i % 3 == 0 || i % 5 ==0){ sum += i } } #### Even Fibonacci Here we need to find the sum of even Fibonacci numbers that are lower than 4000000. To do the job all we need is to compute the Fibonacci sequence and sum only those even elements until the condition given stop being verified. The function follows func fiboEven(limit int) int { sum := 0 prev := 1 now := 2 aux := 0 for now < limit { if(now % 2 == 0){ sum += now } aux = prev prev = now now = now + aux } return sum } #### Large prime factor The problem here is to find the biggest prime factor of the number 600851475143. From number theory we know that the biggest factor of a number is always smaller than the square root of that same number so in this case 600851475143 ^ 1/2. To tackle the problem we split this in two subproblems. First we need to find all the prime numbers until a given condition and the use these set of prime numbers to find which of them divide the number given. The first part is done here func getFirstPrimes(less int) (primes []int , size int) { size = 1 primes = make([]int,size) primes[0]=1 flag := true for candidate:=2; candidate < less ;candidate++ { flag=true for i:=1; i<size ;i++{ if(candidate % primes[i] == 0){ flag=false } } if(flag){ primes = append(primes,candidate) size++ } } return } The last part of the problem is as follows func largePrimeFactor(value int) int { largePrime:=1 sqrt:=int(math.Sqrt(float64(value))) primes,size := getFirstPrimes(sqrt) for i := 0;i<size;i++ { if(value % primes[i] == 0){ largePrime=primes[i] } } return largePrime } #### Palindrome number Here we were challenged to find the biggest [palindrome](https://en.wikipedia.org/wiki/Palindrome) number that is a result of a multiplication between number of three digits. First we need to find a way to check if a number is a palindrome. For this we do two things, first we need to compute the length of the number and then we pick the first number and the last and we compare each other, after some time we found that could be done like this func isPalindrome(v int) bool { if (v < 0) { return false; } left:=0 right:=0 div := 1; for v / div >= 10 { div * = 10; } for (v != 0) { left = v / div; right = v % 10; if (left != right){ return false; } v = (v % div) / 10; div /= 100; } return true; } Then we use an auxiliary method to compute all the *n* digit number product and check for the biggest palindrome func computeBiggestPalindrome(dim int) int { palindrome:=0 aux := 0 for i:=0;i<dim;i++ { for j:=0;j<dim;j++ { aux = i*j if(isPalindrome(aux) && aux > palindrome){ palindrome=aux } } } return palindrome } #### Smallest multiples The challenge here is to find the smallest number that is divisible for all the numbers until 20. Here we don't need a program to iterate over all the solutions. We can use prime number properties and a fundamental theorem that says that any number is a product of prime numbers to find the smallest product. First we need to note that at least the product is bigger than the product of all the prime numbers until 20 so value > 1 x 2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 Then we need to find all the prime factorization for all the non prime numbers between 0 and 20, so 4 = 2 x 2 6 = 2 x 3 8 = 2 x 2 x 2 9 = 3 x 3 10 = 2 x 5 12 = 3 x 2 x 2 14 = 2 x 7 15 = 3 x 5 16 = 2 x 2 x 2 x 2 18 = 2 x 3 x 3 20 = 5 x 2 x 2 So the smallest number would be v = 1 x 2⁴ x 3² x 5 x 7 x 11 x 13 x 17 x 19 = 232792560 #### First 1000 digits index Fibonacci number We need to find the smallest index of the Fibonacci number that has 1000 digits. For this we need to take into account the theory we can find [here](http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#logs). Based on this we can compute the following function to get the number of digits of a Fibonacci number func digitsFibonacci(n int) int{ phi:=(1+math.Sqrt(5))/2 return int(math.Ceil(float64(n) * math.Log10(phi) - math.Log10(math.Sqrt(5)))) } The solution for the problem is given by the last line printed by the following set of instructions for n:=1;digitos<1000;n++{ digitos=digitsFibonacci(n); fmt.Println(digitos,"-",n) } #### Get the 10001 prime number We already have a function to get prime numbers less than a certain value. I just reuse this function with several atempts and figure out that if I call the function as getFirstPrimes(104750) this would return the first 10002 prime numbers since it returns also 1 as a prime number we retrieve the position 10002 as the 10001 prime number, which is 104743