0

trying to complete Project Euler #5. The code I have should logically work, and it passes ShellCheck, but gives no output for some reason. The code is below. Thanks and sorry if this should be in a different stack exchange site

#!/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
  • 1
    When I run your code it outputs 2, as it should. Your program doesn't attempt to answer the problem you reference. Hint 1: change all the && to ||. Hint 2: consider the number 30. Is it evenly divisible by 2,3,4, 5? – icarus Nov 23 '16 at 21:30
  • Hmm, I'm trying to make sense of the logic here. The question is asking for a number that is divisible by all the numbers 1-20. Therefore in the while loop, ALL of the conditions need to be met, no? As in, i % 2 needs to equal 0, i % 5 needs to equal 0, etc. 30 is divisible by those yes, but it would not be divisible by some of the other conditions in my code such as 7 or 11. Sorry if I'm not understanding but thank you for your response. – Egrodo Nov 24 '16 at 0:45
  • OK, let me try and explain. The while loop says "why something is true, do something". The "do something" is "move on to the next number". So the "something is true" part needs to be "at least one number doesn't divide". An "at least" almost always requires an or condition, as in "I have three children and at least one is a girl" means either the oldest is a girl or the middle one is a girl or the youngest is a girl. Before the question was edited you had $((i%2)) -ne 0 && $((i%3)) -ne 0 ... which says i is not divisible by 2 and not divisible by 3. – icarus Nov 24 '16 at 4:42
  • With many problems it can help to solve a simpler problem first. Here you were being asked to solve for the case n=20. I took a look at your approach, and suggested that you solve for the case n=5 in my second hint. Assuming I understand your approach, it will work for n=2 and n=3, but fail for n=4 and higher. In particular for n=5 I think your approach will give an answer of 30, but the correct answer is not that. – icarus Nov 24 '16 at 11:07
3

Yes, you should make the test [[ $((i % 2)) -eq 0 && $((i % 3)) -eq 0 ... ... ]].
It will test if a number $i is divisible by all numbers in the list, at the same time.
But what are you doing if the number match that test?
Print it because you found the number?

No, you are incrementing it, what you need is to reverse the action, in other words:

Increment $i if the test fails.

Either do:

while ! [[ … . … ]]; do

Or:

until [[ … . … ]]; do

Doing that will take an awful amount of time to find 9699690 (the number you seek with your code, which is also not the right answer).

The correct way to find it is ahead, keep reading.

Only primes?

However, why are you not including, for example, 4 or 6 or 9, etc ...

Because they are not primes? Let me clarify with an example of the idea.
The number 9699690 is divisible by all the primes (2 3 5 7 9 11 13 17 19) in your test, but is not divisible by 4.

The code you wrote fails. And it takes a very long time to find the answer by brute force (trying every one of the integers until the correct one is found, especially in the shell, which is one of the most slow languages there are).


L.C.M.

But the problem could be easier if we describe it by saying:

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

That is the Least Common Multiple of several numbers. The LCM is: LCM(a,b) = (a*b) / gcd(a,b) (a math equation).

G.C.D.

Where gcd id the Greatest Common Divisor.

And Euclid (about 2300 years ago) described the first one.
Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers

Euclid's algorithm page
Euclid's algorithm in Unix shell code
Least Common Multiple: A Puzzle

The implementation in modern shells as a function is quite simple:

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

And the lcm code is then also simple:

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

What is needed is to loop over all given arguments till only one remains:

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

Calling the whole program with the numbers you used gives the number I used above:

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

You may call the script as:

$ ./script {2..20}

To get the final answer.

  • Wow, not only did you explain what was wrong with my initial thinking in an easy to understand way, but you went and described the correct way of doing it with helpful links and key terms along the way. Not many people would do that on an d for a complete stranger. Thank you so much. I might not be naturally inclined to this stuff but people like you make me want to keep going. If I could give you a bounty I would. – Egrodo Nov 26 '16 at 23:55
  • @Egrodo Thanks for your very kind words. I'll keep trying to do my best. – sorontar Nov 27 '16 at 2:23
1

Has it to be solved with bash as tagged?

If so, lets use Here String mechanism:

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

The point is to multiply largest numbers not dividable by previous numbers. For example in first case we have 9*8*7*... (and there is not 6 because 9 is divisible by 3 and 8 is divisible by 2, so 8*9 is for sure divisible by 6) ...*5. Obviously 4,3 and 2 are also divisible by 8,9 and 8.


After some thought I realized that probably more general approach for sequence with any length is to multiply all prime numbers and in case of not prime only a remaining part, so

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

We put 2 in place of number 4 because second 2 is already there, similar trick was used in case of numbers 8 and 16. Number 6 is covered by 2*3 so we put 1, similarly for numbers 10,12,14,15,18. Finally 9 is replaced by 3. Obviously all this can be simplified by 19*18*17*13*11*8*7*5 as previously noted.

  • Yes but I'm sorry if I don't understand your answer. The question is, verbatim, "What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?". Therefore we have to find which single number can be divided evenly with ALL numbers 1-20. I don't understand how multiplication can be used here? – Egrodo Nov 24 '16 at 2:59
  • @Egrodo it would help to put that quote into your question so it's easy for everyone to find – roaima Nov 24 '16 at 7:41
  • @Egrodo This is exactly what this multiplication is doing. In the explanation I even gave you the general algorithm to find the smallest number divisible by all numbers from 1 to any given N. Your approach with the loop, even if corrected to make it working, would be unbelievably slow. – jimmij Nov 24 '16 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.