8
\$\begingroup\$

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\$.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ For m=5, k=4 value is >= 810001. \$\endgroup\$
    – Ante
    Aug 3 '11 at 20:24
  • \$\begingroup\$ @Ante: Interesting! Are you sure? Do you know for what n is 810001? \$\endgroup\$
    – Eelvex
    Aug 4 '11 at 5:06
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Ante
    Aug 4 '11 at 8:28
  • 1
    \$\begingroup\$ Please clarify spec: how is n arrived at? \$\endgroup\$
    – arrdem
    Aug 5 '11 at 18:12
  • \$\begingroup\$ @mckenzie: brute force, iterating n to few millions and checking gcd(). \$\endgroup\$
    – Ante
    Aug 5 '11 at 19:10
6
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ 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. \$\endgroup\$
    – mellamokb
    Aug 5 '11 at 16:11
  • \$\begingroup\$ And m=7, k=9 has GGCD of at least 9846271 (see n=9790012). \$\endgroup\$
    – Howard
    Aug 5 '11 at 17:14
  • \$\begingroup\$ @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. \$\endgroup\$
    – Ante
    Aug 5 '11 at 19:15
  • \$\begingroup\$ @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. \$\endgroup\$
    – Ante
    Aug 5 '11 at 19:21
  • \$\begingroup\$ @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?? \$\endgroup\$
    – mellamokb
    Aug 5 '11 at 21:00
1
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ What happens if $$ becomes small? You cannot guarantee any value for it. \$\endgroup\$
    – Howard
    Aug 5 '11 at 14:33
1
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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
     +    -   Add k
       Ɲ  - Over each neighbouring pair in the list (i.e. n^m+k and (n+1)^m+k):
      g   -   Calculate their GCD
        Ṁ - Output the maximum
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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