4 Relaxing Number Theory Problems.

Today we take a look at 4 relaxing number Theory problems I found over on Brilliant :) Featuring factorial, a Diophantine equation and a sneaky little identity. Enjoy! =D Video sponsored by Brilliant btw :)

Help me create more free content! =)

--------------------------------------------------------------------------------
Wanna send me some stuff? lel:

Postfach 11 15
06731 Bitterfeld-Wolfen
Saxony-Anhalt
Germany
--------------------------------------------------------------------------------

0:00 Intro
1:35 Solution 1
8:50 Solution 2
12:37 Solution 3
15:26 Solution 4

[PapaFlammy]

*_Hey you, thanks for watching :v Make sure to check out Brilliant for way more amazing Maths Content!
Otehr than that, here are all of today's relevant links

[jackhandma]

First problem is basically how real men do polynomial division.

[FahmiNoorFiqri]

I'm listening to this video when writing code, very relaxing

[xerostat]

21 min video : short video
Shorts : doesn't exist
(Btw it's really relaxing)

[thevastuniverse]

Oh god, I don't know why I have this feeling but it just made me smile, wait...every video of yours makes me smile :) and it is offcourse relaxing.

[Partynumbers]

In the first exercise you also need to check that the n you find actually is prime in the other factor, which is the case here but does not need to in general. Or am wrong?

[MichaelRothwell]

The polynomial division in the first problem can be done very easily using synthetic division (aka Ruffini's rule).

[hopelessdove]

In the first problem, wouldn't you have to check that n=2, 3, 4 do indeed yield prime numbers?

[Charles_Reid]

Me on the second problem:

n = 28

Father Flame on the same problem:

✨ n Ξ 28 ✨

[tregi]

for the second problem you could use the following to count the number of factors of 2 and 3:
every multiple of 2 adds 1 factor of 2 => count how many multiples of 2 we have up to n => floor(n/2)
every multiple of 4 adds 1 additional factor of 2 => count how many multiples of 4 we have up to n => floor(n/4)
every multiple of 8 adds 1 additional factor of 2 => count how many multiples of 8 we have up to n => floor(n/8)
....
so the total number of factors of 2 would be:


same can be applied to 3:


I dont think this is faster for this problem, than manually counting, but I think its neat :)

Edit: the third problem can also use this, with powers of 5 in the denominators

[eduardomalacarne]

Thank you Papa Flammy for this relaxing video

[D.Axtmann]

Such relax, much relief. Work goes brrrr

[lecombattant]

For the second problem, you don't have to brute force it that much, you can be a bit more efficient. Given a number N, the sum of 2s factors between 1 and N is going to be :

SUM i in (from 2, 2^2, 2^3, ..., 2^k) N // i
Where k is the biggest integer such that 2^k <= N

For example, if N = 40, k = 5 because 2^5 <= 40 and 2^6 > 40
Then you will have 40 // 2 + 40 // 4 + 40 // 8 + 40 // 16 + 40 //32 = 20 + 10 + 5 + 2 + 1 = 38 (which is correct).

You can apply this method to any (prime? not sure if required) base, of course, so the same method works for 3, 5, 7 ...

So you could have tried different N until you found the smallest one, which is a bit faster than counting everything by yourself. With good heuristics, it's rather quick.

Still a great video!

[RCSmiths]

There is always something to learn from these! Cheers!

[skylardeslypere]

My favourite way to divide polynomials by other polynomials is basically just doing it like this:

We want to divide n³-8n²+20n-13 by n-1 so we can write it as
(n³-n²) + (-7n² + 7n) + (13n - 13).
The way to find it is: the first term of each parenthesis is added to cover up anything that's "different" from our original polynomial. The second term is added to ensure we can factor n-1 out of each parenthesis.

[sohammanna]

Hey Jens.
I will suggest you to bring a series on combinatorics also.

[theodom]

For the first 5 minutes of the first problem I was just yelling Horner at my screen xd... it’s cool how you find shortcuts though.

[krasimirronkov]

For the first problem dont you have to check if the second factor is a prime number after finding the number N?

[VaradMahashabde]

If you want to know about the prime powers in a factorial, a convinient formula is the following
power of p in factorization of n! = sum_{i = 1}{till the terms are all 0} ( floor(n / p^i) ) = floor( n / p ) + floor( n / p^2 ) + floor( n / p^3 ) + floor( n / p ^4) + ...
Eventually, the terms go to 0 as p^i surpasses n.
This works because the first term counts the number of multiples of p multiplied into n!, and the single power of p they contribute. The second term counts all the extra powers of p contributed by the multiples of p^2, which had their first power counted in the previous term as a multiple of p. And so and so forth.

A neat thing to notice is that floor( n / p^(k+1 ) = floor( floor( n / p^k ) / p). This can be seen by considering the integer and fractional parts of n / p^k.
This means that you don't need to keep track of the entire decimal expansion, and need to only remember one value during the calculation (2 if you are also adding mentally)
For example, when considering the power of 2 in 100!, :
100/2 = 50 → 25 → 12 → 6 → 3 → 1 → 0 (and 0 forever from now)
Adding the results up, we get (50 + 25 + 12 + 6 + 3 + 1 + 0 + 0 + ...) = 97

[TheGatewayProductions]

Fantastic video! Relaxation is the key to feeling better.