Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
2  
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
2  
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
1  
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
show 2 more comments

4 Answers 4

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.

share|improve this answer
    
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
show 3 more comments

Ruby - 84 81 80 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
share|improve this answer
2  
What happens if $$ becomes small? You cannot guarantee any value for it. –  Howard Aug 5 '11 at 14:33
add comment

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])
share|improve this answer
add comment

Haskell, 91

No clue what n is, so I am hard coding it to zero.

main=getContents>>=putStr.f.map read.words
f(m:k:l)=' ':show(gcd(0^m+k)(1+k))++f l
f _=""

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.