Need to clarify this code
The code outputs the number of pairs (i, j) that satisfy the condition
(2^j-1) % (2^i-1) == 0
Where
1<=i<j<=n
n - user number under which the number (i, j) pairs should be found. The code works fine, but the logic behind this code is difficult to understand.
PS: t is a variable that will allow the user to enter numbers more than once at a time.
#include<stdio.h>
#include<math.h>
int main()
{
int t;
long n,sum,ans;
scanf("%d",&t);
while(t--)
{
scanf("%ld",&n);
int nrt=(int)sqrt(n);
sum=0;
for(int i=1;i<=nrt;i++)
{
sum+=n/i;
}
ans=2*sum-nrt*nrt-n;
printf("%ld\n",ans);
}
return 0;
}
source to share
Let's take a brute force approach to a problem and print the results *:
############################# 2^^1 -1 == 1
-#-#-#-#-#-#-#-#-#-#-#-#-#-# 2^^2 -1 == 3
--#--#--#--#--#--#--#--#--# 2^^3 -1 == 7
---#---#---#---#---#---#-- 2^^4 -1 == 15
----#----#----#----#----# 2^^5 -1 == 31
-----#-----#-----#-----# 2^^6 -1 == 63
------#------#------#-- 2^^7 -1 == 127
-------#-------#------ 2^^8 -1 == 255
--------#--------#--- 2^^9 -1 == 511
---------#---------# 2^^10 -1 == 1023
----------#-------- 2^^11 -1 == 2047
-----------#------ 2^^12 -1 == 4095
------------#---- 2^^13 -1 == 8191
-------------#-- 2^^14 -1 == 16383
--------------# 2^^15 -1 == 32767
-------------- 2^^16 -1 == 65535
------------- 2^^17 -1 == 131071
... ...
The symbolic label indicates when your condition is met. A good picture emerges: each of your numbers is divisible by 1, each other is divisible by 3, every third is divisible by 7, etc. Each i
-th number is divisible by 2^^i - 1
. **
With this understanding, we can program your function as:
int f(int n)
{
int sum = 0;
int i;
for (i = 1; i <= n; i++) sum += (n - i) / i;
return sum;
}
We can replace (n - i) / i
with n / i - 1
and move the total subtracted character -1
into the return value:
int g(int n)
{
int sum = 0;
int i;
for (i = 1; i <= n; i++) sum += n / i;
return sum - n;
}
Now let's look at the amount β(1, n: n / i)
. For example:
β(i = 1, 9: 9 / i) = 9 + 4 + 3 + 2 + 1 + 1 + 1 + 1 + 1
We can get the same amount by looking at it from right to left and calculating how often each term occurs:
β(i = 1, 9: 9 / i) = 5*1 + 1*2 + 1*3 + 1*4 + 1*9
We can easily get this view:
β(i = 1, n: n / i) = β(1, n: i * (n / i - n / (i + 1))
This is really another way to write the amount; you can see that by grouping the terms differently so that they have the same denominator:
β(i = 1, N: i * (n / i - n / (i + 1)) = n + β(i = 1, n: ((i + 1) - i) * n / (i + 1)) = n + β(i = 1, n: n / (i + 1)) - (N + 1) * (n / (N + 1)) = n + β(i = 2, n + 1: n / i) - c = β(i = 1, n: n / i) - c
The supplementary term c = (N + 1) * (n / (N + 1))
is a correction term since only half of the term is used for i = n + 1
. When summed over the entire range, it n / (n + 1)
is zero and disappears. It does not disappear when only part of the array is summed, as we will see later.
If we divide the sum for the head and tail by s = sqrt(n)
, we get:
β(i = 1, n: n / i) = β(i = 1, s: n / i) + β(s + 1, n: n / i)
Let's depict the head in the original style and the tail in the "counting terms" method, for example:
β(i = 1, 9: 9 / i) = (9 + 4 + 3) + (5*1 + 1*2)
For anyone n
:
β(i = 1, n: n / i) = β(i = 1, s: n / i) + β(1, s - 1: i * (n / i - n / (i + 1)) = β(i = 1, s: n / i) + β(1, s: n / i) - s * (n / s)
All divisions are whole divisions (and therefore there must be parentheses sometimes) and n / s == s
, therefore:
β(1, n: n / i) = β(i = 1, s: n / i) + β(i = 1, s: n / i) - s * (n / s) = 2 * β(i = 1, s: n / i) - sΒ²
And this gives your original function:
int h(int n)
{
int nrt = sqrt(n);
int sum = 0;
int i;
for(i = 1; i <= nrt; i++) sum += n/i;
return 2 * sum - nrt * nrt - n;
}
where β(1, n: n / i)
in g
above has been replaced by 2 * β(i = 1, s: n / i) - sΒ²
.
*) I stole the D power operator ^^
here so as not to confuse the old C-buffs, which are taken ^
at the nominal value, i.e. like xor.
**) I don't know why the picture shows. There is probably a good explanation, but at the moment I trust my pattern matching skills. Blindly. Edit @ nevets answer has an explanation for this pattern.
source to share
This is a very interesting problem. If you have tried some small inputs, you will get a basic understanding of the code.
I used very simple code to generate all valid when pairs n = 10
, and this is what I got:
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 4
2 6
2 8
2 10
3 6
3 9
4 8
5 10
Surprise? Here we can see a very clear pattern: when i, j
satisfies j = k * i
, where k
- an integer, and j = k * i < n
, i, j
- the actual vapor. It has absolutely nothing to do with the original equation, it only depends on n
.
In fact, it is not surprising to (2^(nk) - 1) = ((2^k)^n - 1) = (a^n - 1)
where a = 2^k
, so we can apply the rule of factorization , which allows (a^n - 1) = (a - 1)(a^(n - 1) + a^(n - 2) + .. + 1)
and, therefore, can be factored (a - 1)
, ie (2^(nk) - 1) % (2^k - 1) == 0
...
The problem now is how to read this number efficiently. By hypothesis, we have j > i
. We know earlier j = k * i
. Therefore, it k
must be in the range [2, n / i]
. For each, i
we have a complete (n / i) - 2 + 1 = (n / i) - 1
valid choice for k
. Hence, there will be full valid pairs sigma((n / i) - 1, 1 <= i <= n)
.
How to convert the equation to the code you provided see @MOehm's answer.
source to share