a nice divisibility problem

[@GreenMeansGOF]

1:46 Bless you.

[@Jeff_Saunders]

And that's a good place to sneeze.

[@임한준-d7v]

I think the condition for the Chinese Remainder Theorem should be changed to pairwise coprime. There's no solution for x=1mod2, x=2mod4, x=2mod3

[@rainerzufall42]

Yes, I immediately cringed when I saw gcd() = 1...

[@MichaelRothwell1]

​@rainerzufall42Me too!

[@tsunningwah3471]

Problem suggestion: Given a cubic equation with blank coefficients: x^3+()x^2+()x+()=0 For each turn, Player A will provide a real number, and Player B will fill it into any one of the remaining (). After 3 turns, all () are filled and a cubic equation with coefficient is formed. If the equation has 3 distinct integer roots, A wins. If it doesn't, B wins. Question: Does a must-win strategy exist for A/B?

[@PULLABHATLAMEDHA]

I think yes. Correct real numbers and correct placing in 3 attempts may exist

[@hyperboloidofonesheet1036]

Something about Vieta's formulas and the cubic discriminant pop into mind. I think B has the advantage, but I'm not ready to write a paper on it.

[@maxhagenauer24]

Cant player B just think of all the possibilities of integer roots he can have with the number and place it in the right spot to be most likely to not give distinct integer roots and place them in the spot that is most likely?

[@fahrenheit2101]

Whoa, that's cool! Clearly A needs to provide integers - A's hypothetical winning strategy would obviously require numbers such that the eqn is factorable as (x - a)(x - b)(x - c) for some integers a, b, c distinct. The numbers being chosen are the negative sum, the product in pairs, and the negative product of the 3 integer roots. B wants to force a permutation of these that won't work, A wants to find integers that will work no matter what B does (well, the choice of those integers can depend on B's choices, of course) The question only asks if a strategy exists for either A or B. I reckon Zermelo's theorem maybe clears that up, since there's no possibility for a draw. Intuitively it also seems obvious that if one player lacks a winning strategy, it's because the other player has one. But since that's "obvious", one should probably also find the strategy, and the advantaged player. If there are 3 integers which when permuted in any order will always yield a cubic factorable as above, then A has an easy strategy by simply picking those 3. This seems... tricky to guarantee. I'd bet on this being impossible. I feel like B has the upper hand. It just feels like no matter what A chooses, B being able to freely choose the position of the coefficient means A needs some real special choice of first number, such that wherever it's put, they have some special choice of second number, such that wherever it's put, they have some 3rd number that gives a factorable cubic. That's what a winning strategy for A looks like, and it seems hard to guarantee. Whereas for B, all we need is to pick positions that screw things up. But yeah, I've got nothing as for how to proceed. I can't even tell how tricky of a problem this is, which scares me from giving it a real try. Edit: I believe a winning strategy for A would need 10 special numbers in total, having drawn a tree diagram. 1 initial choice, 3 subsequent choices conditional on B's choice, then for each of those, 2 subsequent choices i.e. 6 more. So 1 + 3 + 6 = 10 numbers that fill out a decision tree for A's strategy. I know this is probably obvious, but I'm pretty new to anything involving game theory.

[@jellymath]

I think player B aims to put the integers such that the function has an turning point zero and otherwisA wins. Sounds like A has an advantage

[@ELS737]

The numbers from 9,440 to 9,460 also fit, right?

[@MarsupialPower]

Yep! If you swap what divides (x-1) and (x+1) in the system of congruences, you get 9450=210x45. Then 9449=11x859 and 9451=13x727.

[@timstorer978]

Yup. 9440 to 9460 fits. I Think the mistakes were for one, to start with the middle number x BEING divisible by lots of things, and two looking for symmetry. Start with x NOT being divisible by any of these things, and only look in one one direction to keep it simple. In each dividers case, you hoping to squeeze in as MANY dividable numbers into the range as possible, not as FEW. As far as FINDING the range that fits... I still say he's got mad skills! (I cheated and wrote a loop to test for it in python.)

[@fahrenheit2101]

@@timstorer978 Nobody was looking for as few as possible, it's just convenient pedagogically to have x being divisible by the first few. The game of efficiency isn't needed, and takes a little longer. But is still interesting, and perhaps worth trying. But it'll only be sizeably better if you can remove the need for one of the congruences altogether. Otherwise I think you're just relying on luck?

[@pwmiles56]

Quite right. I worked this out by swapping the conditions for p=11 and p=13, i.e. 11 divides x-1 and 13 divides x+1, where x=9450.

[@johnnypoker46]

Because 9,450 + 20,580 = 30,030, which is 2 x 3 x 5 x 7 x 11 x 13

[@Utesfan100]

22 is not possible. Consider an interval of 22 integers. 11 are even. At most 4 are odd and divisable by 3. At most 3 are odd and divisable by 5, but if there are 3 one must be divisible by 3, so 2 not divisible by 2 or 3. At most 2 are odd and divisible by 7. At most 1 are odd and divisible by 11 or 13. Thus any interval of 22 integers can have at most 11+4+2+2+1+1=21 numbers divisible by a prime 13 or less.

[@MichaelRothwell1]

Nice!

[@jay_sensz]

One-liner in Java: IntStream.iterate(10, x->x+1).filter(x -> IntStream.rangeClosed(x-10, x+10).allMatch(k -> IntStream.of(2,3,5,7,11,13).anyMatch(p -> k%p == 0))).limit(1).forEach(System.out::println);

[@icew0lf98]

if we can find a number N so that 2*3*5*7*N-1 is divisible by one from {11,13} and 2*3*5*7*N+1 by the other from {11,13}, then this number is the middle member of such 21 long sequence, this can be easily explained if we take a string of 21 boxes with a 1by1 increasing sequence of numbers as their label and declare the middle one to be 2*3*5*7*N, we fill in all the boxes divisible by 2 or 3 or 5 or 7 and the only ones left would be the two right next to the middle box.

[@icew0lf98]

the next step we can take is look for such N where the predecessor of 2*3*5*7*N is divisible by 11 and successor by 13, by noticing that 2*3*5*7*N-12 is divisible by 11*13 2*3*5*7*N=11*13*K+12, K is divisible by 2 and 3 but not by 5 and 7 so let's divide both sides by 6 5*7*N=11*13*k+2, where k=K/6 and if we check for all k in {0,1,...,34} we are guaranteed to find an example because this equation mod 35 looks like 11*13*k+2=0 and because k is not divisible by 5 nor 7, we will hit a different remainder for each k in {0,1,...,34}

[@Utesfan100]

This proof generalizes nicely to show than an interval of integers of length 2p_n-1 exists where each number in the interval is divisible by a prime at most p_3, where p_n is the nth prime.

[@shohamsen8986]

There is a possibility i misunderstood the question cause i didnt agree with the x needing to be divisible by 3*5*7*2 to be a requirement, since consecutive 21 nos, will have numbers in their list divisible by 2,3,5,7 (pigeon hole principle). Anyway my answer is : 2,3,4,....,21,22. This is 21 consecutive nos which satisfy this condition.

[@surem8319]

17 and 19 are divisible by a number less than 17? News to me

[@shohamsen8986]

@@surem8319 ahh yes, you are right. Thats where i made the mistake. Thanks.

[@frenchguy7518]

17 and 19 are on your list and, being prime themselves, aren't divisible by any of 2, 3, 5, 7, 11 or 13. It's not enough that the list contains multiples of the given primes, every single number in the list must be divisible by at least one of the given primes, which is a different (and much stronger) constraint. On the other hand, there could be other ways to choose the remainders that result in smaller numbers (the question is proving that a list exists, not finding the smallest possible one). I just checked that choosing x-1 to be divisible by 11 and x+1 by 13 (instead of the reverse as in the video) gives x=9450, giving us numbers from 9440 to 9460. Skipping multiples of 2 and 5, we have: 9441, 9447, 9453 and 9459 are divisible by 3; 9443 and 9457 are divisible by 7; 9449 is divisible by 11; and 9451 is divible by 13.

[@shohamsen8986]

@@frenchguy7518 "the question is proving that a list exists, not finding the smallest possible one)." Good point. His method, makes sense now. thanks.

[@fahrenheit2101]

All the numbers! Not just some of them. The pigeonhole principle is far too weak to guarantee what we're after.

[@eulerization995]

You don't need to handwave the proof that x-10 is positive. Given a set of congruences mod n1, n2, n3,...ni, with all n pairwise coprime, we can construct the homogeneous solution n1*n2*n3*...ni. Adding this doesn't change our congruences so we can always get our smallest x-k above 0.

[@xinpingdonohoe3978]

Starting at the first place, I filled in every second one with 2. Then at the third, I filled them in with 3. I then added 5s and 7s so as to cover the gaps, and that just left two places. 2,3,2,7,2,5,2,3,2,x,2,y,2,3,2,5,2,7,2,3,2 Observe the middle 2, between x and y, is a multiple of 2, 3, 5 and 7, so 210. From there, I saw that 210=2 mod 13 and 210=1 mod 11. We need 210n to be one of ±1 mod 13, and the other of ±1 mod 11. It's already 1 mod 11, so I'll use that as the basis. Multiply by 10, 12, 21, 23, etc. since they're all -1, 1, -1, 1, etc. mod 11, then check if 2× those numbers is 1, -1, 1, -1, etc. mod 13. After searching a few, I found that n=45 works, meaning 210×45=1 mod 11 and 210×45=-1 mod 13, so x=11 and y=13. It's not pretty, but brute force sometimes just works in number theory. The centre is 210×45=9450, so the 21 numbers are 9440 to 9460.

[@MichaelRothwell1]

Here is a solution based on the proof of the Chinese Remainder Theorem. We'll solve these congruences (I've swapped 11 & 13 as compared to the video): x≡0 (mod 210) x≡1 (mod 11) x≡-1 (mod 13) The CRT guarantees a solution as the moduli 210, 11, 13 are pairwise coprime. From the 1st congruence x=210a, for some a∈ℤ In the 2nd congruence 210a≡1 (mod 11) As 19×11=209, we have 210≡1 (mod 11), so a≡1 (mod 11) a=11b+1, for some b∈ℤ x=210(11b+1) In the 3rd congruence 210(11b+1)≡-1 (mod 13) As 16×13=208, we have 210≡2 (mod 13), so 2(11b+1)≡-1 (mod 13) 2(11b+1)≡12 (mod 13) 11b+1≡6 (mod 13) 11b≡5 (mod 13) The existence of a solution is guaranteed by the fact that as 11 and 13 are coprime, there exists c∈ℤ such that 11c≡1 (mod 13), this last result being guaranteed by Bézout's identity. If we multiply this by 5, we'll then have 11(5c)≡5 (mod 13). Specifically, as 6×13=78=7×11+1, i.e. 7×11≡-1 (mod 13), multiplying our previous line by 7 we get: 77b≡35 (mod 13) -b≡-4 (mod 13) b≡4 (mod 13) For smallest solution of this kind, take b=4 a=11b+1=45 x=210a=45×210=9450

[@miraj2264]

I'm not familiar with the proof of CRT, so maybe my method is using it without realizing it, but what I did: We need to find some value x that satisfies the 3 mod conditions. Assume x = 210. x = 0 mod(210), x-1 = 209 = 0 mod(11), but sadly x+1 = 211 = 3 mod(13) so 210 doesn't work. However, we know that the answer has to be a multiple of 210. So let's see what happens as we add 210n for some natural number n. x+210n = 0 mod(210), x-1+210n = n mod(11), x+1+210n = 3+2n mod(13). From this, we see that n has to be multiplied by 11*210 = 2,310 so that we don't break the second mod condition from already working. From this, we have x+2310n = 3 + 9n mod(13). Just plugging in, we see n = 4 makes this 0 mod(13). So an answer to this question is x = 210+4*2310 = 9,450.

[@MichaelRothwell1]

@@miraj2264 Please see my comment for a method using the proof of the CRT. I guess your method is pretty close.

[@koenth2359]

My reasoning: Every range of 21 consecutive numbers contains 9 numbers that are either divisible by 3 or by 7 (one by both, 7+3-1=9), so 12 remain undivisible by 3 or 7 Of these 12, 6 are even and 6 are odd (by symmetry) so 6 remain by undivisible by 2, 3 or 7 Of 21 consecutive numbers, at most 3 are divisible by 5 but not by 2, so at least 3 remain undivisible by 2, 3, 5 or 7 Of 21 consecutive numbers, at most 1 is divisible by 11 but not by 2, so at least 2 remain undivisible by 2, 3, 5, 7 or 11 Of 21 consecutive numbers, at most 1 is divisible by 13 but not by 2, so at least 1 remains undivisible by 2, 3, 5, 7, 11 or 13 Therefore, no.

[@stewartcopeland4950]

Python: L1 = [2,3,5,7,11,13] L2 = [ ] x = 2 while len(L2)< 21: c = 0 for i in L1: if x%i == 0: c += 1 if c != 0: L2.append(x) else: L2 = [ ] x += 1 print(L2)

[@OrbitTheSun]

ChatGPT did the job for me, starting with a screenshot of the board.

[@raditzan]

On the more general problem. Is there a characterization of all positive integer pairs (m,n) such that there exist m consecutive positive integers that are divisible by all primes less than n?

[@blue2003fordwindstar]

your videos always make me feel like im in my math lectures again. good stuff, thank u

[@jcfgykjtdk]

9450 is smaller

[@fahrenheit2101]

Very neat. This is roughly what I was thinking, but the symmetrical approach makes things convenient and easy to see.

[@holyshit922]

1=1*210 - 19*11 x = 1*210*10 - 19*11*0 x = 2100 mod 2310 x = 1 mod 13 1 = 3*2310 -533*13 x = (3*2310 *1 - 533*13*2100)mod 30030

[@yonatanrosmarin4135]

It is the smallest sequence of numbers satisfying the puzzle with the additional conditions? But is it the smallest sequence of numbers that satisfy it in general?

[@fahrenheit2101]

Well, nobody was asking for the smallest. It indeed is not the smallest, many have found others, like x = 9450

[@59de44955ebd]

So what's wrong with x = 9450?

[@talastra]

It had a rough childhood.

[@MyOneFiftiethOfADollar]

We all have trouble with this, but you did not sufficiently motivate why symmetry is important. This means it is likely you read a proof that exploited symmetry for this problem type.

[@JalebJay]

A similar problem has been on the putnam: Can you create a list of 10 consecutive numbers where every element shares a factor with at least one other element in the list?

[@Coach-Jay-Math]

isn't it that one of any consecutive n numbers is divisible by n?

[@f5673-t1h]

Solution: Draw 7 rows of 21 squares in MS Paint. Each of the six primes gets a row (final one blank for now), where you color the leftmost square in its row, then also every pth square in that row. Take the first 6 rows and place them on the blank row (with transparency selection) such that all the blank squares are covered, by shifting the placed rows to the right if necessary. 2 row not shifted (covers 11). 3 row shifted by 1 (covers 4 more). 5 not shifted (covers 2 more). 7 row shifted by 3 (2 more). 2 blanks and 2 primes left, do it however, all 21 squares covered. Could've used the Chiense Remainder Theorem explicitly, but implicitly is more fun.

[@shruggzdastr8-facedclown]

Hm, I always thought that the Chinese Remainder Theorem was related to why we always feel hungry again half an hour after eating Chinese food 😏

[@jackthisout9480]

I wonder why not choose x-1 to be divisible by 11, as that would automatically make x+1 divisible by 13.

[@januszkobayashi1361]

It wouldn't, 33 is divisible by 11 but 35 is not divisible by 13

[@talastra]

Since I'm not math fast, it would have been helpful to have it explicitly stated why x+1 and x-1 must be divisible by different primes.

[@MyOneFiftiethOfADollar]

Become math fast then.

[@talastra]

@@MyOneFiftiethOfADollar Ah, the math version of "git gud." So, you're offering free tutorials then? I'm not sure I'm sold on your crediibility :(

[@jimthompson5910]

A great question. If x is even then x-1 and x+1 are odd. Assume there does exist a prime p that is a factor of both odd integers x-1 and x+1 at the same time. That would mean there are integers k and m such that pk = x-1 and pm = x+1. Then (x+1)-(x-1) = pm-pk Simplify both sides a bit to end up with 2 = p*(m-k). At this point it should be clear that p = 2 is the only possibility for p. This leads x-1 and x+1 both being even, but this is a contradiction. This proves there isn't a prime that is a factor of odd integers x-1 and x+1 simultaneously. Of course if x is odd then x-1 and x+1 are even, and p = 2 is a factor of both of them.

[@talastra]

@@jimthompson5910 This is more thorough than I was imagining, of course. And thanks for it. I was just realizing that, whatever x is, x - 1 and x + 1 can't both be divisible by 11 or 13.

[@Kyoz]

🤍

[@wolframhuttermann7519]

I check this with a computer program. I verify if the difference between two consecutive odd numbers from 17 to 15013 which are coprime to 15015 is bigger than 22 or not. And there is no such pair of such numbers. That is very easy.

[@hazalouldi7130]

the GOD ALLAH Sobhanah bless you

[@the_multus]

It seems like you've just magicked the solution into existence without any specific way to reach it. Too many leaps. I don't really like that style.

[@paulgillespie542]

True. He definitely found an example satisfying the conditions, which was all that was needed for this question though.

[@fahrenheit2101]

It's not magic, though. It's rigorous, there are no actual holes or leaps. The only thing missing is the explicit computation, which any sane mathematician wouldn't bother with if not asked to do so. The question is whether such a set of 21 consecutive integers exists, and he proved it does somewhat non-constructively, and with minimal effort. And there IS a specific way to reach it, since there is a specific computation that he mentioned but didn't show as regards the chinese remainder theorem. But there's no need to actually do so, since said theorem posits the existence of the solution anyways. You could also specifically reach a solution by simply writing some code to do it. It would be much faster, and explicitly shows you an answer. But it's not very interesting, even though it technically doesn't suffer those complaints. Also, what style would you prefer? Things don't usually get very computational in number theory, especially when it can be avoided.

[@pwmiles56]

@@fahrenheit2101 >>The only thing missing is the explicit computation, which any sane mathematician wouldn't bother with if not asked to do so

[@Roescoe]

I agree. I was missing the explanation for why x-1 should be divisible by 13 and x+1 by 11, until 6:55 All the other logic directly followed out of picking a good x.

[@Roescoe]

From other comments working it out, it appears that choice was arbitrary and pretty much relied on "well we have left over primes in this questions so we have to use them somehow"

[@christianimboden1058]

1:15-2:00 Penn demonstrates the value of an ellipsis without writing an ellipsis.

[@PleegWat]

X=420 is also a solution, much earlier in the number line.

[@pwmiles56]

419 and 421 are both primes

[@jay_sensz]

No it's not. The first interval that matches is 9440...9460.

[@PleegWat]

No it isn't. I'm not sure what I was on last night.