a Monkey's Euler Solutions

[amonkeyseulersolutions-blog]

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

# 998001 - so what's the largest palindrome number less than this one - then check if it's a product of 3-digit numbers function ispalindrome { [cmdletbinding()] param( [int] $number ) process{ $digits = @() $next_int = $number while ($next_int -gt 9) { $digit = $next_int % 10 $digits = $digits + $digit $next_int = ($next_int / 10) - (($next_int % 10)/10) #(99099 / 10) - ((99099 % 10)/10) } $digits = $digits + $next_int #$digits #$digits.Equals([array]::Reverse($digits)) #$digits.Equals($digits[($digits.Length - 1)..0]) for($i = 0; $i -ile $digits.count; $i += 1) { #Write-Host $digits[$i] #Write-Host $digits[-($i+1)] if ($digits[$i] -ne $digits[-($i+1)]) { #Write-Host "Value $($digits[$i]) at position $i does not match value $($digits[-($i-1)]) at position -$($i+1) [NB: Going through the array backwards]" return $false } } return $true } } #ispalindrome 9909 #ispalindrome 99099 # largest product of 3-digit numbers $max = 999 * 999 for ($i = $max; $i -igt 0; $i -= 1) { if (ispalindrome $i) { Write-Verbose "Checking the palindrome $i" # is it divisable by a 3 digit number for($j = 999; $j -igt 100 ; $j -= 1){ Write-Verbose "Checking $i % $j ($($i % $j))" if ($i % $j -eq 0) { Write-Verbose "Checking the product $j" # it is divisable by 3 digit number - if it's a 3 digit number return $i and $j if (($i/$j -gt 99) -and ($i/$j -lt 1000)) { Write-host $i Write-Host $j return $true } } } } }

[amonkeyseulersolutions-blog]

reworking factorial to avoid PowerShell 1000 recusions limit

Turns out it was the recusionin the factorial function - i've reworked it to use a for loop

function factorial { [cmdletbinding()] param($x) if ($x -lt 1) { return "Has to be on a positive integer" } Write-Verbose "Input is $x" $fact = 1 for ($i = $x; $i -igt 0; $i -= 1){ #Write-verbose "i: $i" $fact = [System.Numerics.BigInteger]::Multiply($i , $fact) } Write-Verbose "i equals $i" $fact }

it's still running for factorial 486847...

[amonkeyseulersolutions-blog]

Problem #3

[amonkeyseulersolutions-blog]

amonkeyseulersolutions:

I’ve read that an integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p.

So I’ve written this:

Read More

Here's the fixed version...

function isprime { [cmdletbinding()] param($x) if ($x -lt 1) { return "Has to be on a positive integer" } # An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p $factorial = factorial ($x-1) Write-Verbose "Factorial: $($factorial.ToString())" [System.Numerics.BigInteger] $remainder = ($factorial + 1) % $x Write-Verbose "Remainder: $($remainder.ToString())" if ($remainder -eq 0) { return $true } else { return $false } }

And using that the largest prime factor can be found with this:

function Get-LargestPrimeFactor { [cmdletbinding()] param([int] $x) if ($x -lt 1) { return "Has to be on a positive integer" } $i = [int] [System.Math]::Sqrt($x) Write-Verbose "Square root: $i" for ( $i ; $i -gt 1 ; $i -= 1 ) { Write-Verbose "checking: $i" if ( ($x % $i) -eq 0 ) { Write-Verbose "Factor: $i" if (isprime $i) { Write-Verbose "Prime Number: $i" break } } } if ($i -gt 1) { Write-Output "The largest prime is $i" } else { Write-Output "No prime factor" } }

And just for completeness a function that returns them all:

function Get-PrimeFactors { [cmdletbinding()] param($x) if ($x -lt 1) { return "Has to be on a positive integer" } $output = @() $i = [int] [System.Math]::Sqrt($x) Write-Verbose "Square root: $i" for ( $i ; $i -gt 1 ; $i -= 1 ) { Write-Verbose "checking: $i" if ( ($x % $i) -eq 0 ) { Write-Verbose "Factor: $i" if (isprime $i) { Write-Verbose "Prime Number: $i" $output = $output + $i } } } $output }

which works for low number but gets the following error for the for the number from project euler...

PS C:\Users\Matt> Get-LargestPrimeFactor 600851475143 The script failed due to call depth overflow. The call depth reached 1001 and the maximum is 1000. + CategoryInfo : InvalidOperation: (1001:Int32) [], ParentContainsErrorRecordException + FullyQualifiedErrorId : CallDepthOverflow

it needs a couple of for loops? where depends on what is being called more than 1000 times?

[amonkeyseulersolutions-blog]

An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p

I've read that an integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p.

So I've written this:

function isprime { [cmdletbinding()] param([int] $x) if ($x -lt 1) { return "Has to be on a positive integer" } # An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p [int] $factorial = factorial ($x-1) Write-Verbose "Factorial: $factorial" $remainder = ($factorial + 1) % $x Write-Verbose "Remainder: $remainder" if ($remainder -eq 0) { return $true } else { return $false } }

Unfortunately it doesn't work for some numbers known to be prime - 29 is the example I have...

[amonkeyseulersolutions-blog]

factorial...

function factorial { [cmdletbinding()] param([int64] $x) if ($x -lt 1) { return "Has to be on a positive integer" } if ($x -eq 1) { [int64] $x } else { [int64] $x * (factorial ($x-1)) } }

[amonkeyseulersolutions-blog]

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

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

# function fib { [cmdletbinding()] param ( [int] $x ) process { if ($x -lt 2) { $x } else { $n1 = $x - 1 $n2 = $x - 2 $fib2 = fib $n2 $fib1 = fib $n1 $result = $fib1 + $fib2 #Write-Verbose $result $result } } } #fib 5 -Verbose Write-Host "___________-------------______________" $ScriptStartTime = date for ($i = 0; $fib -lt 4000000 ; $i+=1) { $fib = fib $i Write-Host -ForegroundColor Magenta "fib = $fib" If ($fib % 2 -eq 0 ) { $sum += $fib Write-Host -ForegroundColor Green "sum = $sum" } } $ScriptEndTime = date $ScriptDuration = $ScriptEndTime - $ScriptStartTime Write-Host "`n Time Taken:" + $ScriptDuration #

[amonkeyseulersolutions-blog]

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

# Solution to Euler's Problem #1 for ($i = 1; $i -lt 1000; $i += 1) {if ( ($i % 3 -eq 0) -or ($i % 5 -eq 0) ) { $count += $i } };$count #