# Greatest greatest common divisor

Find the greatest gcd of the numbers nm + k and (n+1)m + k for given `m` and `k`.

For example, for `m=3, k=1` we have:

``````gcd(1^3 + 1, 2^3 + 1) = 1
gcd(2^3 + 1, 3^3 + 1) = 1
...
gcd(5^3 + 1, 6^3 + 1) = 7  :max
...
``````

### Input/Output

Input is L lines through file or stdin, EOF terminated. Each line contains two integers: `m` and `k` separated by a space.

Output is L integers separated by any pattern of whitespace characters (tabs, spaces, newlines etc).

### Examples

Input

``````2 4
2 7
3 1
4 1
3 2
5 4
10 5
``````

Output

``````17
29
7
17
109
810001
3282561
``````

### Update

I can't find a proof that the solution is bounded for all `n` given some `m` and `k`, so you only have to find the GGCD for `n < 10,000,000`.

-
For m=5, k=4 value is >= 810001. – Ante Aug 3 '11 at 20:24
@Ante: Interesting! Are you sure? Do you know for what `n` is 810001? – Eelvex Aug 4 '11 at 5:06
n=329529. Are you sure that max(gcd(n,n+1) of series) is good defined? I can't find a proof or good rezone for that, except very much regularity in gcd(n,n+1) series. – Ante Aug 4 '11 at 8:28
Please clarify spec: how is n arrived at? – arrdem Aug 5 '11 at 18:12
@mckenzie: brute force, iterating n to few millions and checking gcd(). – Ante Aug 5 '11 at 19:10

Update:

GGCD for given `m` and `k` is good defined.

This is table of GGCD tested for n up to 500000.

``````m/k      1       2       3       4       5       6       7       8       9      10
2        5       9      13      17      21      25      29      33      37      41
3        7     109      61     433     169     973     331    1729     547    2701
4       17      33      49      65      81      97     113     129     145    2093
5      341   52501  258751  810001       1  131371       1       1  501311 2846591
6       65     129     193     257   21507     385     449   22059     577     641
7     3683  235747       1       1      71  438299  940507   33461     757  110503
8     4369     513     769   13325    1281  149089  202609    2049  975937  617201
9   359233  232537  202927  470983  123019  708589  241117 5601589  398581   19783
10   62525  514299  183757  807517 1094187 16856405  97477    8193  377897 25919971
``````

For `m==2 or 4` it looks quite good :-)

It seems that if p_in_i is gcd for some n, where p_i is a prime, than every combination of products of p_i's with exponents <= n_i is also gcd for some n. E.g. for m=8,k=2, 3^3 and 19 are gcd of type p_in_i, also 57, 171 and 513 are gcd's.

Some theory background: If `g = gcd(n) > 1` for some `n`, and `d > 1` and `d divide g` (it can be `d=g`) than `d divide gcd(n±d)`. It is easy to prove. That means:

• If you find some `g = gcd(n) > 1` for some `n`, than `gcd(n±d) > 1`. So, it is enough to jump for found prime number of steps while iterating `n`.
• If prime `p` divide some `gcd()` than there is `n <= p` where `p` divide `gcd(n)`. Prime `p` will 'appear' in `gcd(n)` for some `n <= p`.

These properties can speed up search, but still there is a question is GGCD good defined.

-
Except m=4,k=10 - that one is very interesting and breaks the pattern (2093). Makes one wonder if you made `n` go higher you might find even higher numbers for m=4, k<10. – mellamokb Aug 5 '11 at 16:11
And m=7, k=9 has GGCD of at least 9846271 (see n=9790012). – Howard Aug 5 '11 at 17:14
@mellamokb: maybe it doesn't break a pattern, 161 is gcd() for n = 241. For m=4,k=10 there is no other gcd till n=10^7. – Ante Aug 5 '11 at 19:15
@Howard: Now I checked also till n=10^7:-) Since 757 and 9846271 are both prime, than 757*9846271=7453627147 is also gcd() for some large n. – Ante Aug 5 '11 at 19:21
@Ante: I was commenting about the fact that your table above has 2093 as the entry for m=4, k=10... or am I misreading the table?? – mellamokb Aug 5 '11 at 21:00

# Ruby - 848180 79 chars

Passes all test cases, not sure if it can handle larger numbers.

``````\$<.map{|l|m,k=l.split.map &:to_i;p (1..\$\$).map{|n|(n**m+k).gcd (n+1)**m+k}.max}
``````

### Test

``````D:\tmp>ruby cg_gcd.rb < cg_gcd.in
17
29
7
17
109
3361
``````
-
What happens if `\$\$` becomes small? You cannot guarantee any value for it. – Howard Aug 5 '11 at 14:33

Sage, 92

``````for l in sys.stdin.readlines():m,k=l.split();print max(gcd(n^m+k,(n+1)^m+k)for n in[1..1e7])
``````
-

No clue what `n` is, so I am hard coding it to zero.
``````main=getContents>>=putStr.f.map read.words
Note: `0^m` cannot be reduced further (either 0 or 1, depending if `m` is 0). I say `0^0` is 1 because combinatoric mathmaticians define it as such. Screw calculus.
I have a feeling OP meant that `n` is every possible integral `n`. However, as discussed by @Ante, we have no upper bound defined for this sequence, and perhaps there can't be one defined, which is the fundamental problem with this question. – mellamokb Aug 5 '11 at 21:04