Largest Denominator [closed]

Question

The number 1 can be written as sum of fractions of the form 1/p (where p>1). There are different ways to write it. You will be given an integer k which denotes the number of fractions to be used to get the sum as 1. You need to find the largest possible value of p among all possible ways. See sample input for clarity

Input Format:

The first line contains number of test cases t. Then t lines follow each having a single integer k.

Output:

You need to print the largest value of p modulo 10^9 + 7.

Constraints:

1<=t<=10^5
2<=k<=10^6

Sample Input --------------- Sample Output

2                        2
2                        6
3

Explanation There is only one way to write '1' as sum of two fractions. 1/2 + 1/2. hence the largest value is 2. In the second test case, the only possible ways as sum of three fractions are:

1/3, 1/3, 1/3
1/6, 1/2, 1/3
1/4, 1/4, 1/2

Among these the second representation has the largest denominator which is '6' and hence the answer.

Answer 1

Java

I solved this basic problem on Stack Overflow already, so I might as well do it here, too. Follow the link for a deeper explanation of the algorithm, but there's no reason to calculate all the possible fractions if you just want to know the largest denominator.

The only major difference between the code here and on SO is that I'm using modular multiplication, since each result should be mod 10^9 + 7 and this speeds it up considerably.

public class Egyptian {
    static int range = 1000000;
    static long[] mods;
    static long mod = 1000000007;

    public static void main(String[] args){
        mods = new long[range+1];
        mods[1] = 1;
        for(int k=2;k<=range;k++){
            mods[k] = (mods[k-1] * (mods[k-1]+1)) % mod;
            System.out.println(mods[k]);
        }
    }
}

Note: This code simply calculates and outputs every value for inputs 2 to 10^6. As a popularity contest, I thought a simple proof of concept would be enough. Feel free to downvote if you disagree.

It runs in a few seconds, but most of that time is taken by the million-line output. If you just want to fill the array with correct values, it finishes in well under a second. You can then read/write the input/output at the speed of IO.

Output: (only from 2-40, can't exactly paste a million lines here)

2
6
42
1806
3263442
56876256
530809436
905136947
994707547
127363070
613638513
614624128
690044800
363952039
128981958
502041307
671991252
275513076
791142674
33665861
222603452
718053684
214817910
348558872
748018254
148507635
647419241
330373625
661987133
851958095
407158983
684304220
916206786
752612499
438658510
487129601
996482080
806772777
958888343

Answer 2

APL (50)

⍪{⌈/∊v/⍨{g=+/(g←∧/⍵)÷⍵}¨v←,∘.,∘v⍣(n-1)⊢v←⍳!n←⎕}¨⍳⎕

This code skips the 'p modulo 10⁹ + 7' computation. But the algorithms is so slow (exponential) that you can barely get a result for k=5, let alone 10⁹. Therefore by all practical means it can be considered equivalent to a piece of code that computed it :-)

Example

      ⍪{⌈/∊v/⍨{g=+/(g←∧/⍵)÷⍵}¨v←,∘.,∘v⍣(n-1)⊢v←⍳!n←⎕}¨⍳⎕
⎕:
      3
⎕:
      2
⎕:
      3
⎕:
      4
 2
 6
24

The ⎕: is just the "input prompt" when used interactively.