# There is a number divisible by all integers from 1 to 200, except for two consecutive numbers. What are the two?

To reiterate the question, basically there is some number, $$n$$ that exists that is divisible all the integers $$1, \dots, 200$$, except for two consecutive numbers in that range. The goal is to find what those two consecutive integers are. The answer isn't trivial though, since $$n$$ needs to be divisible by all those numbers, it is difficult to find two numbers next to each other such the multiples of those numbers aren't less than $$200$$ and such that those cannot be prime factorized into numbers that are in the prime factorization of $$n$$.

I have tried doing this computationally, but the LCM of all the numbers in the range (less two of them) is ginormous and checking the divisibility condition doesn't seem to work on my computer. The problem would be simple if the two numbers didn't have to be consecutive, since we could just select two prime numbers, but since one must be even, this is not possible.

I am trying to think of properties of divisibility that could help, but haven't found anything that worked yet. For example, I was looking for numbers that a prime such that a number before or after it is the square of a prime number. This way, we could say that the prime number itself is omitted from $$n$$ and that there is only one factor of the square root of the other number in $$n$$. I am not sure if that would definitely work, but regardless I couldn't find those numbers. I tried another perfect square and a prime number, $$196$$ and $$197$$, but there must be enough factors to make two $$14$$s in $$n$$, so that doesn't work either.

I am not experienced at all in number theory or discrete math, this is just a brainteaser I have heard. (Also for reference, I do not know the answer to reverse engineer something from). Any help would be appreciated!

Thanks!

• @J. W. Tanner Because $4$ and $49$ should both divide $n$. – paw88789 Nov 14 '19 at 23:55
• 127 and 128 work as one is prime and no other number from 1 to 200 divides by $2^7$ – Conrad Nov 14 '19 at 23:55
• $1327927515090260884407345538562367745796828278681721394601759928808007945120777126248000$ – paw88789 Nov 15 '19 at 0:04
• $609236484862644336153546507488522923077606\equiv 108 \bmod 127$ is equivalent via the method I used on the 78 digit number. – user645636 Nov 18 '19 at 13:36
• This was a question asked a month ago on The Riddler, the puzzle column on FiveThirtyEight with the same answer as in the above answers. – Xi'an Nov 20 '19 at 8:32

Excellent question! The answer is $$127$$ and $$128$$... but why? If you wanted to find a number divisible by $$1,2,3,4$$ you might first multiply these numbers and say $$24$$. However, you soon realize $$4$$ is already a multiple of $$2$$; you can use just $$3\times4$$ to get $$12$$. Therefore, you need only multiply the largest powers of the primes that factor all of the digits from $$2$$ to $$200$$ to get a number that is divisible by all of the integers from $$1$$ to $$200$$.

If you do this; you will find the number is $$2^7\cdot3^4\cdot5^3\cdot7^2\cdot11^2\cdot13^2\cdot17\cdot19\cdot23\cdot29\cdot\ldots$$(the rest of the primes up to $$199$$) = a very large number.

Next we need to find a restriction to eliminate two consecutive numbers. One of the two numbers must be even. The only way to remove an even number from the above calculation without modifying any of the other primes is to reduce the power of $$2^7$$ to $$2^6$$; this removes the number $$128$$ from the list. Since $$127$$ is also a prime number, it can also be removed from the list without affecting any of the other primes in the list...

I hope this helps.

• Thanks for your answer. It's helping me think of a systematic approach. Can you clarify what you mean by removing an even number without modifying any of the other primes in the list? – Slade Nov 15 '19 at 1:43
• I'll have a try. Even though I understand the concept it is hard to put into words. The even number that you remove must not contain any factors that are also prime numbers. Doing so would remove any multiples of those factors within the given range. – acevans Nov 15 '19 at 12:09
• @Slade - 2^7 is the ONLY even number in those prime-factors he multiplies - so to take off an even number ( and one of them has to be even .. ) you can only access this even 2^7 ... – eagle275 Nov 15 '19 at 12:11
• Good comments; to clarify what I was thinking when I said to remove an even number without affecting the other primes. We know our number is divisible by 100; suppose we wanted to remove it. 100 is 2^2*5^2... and we have 7 powers of 2 and 3 powers of 5 in our calculation. To remove 100 we would have to reduce our powers of 2 by 5 or reduce our powers of 5 by 2. However, making either change will remove a lot of other integers too. Suppose we decide to change the powers of 5 from 3 to 1. Now we can't divide by 100 or 25,50,75,... – slbtab Nov 15 '19 at 13:22
• @acevans: Not quite right. It can contain odd prime factors that already occur elsewhere. – user21820 Nov 16 '19 at 16:11

Hint: Think about how many factors of $$2$$ the number will have and find a prime nearby.

Thought process (likely partially reversed order):

• $$m<200<2m\implies m>100$$
• if $$m$$ doesn't divide by a higher prime power than other numbers, for at least one prime, then its factorization, can be made up for by other numbers.
• 243 is the next power of 3 after 81, that's too large (and that happens for all other powers for larger primes), and 162 fails at escaping 81.
• largest power of 2, in the range of a factorization is $$2^7=128$$, which is too large for other primes (including another 2) to be added.
• $$129=3×43\implies (127,128)$$

Edit

• If $$m=p^x\cdot q^y$$ then its factorization, can be made up for by the product of a number that has $$p^x$$ in its factorization, and another that has $$q^y$$ in its factorization. It follows that, if at least one of $$x,y$$ aren't unique to $$m$$, then $$m$$ is a divisor of $$n$$
• Thanks for the answer. Can you make your second bullet point a bit clearer, there may be some grammar issue that is making it hard for me to understand – Slade Nov 15 '19 at 1:14

Since you specifically mentioned trying to solve this problem computationally, I hope it's okay to post some Python code even though we're not on StackOverflow.

As long as you're working with standard unbounded integers, Python shouldn't have any problem calculating lcm for large numbers or checking divisibility. It wouldn't work with floats (e.g. 1.3279275150902608e+87) or numpy fixed-size integers.

from functools import reduce
from math import gcd

def lcm(x, y):
return x * y // gcd(x, y)

N = 200
for i in range(1, N+1):
# Testing i and i + 1
all_except_two = list(range(1, i)) + list(range(i + 2, N + 1))
lcm_all_except_two = reduce(lcm, all_except_two)
divisible_by_i = (lcm_all_except_two % i == 0)
divisible_by_i_plus_one = (lcm_all_except_two % (i + 1) == 0)
if not divisible_by_i and not divisible_by_i_plus_one:
print(f"{lcm_all_except_two}\nisn't divisible by either {i} or {i+1}.")


It outputs:

1327927515090260884407345538562367745796828278681721394601759928808007945120777126248000 isn't divisible by either 127 or 128.

in a few milliseconds. It also works for N=500.

• Thanks for an awesome answer. My code was nearly the exact same (used a numpy array instead of lists) but was having some problems with overflow on the numbers. I'll check it out again to see what went wrong – Slade Nov 15 '19 at 12:04
• @Slade Numpy uses fixed-size integers, not python 3 unbounded integers, so that's most likely what went wrong... – Maxim Nov 15 '19 at 14:18
• At least it was only a few msec.; I would be sorry to hear of much time spent computing a problem that can be pretty well analysed without much calculation. (But fair enough; the questioner did mention it.) – PJTraill Nov 28 '19 at 17:03
• @PJTraill: Ahah, you're right. Let's say it's a good starting point in order to test more elegant solutions. – Eric Duminil Nov 28 '19 at 18:38

First of all, one of those consecutive numbers must be a prime number. Because;

1. The divisibility of an arbitrary number to a prime number is not affected by its divisibility to numbers smaller than that prime number.
2. But, that prime number should be chosen in such a way that it must be greater than $$200$$ when multiplied by $$2$$. Let $$p$$ be a prime number in the $$[1,200]$$ closed interval. We can state that: $$0 \equiv n\pmod {2p} \space \Rightarrow \space 0 \equiv n\pmod p$$ $$2p \gt 200 \space \Rightarrow \space p \gt 100$$

Although this reasoning is valid, it is not enough for us to assign the value of the second integer. Let us take a look at the maximum possible number of a prime factor making up the integer $$n$$. For example, the number of $$2$$ as a factor in $$n$$ is $$7$$ at most. This boils down to the fact that the number of 2 as a prime factor in each divisor except for 128 in the [1,200] closed interval is 6 at most. If we exclude $$128$$ as one of the divisors of $$n$$, this does not affect the divisibility of $$n$$ to other integers in the $$[1,200]$$ closed interval. When the same thought process is applied to other prime factors making up the integer $$n$$, we see that predefined conditions do not meet. Therefore, one of the consecutive numbers is $$128$$.

Now, look at the numbers $$127, 128$$, and $$129$$. Among them $$128$$ is the one assigned but what is the other one? We have two options: $$127$$ and $$129$$. Since one of the consecutive numbers must be prime, we can easily deduce that the other one is $$127$$. So, $$127$$ and $$128$$ are the integers that do not divide $$n$$. Hope it helps!

One of the two consecutive numbers is even lets call it $$m$$ if $$m\neq 128$$ then both $$m/2$$ and $$128$$ divide the number hence $$lcm(m/2,128)$$ divides the number and $$m$$ divides $$lcm(m/2,128)$$ so by transitivity $$m$$ divides the number; contradiction so $$m=128$$ and you're left with two choices for the other one.

• one actually as 129 is composite factoring into other numbers. – user645636 Nov 15 '19 at 2:38