Project Euler 16

O desafio no problema 16 de está relacionado a estouro de buffer, já que 2 elevado à potência 1000 gera um número muito grande.

Uma alternativa seria calcular as multiplicações tal e qual fazemos manualmente, armazenando os dígitos do resultado em um array. Assim, iremos efetuar 1000 multiplicações de cada resultado intermediário por 2. Ao final, teremos o número correspondente ao resultado de 2^1000 armazenado em um array, dígito a dígito, porém ele estará invertido.

Para o propósito do problema, não faz diferença ele estar invertido, já que estamos interessado na soma dos dígitos.

## Número de dígitos de 2^1000 pode ser calculado com
## Ndig = 1 + Log10(2^1000)
$tamanho_array = [Math]::Truncate(1 + 1000 * [Math]::Log10(2))
## Cria-se um array para armazenar os dígitos
$digito = New-Object int[] $tamanho_array

[int]$ordem = 0
$digito[0] = 1

## O número que será armazenado no array $digito
## será o resultado das multiplicações por 2 (1000 vezes)
## Cada digito é calculado separadamente, na forma
## como se faz a multiplicação manualmente
For ($i=0; $i -lt 1000; $i++) {
    [int]$pracima = 0
    For ($j = 0; $j -le $ordem; $j++) {
        $produto = 2 * $digito[$j] + $pracima
        $digito[$j] = $produto % 10
        If (($produto / 10) -lt 1) { $pracima = 0 }
        Else { $pracima = 1}
        If (($j -eq $ordem) -and ($pracima -gt 0)) {
            $ordem++
        }
    }
}

## Ao final o número armazenado no array $digito
## está invertido, mas para o propósito de
## somar os dígitos não importa
[int]$soma_digitos = 0

For ($i=0; $i -lt $digito.Length; $i++) {
    $soma_digitos += $digito[$i]
}

Write-Host "A soma dos dígitos de 2^1000 é:" $soma_digitos

A soma dos dígitos de 2^1000 é: 1366