1

What would the math equation be for finding the lowest number divisible by 1 to A? I know factorial can make numbers divisible by 1 to A but that dosn't give me the lowest number.

Example of what I'm talking about:

the lowest number divisible by 1,2,3,4,5,6,7,8 = 840

Example of factorial (What I'm not talking about):

8! = 40,320

Note:

A is anything that's more then 1 and is whole.

Binary Freak
  • 107
  • It is called the least common multiple. It is approximately $e^A$ in size, that is a version of the Prime Number Theorem. – Will Jagy Mar 13 '14 at 23:25
  • I would emphasize that the function, call it $f(A),$ can be calculated on computer by iterating $f(A) = \operatorname{lcm} (A, f(A-1)).$ – Will Jagy Mar 13 '14 at 23:31

3 Answers3

2

The problem with taking the factorial is that it repeats prime powers too many times: For example, $8!$ contains $6$ powers of $2$, while $8$ is only divisble by $2^3$.

You're looking for the number that's divisible by all the primes at most $A$, and powers of primes that are still less than $A$; to this end, let $P_A = \{p_1, p_2,\dots p_n\}$ be the collection of primes in $\{1, \dots, A\}$. Then for primes $p$,

$$p^k \le A \iff k \le \frac{\log A}{\log p}$$

Thus, the desired number is

$$\operatorname{lcm}(1,2,\dots,A) = \prod_{k = 1}^n p_k^{\lfloor\log A / \log p_k\rfloor}$$ where $\lfloor \cdot \rfloor$ denotes the floor function.

As an example, for $A = 8$, we have $P_A = \{2,3,5,7\}$. Then the exponent for $2$ is $$\left\lfloor \frac{\log 8}{\log 2} \right\rfloor = 3$$ as expected. Similarly, the exponent for $3$ is $\lfloor \log 8 / \log 3\rfloor = 1$, and likewise for $5$ and $7$. Thus the desired number is

$$2^3 \cdot 3 \cdot 5 \cdot 7 = 840$$

  • Would the downvoter mind explaining? If there's a correction or improvement suggested, I'd be happy to hear it. –  Mar 13 '14 at 23:33
  • 1
    seems Ross got a downvote at the same time. I have seen this before, someone downvoting everything to do with a single question, the software does not see it as a suspicious pattern as there are relatively few posts involved. – Will Jagy Mar 13 '14 at 23:35
  • 1
    @WillJagy And so did mlo105, it seems. Oh, well. –  Mar 13 '14 at 23:36
  • I just checked, one needs to open a question to downvote it. So, if we have a malicious individual rather than a bot, opening a question offers the chance to downvote every answer. Like popping bubble wrap. – Will Jagy Mar 13 '14 at 23:41
1

You can write it as $LCM(1,2,3,4,\dots A)$ To figure it out, you take the highest power of each prime less than $A$ and multiply them. For $A=37$, we have $2^5,3^3,5^2$ and all other primes less than $37$, so it is $2^5\cdot 3^3\cdot 5^2\cdot 7 \cdot 11 \dots \cdot 37$ They are given in OEIS A003418

Ross Millikan
  • 374,822
  • 1
    For this user, I would emphasize that his function, call it $f(A),$ can be calculated on computer by iterating $f(A) = \operatorname{lcm} (A, f(A-1)).$ – Will Jagy Mar 13 '14 at 23:28
0

Look at the LCM. Note $lcm\{a,b\} = \frac{ab}{gcd(a, b)}$.

If you have a prime $p$ and a power of $p$, $p^{n}$, you will simply discard $p$ and keep $p^{n}$ instead. As $p^{n}|x \implies p|x$, but the converse is not true.

Note as well you can ignore $1$ in your $gcd$ calculations.

ml0105
  • 14,674
  • For completeness's sake, the method for finding the GCD is Euclid's algorithm. – Nick Mar 13 '14 at 23:26
  • The Euclidean algorithm is pretty straight-forward. The Binary GCD algorithm is also a good alternative. – ml0105 Mar 13 '14 at 23:30