# Greatest greatest common divisor

Find the greatest gcd of the numbers $$\n^m + k\$$ and $$\(n+1)^m + k\$$ for given m and k.

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

• $$\n = 1\$$: $$\\gcd(1^3 + 1, 2^3 + 1) = 1\$$
• $$\n = 2\$$: $$\\gcd(2^3 + 1, 3^3 + 1) = 1\$$

$$\\vdots\$$

• $$\n = 5\$$: $$\\gcd(5^3 + 1, 6^3 + 1) = 7\$$ (max)

$$\\vdots\$$

• $$\n \to \infty\$$

### 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? 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? 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. Aug 5 '11 at 16:11
• And m=7, k=9 has GGCD of at least 9846271 (see n=9790012). 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?? 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. 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])


# Jelly, 9 bytes

*@Ɱȷ7+gƝṀ


Try it online!

This times out on TIO no matter the input due to the Ɱȷ7 which iterates over the range $$\1, 2, ..., 10^7\$$. By reducing the 7 to a smaller value, we can get TIO to actually output some results (obviously it gets it wrong for inputs where $$\n > 10^5\$$): Try it online!

Not exactly spec-conforming, but given the age I didn't see much issue with that. Takes input in the form of command line arguments. $$\m\$$ first, then $$\k\$$

## How it works

*@Ɱȷ7+gƝṀ - Main link. Takes m as a left argument and k on the right
ȷ7     - 10000000
Ɱ       - Over each n between 1 and 10000000:
*@        -   Calculate n^m