Project Euler 17

O problema 17 do Project Euler propõe como desafio somar o número de letras dos números de 1 a 1000 escritos por extenso. Vamos adaptar o problema para o português do Brasil, mantendo-se a mesma proposta.

[int]$sum = 0

Function decompPTBR([int]$num) {
    $unidade = @("dez","um","dois","três","quatro","cinco","seis","sete","oito","nove")
    $dez_nove = @("onze","doze","treze","quatorze","quinze","dezesseis","dezessete","dezoito","dezenove")
    $dezena = @("vinte","trinta","quarenta","cinquenta","sessenta","setenta","oitenta","noventa","cem")
    $centena = @("cento","duzentos","trezentos","quatrocentos","quinhentos","seiscentos","setecentos","oitocentos","novecentos","mil")

    If ($num -le 10) {
        Write-Host $num":" $unidade[$num % 10]
        Return $unidade[$num % 10].Length
    }
    If (($num -gt 10) -and ($num -lt 20)) {
        Write-Host $num":" $dez_nove[($num % 10)-1]
        Return $dez_nove[($num % 10)-1].Length
    }
    If (($num -ge 20) -and ($num -le 100)) {
        $u = $num % 10
        $d = [Math]::Truncate($num / 10) - 2
        If ($u -eq 0) { 
            Write-Host $num":" $dezena[$d] 
            Return $dezena[$d].Length
        }
        Else { 
            Write-Host $num":" $dezena[$d] "e" $unidade[$u]
            Return ($dezena[$d].Length + 1 + $unidade[$u].Length)
        } 
    }
    If (($num -gt 100) -and ($num -le 1000)) {
        $u = $num % 10
        $d = [Math]::Truncate(($num / 10) % 10) ## - 2
        $c = [Math]::Truncate($num / 100) ## - 1

        If (($d*10+$u) -eq 0) { 
            Write-Host $num":" $centena[($c-1)] 
            Return $centena[($c-1)].Length
        }
        Else {
            If (($d*10+$u) -le 10) {
                Write-Host $num":" $centena[($c-1)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $unidade[$u].Length)
            }
            If ( (($d*10+$u) -gt 10) -and (($d*10+$u) -lt 20) ) {
                Write-Host $num":" $centena[($c-1)] "e" $dez_nove[($u-1)]
                Return ($centena[($c-1)].Length + 1 + $dez_nove[($u-1)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -eq 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -gt 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length + 1 + $unidade[$u].Length)
            }
        }
    }
}

For ([int]$num=1; $num -le 1000; $num++) {
    $sum += decompPTBR($num)
}

Write-Host "=========================================="
Write-Host "Número de letras dos números de 1 a 1000:" $sum
Write-Host "=========================================="

Estamos imprimindo os números por extenso:

1: um
2: dois
3: três
4: quatro
5: cinco
6: seis
7: sete
8: oito
9: nove
10: dez
11: onze
12: doze
13: treze
14: quatorze
15: quinze
16: dezesseis
17: dezessete
18: dezoito
19: dezenove
20: vinte
21: vinte e um
22: vinte e dois
23: vinte e três
24: vinte e quatro

989: novecentos e oitenta e nove
990: novecentos e noventa
991: novecentos e noventa e um
992: novecentos e noventa e dois
993: novecentos e noventa e três
994: novecentos e noventa e quatro
995: novecentos e noventa e cinco
996: novecentos e noventa e seis
997: novecentos e noventa e sete
998: novecentos e noventa e oito
999: novecentos e noventa e nove
1000: mil
==========================================
Número de letras dos números de 1 a 1000: 19672
==========================================

Project Euler 10

Project Euler - Problema 10
Calcular a soma dos números primos abaixo de 2000000.

Function testPrimo([Long]$n) {
    if (($n % 2) -eq 0) { return $false }
    [Long]$c = 3
    while (($c * $c) -le $n) {
        if (($n % $c) -eq 0) { return $false } 
        else { $c +=2 }
    }
    return $true;
}

Function _Main([Int32]$max) {
    [Long] $somaPrimos = 0
    [Long] $num = 3
 
    while ($num -lt $max) {
        if ((testPrimo $num) -eq $true) {
            $somaPrimos += $num;
        }
        $num += 2; #com exceção do 2, todo primo é ímpar
    }
    $somaPrimos += 2
    Write-Host "A soma dos primos abaixo de $max é: $somaPrimos"
}

Clear-Host
_Main 2000000

A soma dos primos abaixo de 2000000 é: 142913828922

Project Euler - 9

Uma implementação para o problema 9 do Project Euler.

Function PE09 {
    For ([Int32]$a=1; $a -lt 333; $a++) {
        For ([Int32]$b=$a; $b -lt 500; $b++) {
            $c = 1000 - $a - $b
            If (($a+$b+$c) -eq 1000) {
                If (($a*$a+$b*$b) -eq ($c*$c)) {
                    Write-Host "a=$a"
                    Write-Host "b=$b"
                    Write-Host "c=$c"
                    Write-Host "a x b x c = " ($a*$b*$c)
                    Return
                }
            }
        }
    }
}

Clear-Host
PE09

a=200
b=375
c=425
a x b x c =  31875000

Project Euler - 8

Esta é uma implementação para o problema 8 do Project Euler: Encontrar em um número de 1000 dígitos, o maior número da multiplicação de 13 dígitos adjacentes.

Clear-Host

[String]$milDig = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
[Long]$Multi13 = 0
[Long]$curMulti = 0
$dig = (0,0,0,0,0,0,0,0,0,0,0,0,0)
$digSalvo = (0,0,0,0,0,0,0,0,0,0,0,0,0)

For ([Int32]$i=0; $i -lt 988; $i++) {
    For ($d=0;$d -lt 13;$d++) {
        $dig[$d] = [convert]::ToInt32($mildig[$i+$d],10)
    }    
    $curMulti = $dig[0]*$dig[1]*$dig[2]*$dig[3]*$dig[4]*$dig[5]*`
        $dig[6]*$dig[7]*$dig[8]*$dig[9]*$dig[10]*$dig[11]*$dig[12]

    If ($curMulti -gt $Multi13) { 
        $Multi13 = $curMulti
        For ([Int32]$d=0;$d -lt 13;$d++) {
            $digSalvo[$d] = $dig[$d]
        }
    }
}

Write-Host "Dígitos adjacentes com maior produto são:"
Write-Host $digSalvo[0] "x" $digSalvo[1] "x" $digSalvo[2] "x" $digSalvo[3] "x"`
           $digSalvo[4] "x" $digSalvo[5] "x" $digSalvo[6] "x" $digSalvo[7] "x"`
           $digSalvo[8] "x" $digSalvo[9] "x" $digSalvo[10] "x" $digSalvo[11] "x"`
           $digSalvo[12] "=" $Multi13

Os 13 dígitos adjacentes com maior produto são:
5 x 5 x 7 x 6 x 6 x 8 x 9 x 6 x 6 x 4 x 8 x 9 x 5 = 23514624000

Project Euler - 7

Nesse problema proposto em Project Euler, deseja-se descobrir qual é o 10001° número primo.

Uma possibilidade de implementação seria:

Function testPrimo([Int32]$n) {
    if (($n % 2) -eq 0) { return $false }
    [Int32]$c = 3
    while (($c * $c) -le $n) {
        if (($n % $c) -eq 0) { return $false } 
        else { $c +=2 }
    }
    return $true;
}

Function _Main([Int32]$indPrimo) {
    [Int32] $qtdePrimos = 1
    [Int32] $enesimoPrimo = 1
 
    while ($qtdePrimos -lt $indPrimo) {
        $enesimoPrimo += 2;
        if (testPrimo($enesimoPrimo)) {
            $qtdePrimos++;
        }
    }
    Write-Host "O $indPrimo° número primo é: $enesimoPrimo"
}

Clear-Host
_Main 10001

O 10001° número primo é: 104743

Project - Euler 4

O enunciado do problema de nº 4 pede que se encontre o maior palíndromo da multiplicação de 2 números de 3 dígitos.

O enfoque aqui será o de implementar a solução tendo por base o método de busca de palíndromos que utilizamos no post Invertendo String e Palíndromos. Também, utilizaremos o fato de que estamos a procura do maior palíndromo, logo faz mais sentido começarmos a busca pelos números mais altos, dividindo a busca em intervalos [999-900], [899-700], etc. Assim sendo, quando encontrarmos um palíndromo, certamente será o maior, pois estamos multiplicando números maiores do que os intervalos que se seguirão. A busca então pode ser interrompida, acelerando a resposta.

Function ehPalindromo($pal) {
    $reversePal = -join([System.Linq.Enumerable]::Reverse($pal))
    if ($pal -eq $reversePal) {
        Return $true
    }
    else {
        Return $false
    }
}

Function VerPalNoIntervalo([Int32]$int1, [Int32]$int2) {
    [Int32]$max = 0
    For ($i=$int1; $i -gt $int2; $i--) {
        For ($j=$int1; $j -gt $int2; $j--) {
            If (ehPalindromo ([String]($i*$j))) {
                If (($i * $j) -gt $max) {
                    $max = $i * $j
                    Write-Host "Palíndromo entre $i * $j = $max"
                    Return $max
                }
            }
        } ## for $j
    } ## for $i
    Return 0
}

Clear-Host
[Int32]$i=999
For ([Int32]$j=899; $j -gt 100; $j-=100) {
    $i = $j + 100
    If (VerPalNoIntervalo $i $j) {
        Write-Host "O maior palíndromo encontrado de 3 dígitos foi: $max"
        Break
    }
}

Na implementação, a função ehPalindromo retorna $true se o número em questão é palíndromo. A função VerPalNoIntervalo recebe um intervalo, por exemplo [999-900], e verifica se há um palíndromo nesse intervalo - a verificação é feita chamando a função ehPalindromo.
No corpo principal, foi construído um loop que chama a função VerPalNoIntervalo passando os intervalos de busca. Conforme dito, como a busca está sendo feita a partir dos números maiores, em bloco, ao ser encontrado um palíndromo é seguro deduzir que é o maior.

Palíndromo entre 993 * 913 = 906609
O maior palíndromo encontrado de 3 dígitos foi: 906609

Project Euler - 3

O problema 3 do Project Euler é sobre decompor um número em seus fatores primos.

Vamos demonstrar 2 soluções (o maior fator é 6857) com seus respectivos tempos de cálculo.

Function LargestPrimeFactor([Long]$Num) {
    Write-Host "Força Bruta"
    [Long]$sqrtNum = [math]::Sqrt($Num) 
    $maxFactor = 2
    $prime = 2
    Write-Host "Fatores Primos de $Num : " -NoNewline
    While ($Num -gt 1) {
        If (($Num % $prime) -eq 0) {
            $maxFactor = $prime
            $Num = $Num / $prime
            Write-Host "$prime," -NoNewline
        }
        Else {
            If ($prime -lt $sqrtNum) { $prime = getNextPrime($prime+1) }
        }
    }
    Return $maxFactor
}

Function getNextPrime([Long]$p) {
    [Int32]$sum = 0
    While ($sum -eq 0) {
        For([Long]$j=1; $j -le $p; $j++) {
            If($p % $j -eq 0) { $sum++ }
        }

        If ($sum -eq 2) { Return $p }
        Else { 
            $sum = 0 
            $p++
        }
    }
}

Function FastLargestPrimeFactor([Long]$Num) {
    Write-Host "Método Rápido"
    Write-Host "Fatores Primos de $Num : " -NoNewline
    [Long]$i = 2
    While (($i * $i) -lt $Num) {
        While (($Num % $i) -eq 0) { 
            Write-Host "$i," -NoNewline
            $Num = $Num / $i 
        }
        $i = $i + 1
    }
    Write-Host $Num -NoNewline
    Return $Num
}
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
$maxFactor = LargestPrimeFactor 600851475143
$time.Stop()
$ts = $time.Elapsed
Write-Host ""
Write-Host "O maior fator primo de 600851475143: $maxFactor"
Write-Host "Tempo de Cálculo - Força Bruta:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milissegundos"
Write-Host "----------------------------------------------------"
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
$maxFactor2 = FastLargestPrimeFactor 600851475143
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host ""
Write-Host "O maior fator primo de 600851475143: $maxFactor2"
Write-Host "Tempo de Cálculo - Método Rápido:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milissegundos"

Força Bruta
Fatores Primos de 600851475143 : 71,839,1471,6857,
O maior fator primo de 600851475143: 6857
Tempo de Cálculo - Força Bruta:
7 segundos e 79 milissegundos
----------------------------------------------------
Método Rápido
Fatores Primos de 600851475143 : 71,839,1471,6857
O maior fator primo de 600851475143: 6857
Tempo de Cálculo - Método Rápido:
0 segundos e 29 milissegundos

Project Euler 2

Implementaremos 2 soluções para o problema de nº 2 do Project Euler:

Estamos implementando uma solução através do uso de recursividade (RecursiveFibonacciEvenSum) e outra utilizando um loop (FibonacciEvenSum).

Function RecursiveFibonacciEvenSum([Long]$pre, [Long]$cur, [Long]$evenSum) {
    If ($cur -gt 4000000) { Return $evenSum}
    If ($cur %2 -eq 0) { $evenSum = $evenSum + $cur }
    [Long]$tmp = $pre + $cur
    $pre = $cur
    $cur = $tmp
    RecursiveFibonacciEvenSum $pre $cur $evenSum
}
 
Function FibonacciEvenSum([Long]$pre, [Long]$cur) {
    [Long]$tmp = 0
    [Long]$evenSum = 0
 
    While($tmp -lt 4000000) {
        $tmp = $pre + $cur
        If ($tmp % 2 -eq 0) { $evenSum = $evenSum + $tmp }
        $pre = $cur
        $cur = $tmp
    }
    Return $evenSum
}
 
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
RecursiveFibonacciEvenSum 1 1 0
$time.Stop()
$ts = $time.Elapsed
Write-Host "Tempo calculado com Recursividade:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milisegundos"
 
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
FibonacciEvenSum 1 1
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host "Tempo calculado com Loop:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milisegundos"

Calculamos a soma dos números pares na Série de Fibonacci, obtendo 4613732 como resultado. Com relação ao tempo gasto, observamos que a implementação através de loop teve melhor desempenho do que a solução que utiliza recursividade.

4613732
Tempo calculado com Recursividade:
0 segundos e 157 milisegundos

4613732
Tempo calculado com Loop:
0 segundos e 28 milisegundos

Project Euler 1

Aqui vamos implementar duas soluções possíveis, em Powershell (Sum35v1 e Sum35v2), para o problema 1 de Project Euler, que diz o seguinte:

###### Força Bruta
Function Sum35v1([Int32]$N) {
    [Int32]$S3 = 3
    [Int32]$S5 = 5
    [Int32]$S15 = 15

    For ([int32]$i=2; $i -lt $N; $i++) {
        If ((3 * $i) -lt $N) { 
            ## Múltiplos de 3
            $S3 = $S3 + (3 * $i)
        }
        If ((5 * $i) -lt $N) {
            ## Múltiplos de 5
            $S5 = $S5 + (5 * $i)
        }
        If (($N -gt 15) -And ((15 * $i) -lt $N)) {
            ## Múltiplos de 3 e 5
            $S15 = $S15 + (15 * $i)
        }
    }
    
    ## Resultado é a soma dos
    ## múltiplos de 3 e 5 menos
    ## a soma dos múltiplos de 15
    Return ($S3+$S5-$S15)
}

##### Progressão Aritmética
Function Sum35v2([Int32] $N){
    ## A soma de todos os números de 1 a N
    ## pode ser calculado através da fórmula
    ## ( N * (N + 1) ) / 2
    ##
    ## A soma dos múltiplos de 3 até N 
    ## é calculada com 3*(1+2+3+4+...N/3)
    ## N/3=333, assim a soma de 1 até 333
    ## é (333*(333+1))/2
    ## logo a soma dos múltiplos de 3 é:
    [Int32]$S3 = 3*(333*334/2)

    ## A soma dos múltiplos de 5 até N 
    ## é calculada analogamente
    [Int32]$S5 = 5*(199*200/2)

    ## A soma dos múltiplos de 15 até N 
    ## é calculada analogamente
    [Int32]$S15 = 15*(66*67/2)

    Return ($S3+$S5-$S15)
}

Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
Sum35v1(1000)
$time.Stop()
$ts = $time.Elapsed
Write-Host "Tempo calculado com Força Bruta:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milisegundos" 

$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
Sum35v2(1000)
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host "Tempo calculado com Progressão Aritmética:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milisegundos" 

A soma dos múltiplos de 3 e 5 até 1000 é 233168.

Usando Força Bruta [Sum35v1], o tempo gasto foi:

233168
Tempo calculado com Força Bruta
0 segundos e 35 milisegundos

Usando Progressão Aritmética [Sum35v2], o tempo gasto foi:

233168
Tempo calculado com Progressão Aritmética
0 segundos e 10 milisegundos