Very good, NxCy! Proving that the sum you found equals that is also part of the problem. Here's a hint that might help solving problems like this:
To solve the problem, all you need to do is to provide a sequence of numbers, say f(n). Notice that a summation expression is just one way of representing f(n). It might not be the only one. So, if you suspect two expressions are the same, you should instead shift your definition of f(n) so that the equivalence becomes obvious.
For example, in the theory of special functions, it often happens that a special function has many distinct integral or series representations, and it's not obvious why they're equal. One way out is to look at a differential equation they must satisfy, if you can prove they satisfy the same differential equation, it's guaranteed that they are equal.
So, in your case, if you could define f(n) inductively/recursively, would it be easier to prove their equivalence?
Incidentally, that's something I realized that made me solve math problems much better. Often in math, you only need the right definition of something to find a proof!
I'm thinking your hypothesis is false, but I just have a thought, and that's far from a proof. A rational number can be written as x/y. By allowing negative a1 etc., you get the 1/y part. But what about a number x/y where you need the same number p1, p2, or p3 to make both x and y?
In that case the numerator and denominator wouldn't be relatively prime and you could simplify the fraction.
Yeah, the sketch proof I was thinking of was precisely related to the most-simplified fraction consisting of relatively prime numbers, which by definition don't share any prime factors, and therefore the hypothesis should work.
NxCy is right that the current (as a fraction of the current through the battery) from a node with k-1 bits to a node with k bits is I(k-1,k) = 1/k * 1/(N choose k). In fact, these are the numbers in the Leibniz harmonic triangle, a triangle which is basically a reciprocal form of Pascal's triangle where the Nth row and kth entry from the left, which we denote L(N,k), is given by 1/k * 1/(N choose k).
Ex: For N=2, the values of the currents through each resistor are: 1/2 1/2. For N=3: 1/3 1/6 1/3. For N=4: 1/4 1/12 1/12 1/4. And so on.
For each N, the equivalent resistance is just the sum of the values in the Nth row. We need to prove that the sum of the Nth row can be written as what p4wn3r said above:
There are two facts about the Leibniz harmonic triangle which we need:
(1) L(N,k) = L(N+1,k)+L(N+1,k+1) (this is reverse of the property in Pascal's triangle)
(2) L(N,1) = L(N,N) = 1/N
These can be proven by using L(N,k) = 1/k * 1/(N choose k)
We also know that Rn as p4wn3r gave, has the following recursive formula:
R1=1
Rn=Rn-1/2 + 1/n
Let SN represent the sum of L(N,k) over all k. Then S1=1 and:
SN-1 = L(N-1,1) + L(N-1,2) + ... + L(N-1,N-1) = (L(N,1)+L(N,2)) + (L(N,2)+L(N,3)) + ... + (L(N,N-1),L(N,N)) = L(N,1) + 2L(N,2) + 2L(N,3) + ... + 2L(N,N-1) + L(N,N) = 2(SN - 1/N)
and so SN = SN-1/2 + 1/N, which is the exact same as the recursive formula for Rn. Therefore they are the same.
Joined: 11/21/2019
Posts: 247
Location: Washington
I'm writing this up kinda drunk so the explanation might ramble a bit. We can use Descartes' theorem to figure out the radius of the smallest circle. But to do that we need to figure out the size of the mid-sized circle. We can use triangles to figure that out because you can basically use them to figure out everything.
We set our coordinates origin to the middle of the diagram, where the two large circles are tangent. We know that circle C is tangent to circle A, which means that the segment AC is equal to the sum of the radii of A and C, or AC = rA + rC. Since C is tangent to P, then we can create the segment CB by adding rA to CP. Since AC and CB are of equal lengths, the triangle ABC is Isosceles and a segment from C to the midpoint of AB bisects the triangle, which would give us C.
Alright, let's figure shit out. We need the length of AB so that we can bisect it and get a perpendicular line. AB is defined by the points (0,-2) (5,0), and we want a parameterized line so we can can find the midpoint, so here we go:
Sweet, so now we need a line perpendicular to AB that passes through the point (2.5, -1). First, the point slope equation for our segment AB [(0,-2),(5,0)] is y=0.4x-2. For the perpendicular line:
Figure out where our perpendicular line intersects the x-axis:
So the center of C is (2.1,0), which means the radius of C is 0.9. Since we have our three tangent circles now, we can just apply Descartes' theorem. The curvature k of a circle is the inverse of its radius, where k is positive if the circle is externally tangent, which all of our circles are:
So if I didn't botch this too badly, the radius of the smallest circle is 0.225.
I got the same answer using Pythagoras a few times
Let A be the centre of the upper large circle, B be the centre of the left medium-sized circule, C be the centre of the let small circle and D be the centre of the rectangle (where the two large circles meet).
The radius of the big circle is obviously 8/4 = 2
Let R be the radius of the medium-sized circle. Using Pythagoras on triangle ABD gives
(R + 2)^2 = 4 + (3 - R)^2, which gives R = 9/10
Now let r be the radius of the small circle and use Pythagoras on triangle ACD. I get
(r + 2)^2 = 4 + (6/5 - r)^2
which gives r = 9/40
A classic.
Let X = (x1,x2,...,xn) be a sequence of distinct positive integers such that, for any integer y that divides some xi, y = xj for some j.
Let M denote the gcd matrix of X, that is, the element mij = gcd(xi,xj).
Prove that det(M) = phi(x1)*phi(x2)*...*phi(xn), where phi is Euler's totient function.
A classic.
Let X = (x1,x2,...,xn) be a sequence of distinct positive integers such that, for any integer y that divides some xi, y = xj for some j.
Let M denote the gcd matrix of X, that is, the element mij = gcd(xi,xj).
Prove that det(M) = phi(x1)*phi(x2)*...*phi(xn), where phi is Euler's totient function.
I was curious what you meant by "a classic" and eventually found out this paper basically describes (and solves) the problem you are giving: what is the determinant of a GCD matrix of an ordered distinct factor-closed set of positive integers? I assume this is what you were getting at, although it is difficult to come up with on your own and I wasn't able to solve it this way.
I solved it a different way though, using the Lindström–Gessel–Viennot lemma (henceforth referred as LGV), as follows:
Loosely, LGV is based on: If we have a directed graph with some nodes labelled A1, ... An, B1, ... Bn (not necessarily distinct), and we form an n×n matrix M where the (i,j) entry is the number of distinct paths from Ai to Bj, then the determinant of M is the same as the signed sum of "path systems" (sets of n paths, which collectively begin at A1, ... An and collectively end at B1, ... Bn; the sign being the sign of the permutation from [A1 ... An] to [B1 ... Bn] described by the paths). By cancellation of path systems whose paths intersect at nodes, we only need to consider the signed sum of all "non-intersecting path systems" in order to calculate det(M). LGV further generalizes so you can assign weights on each of the edges in the directed graph, instead of all edges being weight 1.
The primary use of LGV is to provide a way to enumerate the number of non-intersecting path systems just by evaluating a determinant. For example, the number of non-intersecting path systems on the lattice below (A1 must go to B1, A2 to B2 and A3 to B3) is given by the determinant of the matrix:
But LGV can also be used to show that certain combinatorial matrices have a particular determinant (usually 1), by constructing a directed graph for them which has very few non-intersecting path systems. For example, the n×n matrix with entries given by min(i,j) has a determinant of 1, based on the following directed graph (here n=4):
Note that each Ai goes to and each Bj comes from only a central node at the same level or lower; hence the min(i,j). Here there is only one non-intersecting path system: straight across from A1 to B1, A2 to B2, ... So the determinant of the matrix is 1.
I bring up the last example, because there is in fact a directed graph similar to the last one (with modified weights) that proves the determinant of the GCD matrix above, as follows:
Let {A1, ... , An} be nodes that represent the positive integers {x1, ... , xn}, and let {U1, ... , Un}, {V1, ..., Vn} and {B1, ..., Bn} be additional nodes that also represent {x1, ... , xn} in the same order. Without loss of generality, assume x1 ... xn are in increasing order (this is only for visualization similar to the above graph; the order does not change any of the results here). Define the directed edges and their weights as follows:
* Ai goes to each Uk whenever the value of Uk is a factor of the value of Ai. All edges are weight 1.
* Uk goes to Vk. The weight of the edge from Uk to Vk is phi(xk).
* Vk goes to each Bj whenever the value of Vk is a factor of the value of Bj. All edges are weight 1.
We want to show the (i,j) entry of the matrix is gcd(xi,xj). Note that there is a path from Ai to Uk to Vk to Bj, if and only if the value of Uk (and Vk) divides the GCD of the values of Ai and Bj. Because of the special weights on the edges from Uk to Vk, the total weight that marks the (i,j) entry is the sum of phi(k) over all factors k of gcd(xi,xj), which by a result in number theory is equal to gcd(xi,xj) itself. This confirms the (i,j) entry equals gcd(xi,xj), and so the matrix is M.
Then by LGV, det(M) is the signed sum of non-intersecting path systems. Based on the condition that {x1, ... , xn} are distinct and closed under factors, I argue that there is only one such path system. Because all proper factors of xi are among xk where 1≤k≤i-1, any non-intersecting path system starting from {A1, ..., An} must start as Ai → Ui for all i. A symmetric argument shows that the path system must end as Vi → Bi for all i. Finally Ui → Vi for all i (these are the only edges between {U1, ... , Un} and {V1, ..., Vn}).
So there is exactly one non-intersecting path system: Ai → Ui → Vi → Bi for all i. Thus det(M) is just the weight of this path system , which is the product of weights of all the edges: phi(x1)*phi(x2)*...*phi(xn), QED.
Edit: Changed gcd(i,j) to gcd(xi,xj), which is what I meant.
I was curious what you meant by "a classic" and eventually found out this paper basically describes (and solves) the problem you are giving: what is the determinant of a GCD matrix of an ordered distinct factor-closed set of positive integers? I assume this is what you were getting at, although it is difficult to come up with on your own and I wasn't able to solve it this way.
The paper you should be looking at is reference [4] on the paper you cited. The result goes all the way back to 1857. The proof presented in this 1857 paper is the one I intended. The result follows by doing Gaussian elimination on the matrix by choosing the lines carefully.
All right, here's how I think an elementary solution of this problem could be achieved without much trouble.
As Fractal noted, the sets satisfying the required property are called factor-closed sets. Notice that if X is a factor closed set, X without the largest element is also factor-closed. This is an important property which allows us to set up induction.
Consider an n x n matrix where the i-j entry is given by gcd(xi,xj). Assume WLOG that the numbers are in ascending order. If we can somehow replace the n-th line of the matrix with a sequence of 0's, followed by phi(xn) in the very last element, we are done.
Why? Because, by the previous property, the (n-1)x(n-1) matrix will also be factor closed. And assuming that the property holds for n-1, we will have proven det(n) = phi(x_n)*det(n-1), and the result follows by induction.
How do we replace this line? The key is the following formula for phi:
That means, to find phi, we multiply n by a factor of (1-1/p) for every prime p that divides n.
So, if we open up this formula, we can rewrite it as:
phi(n) = n - n/p1 -n/p2 + n/p1p2 + ... and so on.
That means, phi(n) is just the sum of all terms of type n/p1*p2*..., where the sign is given by the number of primes in the denominator.
phi(n) = n* prodp|n(1-1/p)
This suggests the following procedure. Replace the n-th line of the matrix by the sum of itself plus the lines corresponding to xn/p1p2..., with the corresponding sign. The n-th term of each of these lines is just gcd(xi,xn) = gcd(xn/p1p2...,xn) = xi.
From this, it follows that the n-th term of the n-th line is replaced by phi(n), and we just need to prove that all the other entries in the line are replaced by 0. This is the hardest part and we break it up in several cases:
(1), gcd(xi,xn) = 1. In here, we see that any gcd of the form gcd(xi,xn/p1p2...) should be 1. Therefore, terms like this are replaced by an even number of 1's half of them with positive sign, half with negative, so we have a total of 0
(2) xi | xn. Here, we separate the primes p dividing xn in two classes. There are primes q where xi does not divide any number of the form xn/q. And the primes of the form r, where xi does divide numbers of the form xn/r. There must be at least one prime of the form r, or else x_i = x_n.
Anyway, if we restrict our sum to lines where only primes of the form q are present we end up with xi*prod(1-1/q), similar to how phi appears in the last term. However, when we include lines corresponding to primes of the form r, since the gcd is not affected by their presence, we must compute a sum of even terms of the form xi*prod(1-1/q), but where half have positive sign, and half have negative, and so sum to zero.
(3) gcd(xi,xn) = d > 1. Notice that since our set is factor closed, there is an xj=d. Because of this, there's another line with gcd(xj,xn) = gcd(xi,xn), and of course, xj|xn. So, lines like this are identical to case (2), which we already proved sum to 0. So, these must sum to 0 either.
I like this problem, because, unlike most, the best way to solve is to actually open up the formula and understand what's going on with it!
This suggests the following procedure. Replace the n-th line of the matrix by the sum of itself plus the lines corresponding to xn/p1p2..., with the corresponding sign. The n-th term of each of these lines is just gcd(xi,xn) = gcd(xn/p1p2...,xn) = xi.
So I noticed that what you're doing is replacing gcd(xi,xn) (which I assume is the (i,n) entry) with:
sumd|xn μ(d)*gcd(xi,xn/d) (*)
where μ is the Möbius function, and you're trying to show (*) is phi(xn) when i=n and 0 otherwise.
Then we can just use Möbius inversion. If in general we fix b and we let g(n)=gcd(b,n), then the f(n) in the Möbius inversion formula is f(n) = phi(n) when n|b and f(n) = 0 otherwise. You can verify that indeed, g(n) = sumd|n f(d) ; nonzero terms only belong to the factors of gcd(b,n) and when you sum their phi function, you get gcd(b,n).
So by Möbius inversion, f(n) = sumd|n μ(d)*g(n/d) = sumd|n μ(d)*gcd(b,n/d). If b≤n, we get the last quantity is phi(n) if b=n, and 0 otherwise. So we replace b with xi and n with xn, and since xi≤xn for all i, this confirms (*) is phi(xn) when i=n and 0 otherwise, as desired.
From the Michael Penn youtube channel a problem apparently originally published in some math magazine in 1987, which has a nice solution:
Suppose b is an integer larger than 1. Evaluate the integral from 0 to infinity of
floor(log_b(floor(ceil(x)/x))) dx
The easiest way to approach this is from the inside out.
If x > 1, then by definition, floor(ceil(x)/x) < floor((x + 1)/x) = floor(1 + 1/x) = 1 (since 1/x < 1), and since ceil(x) >= x, it follows that floor(ceil(x)/x) = 1.
Otherwise, if 0 < x <= 1, floor(ceil(x)/x) = floor(1/x) = n, where n is such that 1/(n + 1) < x <= 1/n.
Now, for any integer b > 1, floor(logb(x)) = m, where m is such that bm <= x < bm + 1. Hence,
floor(logb(floor(ceil(x)/x))) = 0 if x > 1/b,
and for any integer k >= 1,
floor(logb(floor(ceil(x)/x))) = k if 1/bk + 1 < x <= 1/bk.
Now the integral S of this function between 0 and infinity becomes:
S = sum from k = 1 to infinity of (k * (1/bk - 1/bk + 1)),
S = sum of (k/bk - k/bk + 1).
This is a telescoping sum, since the term -k/bk + 1 will (mostly) cancel with the (k+1)/bk + 1 term of the next term in the sum, leaving
S = sum from k = 1 to infinity of 1/bk.
This is a geometric series of ratio 1/b (which converges since b > 1), and so the sum is equal to
S = (1/b)/(1 - 1/b) = 1/(b - 1).
Guys, I need your help.
How to divide a range of positive numbers (from 1 to 1000, for example) between several threads, so each one would be evenly loaded?
Each thread has to check each number of its range segment in a loop (from 2 to number/2) if it's a prime number. If so, than it adds it to a concurrent collection.
The easiest way to spread the load is to allocate several arrays (lists) and fill them sequentially in a for loop from start to finish. But unfortunately, I'm not allowed to do that. By any means, but without arrays or other containers.
Since processing if 2 is a prime number is much quicker than processing 997, I'm thinking about some division like:
Thread 1 takes sequence 1:500. Thread 2 takes 501:750 and so on, until thread 10 (20, 30, ...). I can't pick right proportions.
TASing is like making a film: only the best takes are shown in the final movie.
If you're trying to find all of the prime numbers in a range, a much faster way to do it instead of checking each number individually for primality is to use a sieve. You start with a list of all of the numbers, and then go removing every even number, then every multiple of 3, etc. The numbers that are left are the prime numbers. If you need more information, see here.
This method is a lot faster at finding all of the prime numbers in a certain range, which should remove the need for you to use multiple threads. The only issue is that you don't have access to an array, which makes it harder to use this method. You do mention that you use a "collection" for storing the final prime numbers, which you could use in the implementation of the sieve as well, but I would need more details if you need help with that.
If you're trying to find all of the prime numbers in a range, a much faster way to do it instead of checking each number individually for primality is to use a sieve. ...
Great stuff, but unfortunately I'm restricted with the conditions I described above.
TASing is like making a film: only the best takes are shown in the final movie.
Ah sure, so we can't change what the threads are doing? If not, could you allocate the numbers to the thread in a non-sequential way? For example, could you say thread 1 has all the even numbers while thread 2 has all the odd numbers (which obviously would not be balanced correctly, it's just for an example)?
Ah sure, so we can't change what the threads are doing? If not, could you allocate the numbers to the thread in a non-sequential way? For example, could you say thread 1 has all the even numbers while thread 2 has all the odd numbers (which obviously would not be balanced correctly, it's just for an example)?
I came up with the idea of assigning the end of the range to each of threads and then checking each 'end = end - total number of threads' number if it's prime. Now, the range division looks pretty simple. Thank you!
Language: java
int currentThread = 3; // this is a serial number of the thread (0..N)
int begin = 1;
int end = 30 - currentThread;
int totalThreads = 4;
for (int i = end; i >= begin; i-=totalThreads) { // i = i - totalThreads
System.out.println(i);
}
//27
//23
//19
//15
//11
//7
//3
TASing is like making a film: only the best takes are shown in the final movie.
That looks good, nice and simple!
There are some minor issues with the way you balance it currently though, which means that some of the threads will still finish a lot earlier than others. For example, in your code, the 0th and 2nd threads will both not have any prime numbers (except 0), since they're only checking even numbers. So you can just remove those threads, and have it run a lot faster (though you need to add 2 as a prime number in after).
The optimum way to split the threads (for small numbers of threads) is as follows:
1 2 [1]
2 6 [1, 5]
4 12 [1, 5, 7, 11]
6 18 [1, 5, 7, 11, 13, 17]
8 30 [1, 7, 11, 13, 17, 19, 23, 29]
12 42 [1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41]
The first column is the number of threads, the second column is the increment in the loop, and the last column is the starting offset (I used a starting value instead of an ending value like you do). So for example, if you're using 4 threads, the optimum way is to check all the numbers of the form 1 + 12*i, 5 + 12*i, 7 + 12*i and 11 + 12*i (each in a different thread). Some of the numbers in the first column are missing, and that's because it's actually faster to use a smaller number of threads in that case.
Anyways, this is all a lot more complicated to implement, especially for a variable number of threads, but if you need speed it would definitely help a lot (eg. for 4 threads it should run about 3 times faster). Good luck!
Proof: The left side contains terms with only Aij's, terms with only wkBij's, and mixed terms. The terms with only wkBij's have an overall factor of wnk = 1. The mixed terms cancel out, as they get a factor of wmk with m not a multiple of n.
HHS is correct, but I'll try to show more detail. Unfortunatly the notation gets pretty awful and I don't know how to write in LaTeX on here. Apologies in advance.
Anyway, the left hand side can be written as the
sum over k [ sum over permuations [ sgn(sigma) * product over i [ a_i,sigma(i) + w^k * b_i,sigma(i) ] ] ]
The sum over k can be brought inside to behind the product. For a given sigma, let's now look at
sum over k [ product over i [ a_i,sigma(i) + w^k * b_i,sigma(i) ] ] =
(a_1,sigma(1) + w^0 b_1,sigma(1))*...*(a_n,sigma(n) + w^0 b_n,sigma(n) ) +
(a_1,sigma(1) + w^1 b_1,sigma(1))*...*(a_n,sigma(n) + w^1 b_n,sigma(n) ) + ...
Expanding the brackets we can identify 3 types of terms.
1) products of only a's
These will be of the form a_1,sigma(1)*a_2,sigma(2)*...*a_n,sigma(n) and there are exactly n copeis of them.
2) products of only b's
These will be of the form w^k b_1,sigma(1)*...*w^k b_n,sigma(n) = w^(nk)*b_1,sigma(1)*...*b_n,sigma(n)
Again, there are exactly n of them and w^(nk) = 1 by definition of w.
3) Cross terms
These will be of the form
c_1,sigma(1)*c_2,sigma(2)*...*c_n,sigma(n)*w^(km)
Where c could be either a or b and m is equal to the number of b's chosen. Summing over k doesn't affect the form of the c factors and so we can identify a group of terms all involving the same c's, but with differnet powers of w. This can be factorised to
c_1,sigma(1)*c_2,sigma(2)*...*c_n,sigma(n)*[w^0 + w^m + w^(2m) + ... + w^((k-1)*m)]
However we know that the w sum is 0. (For example, these are the solutions to x^n - 1 = 0, which has no term with power n-1)
Therefore cross terms all cancel and we are left with.
n*(a_1,sigma(1)*...*a_n,sigma(n) + b_1,sigma(1)*...*b_n,sigma(n))
Putting back in sgn(sigma) and the sum over permutations gets us the final result.
We set our coordinates origin to the middle of the diagram, where the two large circles are tangent. We know that circle C is tangent to circle A, which means that the segment AC is equal to the sum of the radii of A and C, or AC = rA + rC. Since C is tangent to P, then we can create the segment CB by adding rA to CP. Since AC and CB are of equal lengths, the triangle ABC is Isosceles and a segment from C to the midpoint of AB bisects the triangle, which would give us C.
Alright, let's figure shit out. We need the length of AB so that we can bisect it and get a perpendicular line. AB is defined by the points (0,-2) (5,0), and we want a parameterized line so we can can find the midpoint, so here we go:
But LGV can also be used to show that certain combinatorial matrices have a particular determinant (usually 1), by constructing a directed graph for them which has very few non-intersecting path systems. For example, the n×n matrix with entries given by min(i,j) has a determinant of 1, based on the following directed graph (here n=4):
Note that each Ai goes to and each Bj comes from only a central node at the same level or lower; hence the min(i,j). Here there is only one non-intersecting path system: straight across from A1 to B1, A2 to B2, ... So the determinant of the matrix is 1.
I bring up the last example, because there is in fact a directed graph similar to the last one (with modified weights) that proves the determinant of the GCD matrix above, as follows:
Let {A1, ... , An} be nodes that represent the positive integers {x1, ... , xn}, and let {U1, ... , Un}, {V1, ..., Vn} and {B1, ..., Bn} be additional nodes that also represent {x1, ... , xn} in the same order. Without loss of generality, assume x1 ... xn are in increasing order (this is only for visualization similar to the above graph; the order does not change any of the results here). Define the directed edges and their weights as follows:
* Ai goes to each Uk whenever the value of Uk is a factor of the value of Ai. All edges are weight 1.
* Uk goes to Vk. The weight of the edge from Uk to Vk is phi(xk).
* Vk goes to each Bj whenever the value of Vk is a factor of the value of Bj. All edges are weight 1.
We want to show the (i,j) entry of the matrix is gcd(xi,xj). Note that there is a path from Ai to Uk to Vk to Bj, if and only if the value of Uk (and Vk) divides the GCD of the values of Ai and Bj. Because of the special weights on the edges from Uk to Vk, the total weight that marks the (i,j) entry is the sum of phi(k) over all factors k of gcd(xi,xj), which by a result in number theory is equal to gcd(xi,xj) itself. This confirms the (i,j) entry equals gcd(xi,xj), and so the matrix is M.
Then by LGV, det(M) is the signed sum of non-intersecting path systems. Based on the condition that {x1, ... , xn} are distinct and closed under factors, I argue that there is only one such path system. Because all proper factors of xi are among xk where 1≤k≤i-1, any non-intersecting path system starting from {A1, ..., An} must start as Ai → Ui for all i. A symmetric argument shows that the path system must end as Vi → Bi for all i. Finally Ui → Vi for all i (these are the only edges between {U1, ... , Un} and {V1, ..., Vn}).
So there is exactly one non-intersecting path system: Ai → Ui → Vi → Bi for all i. Thus det(M) is just the weight of this path system , which is the product of weights of all the edges: phi(x1)*phi(x2)*...*phi(xn), QED.
Edit: Changed gcd(i,j) to gcd(xi,xj), which is what I meant.
