0

I'm solving this for a programming challenge, in fact I already solved it but I'd like to know if there's some kind of rule that could improve such thing?

For example if I needed the numbers divisible by 2,4 and 8, they are all multiples of 2, so I don't need to test each of them.

But, for 1 to 20, is this possible?

juliano.net
  • 321
  • 3
  • 14
  • 4
    Look up "least common multiple". – Robert Israel Apr 14 '15 at 21:13
  • 2
    $2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19$. – Rob Arthan Apr 14 '15 at 21:25
  • The rule that @RobArthan has presumably used is $$\operatorname{LCM}(1,...,20)=\prod_{p\leq 20}p^{\lfloor\log_p 20\rfloor}$$ where $p$ are primes noting that $k=\lfloor\log_p n\rfloor$ is the maximal power of a given prime $p$ such that $p^k\leq n$. – String Apr 14 '15 at 21:29
  • You're right. The least common multiple does solve the problem. – juliano.net Apr 14 '15 at 21:30
  • From a programming perspective, $k=\lfloor \log_x y\rfloor$ can easily be found by simply starting from $k=0$ and running a while loop that terminates whenever $x^{k+1}>y$. – String Apr 14 '15 at 21:31

1 Answers1

1

The smallest (nonnegative) number that is evenly divisible by a given list of integers $a_1, \dots, a_n$ is called the least common multiple of $a_1, \dots , a_n$. So you could be looking for the least common multiple of $1, 2, \dots, 20$. With this keyword you will find varied information.

A common multiple is always given by the product $a_1 \times \dots \times a_n$, but it might not be the least common multiple as in your example(s).

In your case this would be $1\times 2 \times \dots \times 20$ also denoted $20!$, called "$20$ factorial."

quid
  • 42,135