Projeto Euler – Problema #1 em J

O problema 1 do Projeto Euler quer saber a soma de todos os números múltiplos de 3 e de 5 em um dado conjunto de números naturais. Quase todas as linguagens possuem alguma função para saber o resto de uma divisão. Um número será múltiplo de outro se o resto da divisão for zero. 5 / 3 = 1 e sobra 2, portanto, 5 não é múltiplo de 3. Já 6 / 2 = 2 e resta 0. Consequentemente, 6 é múltiplo de 3.

Para um conjunto de números naturais anterior a 10 (só pode ser 9), os múltiplos de 3 são 3, 6 e 9 e o único múltiplo de 5 é o próprio 5. A resposta para o problema então é: 3+5+6+9=23.

J possui o verbo Residue ‘|’ que retorna o resto de uma divisão. Então 3 | 5 = 2 (lembre-se da avaliação da direita para a esquerda) 3 | 6 = 0. Para saber os múltiplos de 3 do exemplo (naturais anteriores a 10) podemos escrever:

3 | >:i.10-1 => 1 2 0 1 2 0 1 2 0

Você lembra no primeiro artigo a diferença entre 1+i.10 e i.10+1. Optei pela construção i.10-1 apenas por facilidade de leitura no contexto. Poderia perfeitamente adotar i.9 sem alteração do resultado.

1 2 3 4 5 6 7 8 9

1 2 0 1 2 0 1 2 0

Acima podemos ver a relação dos múltiplos de 3 e o resto zero fornecido pela sentença. Para os múltiplos de 5, basta trocar o 3 pelo 5 na sentença anterior. Apenas o 5º elemento é divisível por 5.

5 | >:i.10-1 => 1 2 3 4 0 1 2 3 4

Tá, e daí? Como saber quais são os números e o somatório deles?

Bem, teremos que descobrir um meio de relacionar os valores zero obtidos com o vetor de números naturais e efetuar a soma. Para a façanha utilizaremos o verbo Copy # . Basicamente x # y ira repetir x o argumento correspondente de y. 2 3 # 1 2 => 1 1 2 2 2. Por analogia, se colocarmos uns e zeros na esquerda, teremos como resultado alguns números repetidos uma vez (sem repetição né?) e outros números ausentes (correspondentes aos zeros).

Já podemos definir que teremos que trocar os zeros por um (correspondentes ao resultado da divisão que indica ser o número primo) e os outros valores deverão ter zero pois não são primos. Na página do Equal temos que, x=y retorna 1 se os números forem iguais ou zero caso contrário. alteramos a nossa sentença para:

0 = 3 | >:i.10-1 => 0 0 1 0 0 1 0 0 1

poderemos testar para verificar o resultado:

0 0 1 0 0 1 0 0 1 # 1 2 3 4 5 6 7 8 9 => 3 6 9

Seria um pouco de redundância efetuarmos a mesma operação acima para os múltiplos de 3 e 5. O ideal seria juntar os dois vetores e ‘pegar’ os primos de uma só vez. Como são zeros e uns e o vetor possui o mesmo comprimento, podemos tratar o vetor como sendo bits e efetuar as operações lógicas para obter o resultado. A operação que faz o resultado é o Or ‘+.’ . Sei que todos sabem mas, a operação OR retorna 1 se um dos dois ou os dois bits forem um. Só retorna zero se os dois bits forem zero. Assim sendo, pegaremos todos os números primos de 3 e 5 independente se for de um ou de ambos (15 por exemplo).

1 0 1 0 +. 1 1 0 0 => 1 1 1 0

Para o somatório, todos estão carecas de saber (quem acompanhou os outros artigos é claro) que usamos +/.

p1=. 3 : 0
a=.0 = 3 | >: i.y-1
b=.0 = 5 | >: i.y-1
+/ (a +. b) # >: i.y-1x
)

Para saber o resultado é só digitar:
P1 1000

Anúncios