DP in NT

Revision en3, by stoyan_malinin, 2020-10-16 22:00:22

In this blog I am going to present you a very interesting concept or a technique, I don't know exactly what it is, because I cannot remember where I learned it from.

The thing that makes it so special for me is its simplicity, because it usually doesn't require a lot of thinking or deep knowledge in number theory or mathematics as general.

As you may have guessed by the title of this article it uses dynamic programming to solve problems related to number theory. More specifically, it in my opinion is very appropriate for problems that require us to find the the number of pairs that satisfy some divisibility condition (usually gcd or something like this). Most of the problems presented in this article will probably have a solution using Möbius inversion or some combinatorial approach (usually the inclusion-exclusion principle). If you want to study more about Möbius inversion you can check this.

The technique is really simple and is based on roughly speaking overcounting and compensating for it. I will start explaining with a very popular example. Find the number of coprime pairs of integers from $$$1$$$ to $$$n$$$. This, as I mentioned earlier, can be done using Möbius inversion or inclusion-exclusion principle, but I won't talk about it in this blog. However, there are some similarities between the solutions that I will present and the ones using the other techniques, so check them out if you are not familiar with them. So without anything further to do, let's begin with the solution. Initially we will begin by getting a rough estimate for the actual values. What I mean by that, for example if two numbers have a greatest common divisor $$$d$$$, both of them should be at least divisible by $$$d$$$. So we can say that all pairs of numbers that have gcd $$$d$$$ will be contained in the set of pairs of numbers, where both of the numbers are divisible by $$$d$$$. More specifically the amount of these pairs is $$$\frac{\lfloor n/d \rfloor(\lfloor n/d \rfloor-1)}{2}$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en12 English stoyan_malinin 2021-09-08 21:36:05 377 Tiny change: 'echnique, I don't k' -> 'echnique, that I don't k' (published)
en11 English stoyan_malinin 2021-09-08 21:16:53 909 Tiny change: 'perfect $d-power$. For exam' -> 'perfect $d$-power. For exam'
en10 English stoyan_malinin 2021-09-08 16:28:58 300
en9 English stoyan_malinin 2021-09-08 16:23:18 19
en8 English stoyan_malinin 2020-10-30 23:41:54 1090 Tiny change: 'nExample 2\nProblem: Y' -> 'nExample 2Problem: Y'
en7 English stoyan_malinin 2020-10-30 20:45:59 213 Tiny change: '] = \frac{cntDiv[d](cntDiv[d]-1)}{2}$.\n\n' -> '] = \frac{1}{2}$.\n\n'
en6 English stoyan_malinin 2020-10-28 09:29:28 421 Tiny change: 'd] = /fract{cntDiv[d]' -> 'd] = /frac{cntDiv[d]'
en5 English stoyan_malinin 2020-10-17 00:57:00 12 Tiny change: 'ample $dp[\frac{n}{2}]$ is equa' -> 'ample $dp[n/2]$ is equa'
en4 English stoyan_malinin 2020-10-16 23:08:08 2309 Tiny change: '$ where $k>=1$.\n\n\n\' -> '$ where $k\geq1$.\n\n\n\'
en3 English stoyan_malinin 2020-10-16 22:00:22 1062 Tiny change: 's from $$1$$ to $$n$$. \n' -> 's from $$1 to n$$. \n'
en2 English stoyan_malinin 2020-10-16 21:20:26 795
en1 English stoyan_malinin 2020-10-16 21:09:07 173 Initial revision (saved to drafts)