# 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