8424432925592889329288197322308900672459420460792433

September 1, 2020

Regular readers know of my affinity for number theory. Today’s exercise is a reflection of that.

It is conjectured that the two numbers produced by the equations n17 + 9 and (n + 1)17 + 9 for a given n are always co-prime (that is, their greatest common divisor is 1). Is that conjecture correct?

Your task is to either prove that the greatest common divisor is always 1 or write a program that finds a case where the greatest common divisor is not 1. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “8424432925592889329288197322308900672459420460792433”

  1. Zack said

    Here is my take on it using Julia: https://pastebin.com/AKTLZNee

    Although it’s not solid proof, I checked n values up to 10 000 000 and couldn’t find an exception to this rule. However, there could be a case for higher values of n where the two values are not coprime. Cheers!

  2. Daniel said

    Here’s a C++ solution that conducts the search in parallel, using GMP for arbitrary-precision integers and OpenMP for multiprocessing.

    Given how large the smallest counterexample is, starting the search from zero is practically ineffective.

    When starting the search one billion numbers away, the counterexample is found after about 20 minutes on my 8 core (2 threads per core) processor. However, this approach would also be ineffective if I didn’t check the solution from @programmingpraxis, as I wouldn’t know where to start searching.

    /*
     * search.cpp
     *
     * Build
     *   $ c++ -O3 -fopenmp -o search search.cpp -lgmpxx -lgmp
     *
     * Usage
     *   $ [OMP_NUM_THREADS=INT] search [INIT]
     */
    
    #include <cstdlib>
    #include <iostream>
    
    #include <gmpxx.h>
    #include <omp.h>
    
    using namespace std;
    
    int main(int argc, char* argv[]) {
      mpz_class init(0);
      if (argc > 1)
        init.set_str(argv[1], 10);
      #pragma omp parallel
      {
        int num_threads = omp_get_num_threads();
        for (mpz_class n = init + omp_get_thread_num(); ; n += num_threads) {
          mpz_class x;
          mpz_pow_ui(x.get_mpz_t(), n.get_mpz_t(), 17);
          x += 9;
          mpz_class n1 = n + 1;
          mpz_class y;
          mpz_pow_ui(y.get_mpz_t(), n1.get_mpz_t(), 17);
          y += 9;
          mpz_class gcd;
          mpz_gcd(gcd.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t());
          if (gcd > 1) {
            #pragma omp critical
            cout << n << endl;
          }
        }
      }
      return EXIT_SUCCESS;
    }
    

    Example usage:

    $ ./search
    ...
    
    $ ./search 8424432925592889329288197322308900672459419460792433
    8424432925592889329288197322308900672459420460792433
    ...
    
  3. karnak said

    Another example:

    (n^19 + 6) and (n+1)^16 + 9

    n = 1578270389554680057141787800241971645032008710129107338825798
    gcd = 5299875888670549565548724808121659894902032916925752559262837

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: