8424432925592889329288197322308900672459420460792433

September 1, 2020

This blog is about programming, not proving math theorems, so you probably guessed that there is a counter example. You might have even noticed the hint in the title.

(define (f n) (gcd (+ (expt n 17) 9) (+ (expt (+ n 1) 17) 9)))

> (map f (range 50))
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
> (f 8424432925592889329288197322308900672459420460792433)
8936582237915716659950962253358945635793453256935559

No, nobody wrote a program to calculate that 52-digit number; the problem was constructed using some theorems of number theory. And yes, that 52-digit number is the smallest counter example to the conjecture. A010034 explains how to calculate the infinite sequence of such numbers, and shows the first hundred of them. You might also enjoy this video.

You can see the program at http://ideone.com/tdFHd1, but it doesn’t work because Chicken tries to perform the gcd calculation using floating-point arithmetic, which overflows.

Posted by programmingpraxis

Filed in Exercises

3 Comments »

3 Responses to “8424432925592889329288197322308900672459420460792433”

Zack said
September 4, 2020 at 10:04 AM
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!

Daniel said

September 6, 2020 at 3:49 AM

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

karnak said
September 20, 2020 at 3:30 PM
Another example:

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

n = 1578270389554680057141787800241971645032008710129107338825798
gcd = 5299875888670549565548724808121659894902032916925752559262837

Programming Praxis