Euler Problem 12

I skipped a number of Euler problems since my last post. Anyway, here’s my powershell solution to Problem 12.

http://projecteuler.net/problem=12

It’s not that elegant but it solved the problem in less than 4mins :-)

1. function Count-Divisors($num) 
2. { 
3.     $totalDivisors = 2 
4.     $subTotal = 0 
5.     $localDivisor = 2 
6.     $localNum = $num 
7.      
8.     while($localNum -gt 1) 
9.     { 
10.         if(($localNum%$localDivisor) -eq 0) 
11.         { 
12.             $subTotal++ 
13.             $localNum/=$localDivisor 
14.         } 
15.         else 
16.         { 
17.             if($subTotal -gt 0) 
18.             { 
19.                 $totalDivisors*=($subTotal+1) 
20.                 $subTotal = 0 
21.             } 
22.             $localDivisor++ 
23.         } 
24.     } 
25.      
26.     return $totalDivisors 
27. } 
28.  
29. function Get-FTNumber($start, $divisors) 
30. { 
31.     $i=$start 
32.     while ((Count-Divisors ($i * ($i+1)/2)) -le $divisors) 
33.     { 
34.         $i++ 
35.     } 
36.      
37.     return ($i * ($i+1)/2) 
38. } 
39.  
40. echo (Get-FTNumber 2 500) 

Display Top Level Folder/File Sizes

It’s been a long, long time since my last post. Last week, I was having a problem with my office hard disk. It doesn’t have much disk space anymore and it’s performing very, very slow. I thought it would be nice to have a powershell script which displays the top level folder/file sizes in a given path. It’s also cool to have the largest folder/file displayed on top.

I’m a huge fan of one-liners. Hence, here’s my solution in one powershell line.

1. ls | select Name, @{Name="Type";Expression={if($_.psIsContainer){"Directory"}else{"Folder"}}}, @{Name="Size(MB)";Expression={[Math]::Round($(ls $_.FullName -recurse| measure Length -sum).Sum/1MB, 2)}}| sort -property "Size(MB)" -desc 

Note: This script also indicates whether it’s a folder or file and rounds off the size to 2 decimal points in MB.

Euler Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Powershell Solution:

1. $SumOfSq = 1..100|%{[Math]::pow($_,2)}|measure -sum|%{$_.sum} 
2. $SqOfSum = 1..100|measure -sum|%{[Math]::pow($_.sum,2)} 
3. echo ($SqOfSum - $SumOfSq) 

Note: The solution may not be the optimized one… just a quick hack… I’ll revisit later for optimization if time permits… :-)

Euler Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Powershell Solution:

This can be done manually (pen/paper) using prime factorization.
However, since I love powershell… We’ll use it with prime factorization in mind…

1. function Get-Factors($number) 
2. { 
3.     [Array]$result = {1} 
4.     $factor = 2 
5.     while($number -gt 1) 
6.     { 
7.         if($number%$factor -eq 0) 
8.         { 
9.             $result += $factor 
10.             $number /= $factor 
11.         }  
12.         else 
13.         { 
14.             $factor += 1 
15.         } 
16.     }  
17.      
18.     return $result 
19. } 
20.  
21. function Get-NextMultiple($currentMultiple, $currentFactor) 
22. { 
23.     foreach($factor in Get-Factors($currentFactor)) 
24.     { 
25.         $currentMultiple = $currentMultiple * $factor.ToString() 
26.         if($currentMultiple%$currentFactor -eq 0) 
27.         { 
28.             return $currentMultiple 
29.         } 
30.     } 
31. } 
32.  
33. $currentMultiple = 1 
34. 1..20|foreach{($currentMultiple = Get-NextMultiple $currentMultiple $_)}|measure -max|%{$_.Maximum} 

Note: The solution may not be the optimized one… just a quick hack… I’ll revisit later for optimization if time permits… :-)

Euler Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Powershell Solution:

1. function Reverse-Text([string] $text) 
2. { 
3.     if($text.Length -eq 1) 
4.     { 
5.         return $text 
6.     } 
7.     else 
8.     { 
9.         return (Reverse-Text($text.Substring(1, $text.Length-1))) + $text[0] 
10.     } 
11. } 
12.  
13. $start = 999 
14. $end = 100 
15. $max_palindrome = 0 
16. for($num1 = $start; $num1 -ge $end; $num1--) 
17. { 
18.     for($num2 = $num1; $num2 -ge $end; $num2--) 
19.     { 
20.         $product = $num1*$num2 
21.         if($product.ToString() -eq (Reverse-Text($product))) 
22.         { 
23.             if($product -gt $max_palindrome) 
24.             { 
25.                 $max_palindrome = $product 
26.             } 
27.         } 
28.     } 
29. } 
30.  
31. echo $max_palindrome 

Note: The solution may not be the optimized one… just a quick hack… I’ll revisit later for optimization if time permits… :-)

Euler Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Quick Powershell Solution:

1. $num = 600851475143  
2. $max_prime = 1 
3.  
4. $end1 = 0 
5. while($end1 -eq 0) 
6. { 
7.     $factor = 2 
8.     $end2 = 0 
9.     while($end2 -eq 0) 
10.     { 
11.         if($num%$factor -eq 0) 
12.         { 
13.             if($max_prime -lt $factor) 
14.             { 
15.                 $max_prime = $factor 
16.             } 
17.              
18.             $num = $num/$factor 
19.             $end2 = 1 
20.         } 
21.         $factor = $factor+1 
22.     } 
23.      
24.     if($num -eq 1) 
25.     { 
26.         $end1 = 1 
27.     } 
28. } 
29.  
30. echo $max_prime 

Note: The solution may not be the optimized one… just a quick hack… I’ll revisit later for optimization if time permits… :-)

Euler Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Powershell Solution:

1. $n1 = 1 
2. $n2 = 1 
3. $sum = 0 
4. while(($n1+$n2) -lt 4e+6) 
5. { 
6.     if($n2 -gt $n1) 
7.     { 
8.         $n1=$n1+$n2 
9.         if($n1%2 -eq 0) 
10.         { 
11.             $sum = $sum + $n1 
12.         } 
13.     } 
14.     else 
15.     { 
16.         $n2=$n1+$n2 
17.         if($n2%2 -eq 0) 
18.         { 
19.             $sum = $sum + $n2 
20.         } 
21.     } 
22. }  
23. $sum 

$sum = 4613732

The above solution doesn’t look that elegant though…
I think it can still be optimized… but anyway, I’ll try again if I have the time…