Skip to main content

Equations Puzzle

Source: Interview Street

Problem: 
Find the number of positive integral solutions for the equations 

(1/x) + (1/y) = 1/N! 

(read 1 by x plus 1 by y is equal to 1 by n factorial) 

Print a single integer which is the no of positive integral solutions modulo 1000007.

Update (24 June 2014):
Solution: Posted by JDGM (James D G Miles) in comments!




Comments

  1. N, x, y > 0 so we may multiply both sides by N!xy:

    N!y + N!x = xy

    fiddle about with it:

    0 = xy - N!x - N!y = (x-N!)(y-N!) - N!N!

    (x-N!)(y-N!) = N!N!

    Both factors on the left are positive as x, y > 0 and hence x, y > N! otherwise the product would be non-positive or too small.

    The problem is now how many distinct ways the factors of N!N! may be shared between (x-N!) and (y-N!). We may consider just the possible factors in (x-N!) because whatever is left over will be in (y-N!).

    Decompose N! into prime powers p₁ᵅ¹p₂ᵅ²...pᵢᵅⁱ then we may have between zero and the full 2α₁ of N!N!'s p₁ powers in the (x-N!) factor and the rest in the (y-N!) factor.

    And so on, for p₂, p₃, ..., pᵢ.

    The number of solutions is therefore (2α₁+1)(2α₂+1)...(2αᵢ+1) because for each power p we have 2α+1 choices available to us as to how it shall be split between (x-N!) and (y-N!).

    It is straightforward to write an algorithm to find the α values of N!'s prime factorisation for given N, and hence calculate the answer using the preceding formula.

    For the second part, are we to similarly take arbitrary N, or is the solution to be taken across all values of x, y, N in Z₁₀₀₀₀₀₇? There can only be at most a finite 1000007³ such combinations of x, y, N so the solution in the latter case would be defined.

    Anyway, choose arbitrary M = 1/N! mod 1000007 and we require the number of solutions to 1/x + 1/y = M mod 1000007.

    My algorithm here is to tally ab=1 mod 1000007 for 0<a≤b<1000007 then build an array of that size and fill it with the a values for which ab=1 mod 1000007 through all compliant b. These are the possible 1/x and 1/y values - crucially note that 1/x or 1/y is not necessarily defined for all x, y in Z₁₀₀₀₀₀₇ which is why this step is necessary. The algorithm has effectively calculated just over half of the Z₁₀₀₀₀₀₇ multiplication table (includes diagonal) and stored the inverses where they exist, by picking out the corresponding factor where the entry in a row is 1. The next step of my algorithm is to go through this array, looking for values also in the array which add to the current value to make M mod 1000007. For each it finds, it adds 2 to the total number of solutions (because there is also a solution in the table on the other side of the diagonal - the table is symmetric), except in the case where the value lies on the diagonal when it adds only 1 to the total number of solutions (1000007 is odd, so the diagonal is its own reflection).

    If the question requires the number of all solutions over all x, y, N then we may repeat for all 0 < 1/N! < 1000007 and sum them. If not, and there is a single solution for all N then one calculation will suffice, though one may wish to calculate them all anyway to prove that they are the same.

    I believe Interview Street does not wish its answers publicly published so let's leave it there.

    ReplyDelete
  2. I do not know ... it is infinite? Because if
    x = 2 * N! and
    y = 2 * N!

    Then for any N greater than 2 it will be an equality.
    As many N, those many solutions.
    So infinite

    ReplyDelete
    Replies
    1. That's fair Vivek, but I believe the convention with this type of question is that capital-letter N is an arbitrary input for an algorithm, and not a variable of the problem in the same sense as x and y.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. And so, answer will be a function of N.

      Delete
  3. Solving for a fixed N.

    1/a = 1/(a+k) + k/a(a+k)...........(1)

    If a(a+k)/k is an integer, we have a solution for 1/a = 1/a+k + 1/b, where b = a(a+k)/k

    Therefore in this case, we are looking for all k such that N!(N!+k)/k is an integer.

    Basically this means k divides N!^2

    So we need the number of divisors of N!^2.

    One way of calculating the power of p in the decompsoition of N! is the famous expression
    a(p) = sum over j((n/p) + n/p^2)....+ (n/p^j)+....)
    Based on this, we know a(p) for all the primes, and therefore the number of divisors is
    (product over all primes(2a(p)+1) - 1)/2
    (Divide by 2 to account for double counting)

    ReplyDelete
    Replies
    1. You do not need to divide by 2. There is no double counting here as (1,2) is different from (2,1) when (x,y) is the solution to an equation. Thanks

      Delete
    2. Also, -1 is also not needed, as the trivial solution is also acceptable here. Thanks

      Delete

Post a Comment

Popular posts from this blog

Asking a girl out

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P

Most of my friends already read an article that I wrote more than an year back - "Speak Up"


Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it!

Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis.

@Consultants, correct me if I am wrong in my estimates. :P

Why is there a need to be selective?

From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once every week right …

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process.

1) Calculate P{X>Y}
2) What's the expected value of X
3) What's the expected value of Y

This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment.

Solution:
1)
(Solved by me finally after 13 months :))

Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently.

So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0"

f(State) = P(X>Y | "State" configuration initially)

f(0,0) = 1/4[f(…

Fraction Brainteaser

Source:
Sent to me by Gaurav Sinha

Problem:
Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions. In total, Siddhant scores 25 out of 34. 

Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34.

Note that
a) Vaibhav scores more than Siddhant
b) Siddhant score better than Vaibhav in both individual topics - 5/6 > 20/25 and 20/28 > 6/9

How is it possible?