Tentando concluir o Projeto Euler # 5, passa todas as verificações de sintaxe mas não funciona

Question

tentando concluir o Projeto Euler # 5 . O código que eu tenho deveria logicamente funcionar, e ele passa o ShellCheck, mas não fornece saída por algum motivo. O código está abaixo. Obrigado e desculpe se isso deve estar em um site de troca de pilha diferente

#!/bin/bash
 i=1
 while [[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 && $((i % 5)) -eq 0 && $((i % 7)) -eq 0 && $((i % 11)) -eq 0 && $((i % 13)) -eq 0 && $((i % 17)) -eq 0 && $((i  % 19)) -eq 0 ]]
 do
     i=$((i+1))
 done
 echo $i

    

Answer 1

Sim, você deve fazer o teste [[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 ... ... ]] .
Ele testará se um número $i é divisível por todos os números na lista, ao mesmo tempo .
Mas o que você está fazendo se o número coincidir com esse teste?
Imprima porque achou o número?

Não, você está incrementando, o que você precisa é reverter a ação, em outras palavras:

Increment $i if the test fails.

Faça o seguinte:

while ! [[ … . … ]]; do

Ou:

until [[ … . … ]]; do

Fazer isso levará uma quantidade enorme de tempo para encontrar 9699690 (o número que você procura com seu código, que também não é a resposta correta).

A maneira correta de encontrá-lo está à frente, continue lendo.

Somente primos?

No entanto, por que você não está incluindo, por exemplo, 4 ou 6 ou 9, etc ...

Porque eles não são primos? Deixe-me esclarecer com um exemplo da ideia.
O número 9699690 é divisível por todos os primos (2 3 5 7 9 11 13 17 19) em seu teste, mas não é divisível por 4 .

O código que você escreveu falha. E leva muito tempo para encontrar a resposta por força bruta (experimentando cada um dos inteiros até encontrar o correto, especialmente no shell, que é uma das línguas mais lentas que existem).

L.C.M.

Mas o problema poderia ser mais fácil se descrevêssemos isso dizendo:

find the LCM of the list {1..20}.

Esse é o L leste C que omite M ultiplas de vários números. O LCM é: LCM(a,b) = (a*b) / gcd(a,b) (uma equação matemática).

G.C.D.

Onde gcd id o G reatest C ommon D ivisor.

E Euclides (cerca de 2300 anos atrás) descreveu o primeiro. O algoritmo de Euclides , é um método eficiente para calcular o maior divisor comum (GCD) de dois números

Página do algoritmo de Euclides
Algoritmo de Euclides no código shell Unix
Múltiplo menos comum: um quebra-cabeça

A implementação em shells modernas como uma função é bastante simples:

gcd() {   # Calculate $1 % $2 until $2 becomes zero.
          until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
          echo "$1"
      }

E o código lcm também é simples:

lcm() {   echo "$(( $1 / $(gcd "$1" "$2") * $2 ))";   }

O que é necessário é repetir todos os argumentos até que apenas um permaneça:

while  [ $# -gt 1 ]
do
       t="$(lcm "$1" "$2")"
       shift 2
       set -- "$t" "$@"
done
echo "$1"

Chamar todo o programa com os números que você usou indica o número que usei acima:

$ ./script 2 3 5 7 11 13 17 19
9699690

Você pode chamar o script como:

$ ./script {2..20}

Para obter a resposta final.

    

Answer 2

Tem que ser resolvido com bash como marcado?

Em caso afirmativo, vamos usar o mecanismo aqui String :

$ bc <<< '9*8*7*5'
2520
$ bc <<< '19*18*17*13*11*8*7*5'
232792560

O objetivo é multiplicar os números maiores não divisíveis pelos números anteriores. Por exemplo, no primeiro caso, temos 9*8*7* ... (e não há 6 porque 9 é divisível por 3 e 8 é divisível por 2, então 8 * 9 é certamente divisível por 6) ... *5 . Obviamente, 4,3 e 2 também são divisíveis por 8,9 e 8.

Depois de pensar, percebi que provavelmente uma abordagem mais geral para sequência com qualquer tamanho é multiplicar todos os números primos e, no caso de não primo, apenas uma parte restante, então

2*3*2*5*1*7*2*3*1*11*1*13*1*1*2*17*1*19

Colocamos 2 no lugar do número 4 porque o segundo 2 já está lá, um truque similar foi usado no caso dos números 8 e 16. O número 6 é coberto por 2 * 3 então colocamos 1, da mesma forma para números 10,12, 14,15,18. Finalmente, 9 é substituído por 3. Obviamente, tudo isso pode ser simplificado por 19*18*17*13*11*8*7*5 , conforme observado anteriormente.