Example constructive existence proof

README.md

Example Constructive Existence Proof

CS 180 • 9/8/14

Theorem: There exists some integer that is expressable as the sum of two cubes in two different ways.

This code implements a constructive existence proof of that theorem. It finds two sets of such cubes.

cubes.c

#import <stdio.h>
#import <math.h>
#import <stdlib.h>

typedef struct {
  int a;
  int b;
} expo;

int main() {

  int a, b;

  expo * ways = (expo*) malloc(sizeof(expo) * 1000000);

  for (a = 0; a < 100; a++) {
    for (b = 0; b < 100; b++) {

      int ex = pow(a,3) + pow(b,3);
      if (ex > 1000000) return 1;

      expo result = {a,b};

      if (ways[ex].a != 0) {
        if (ways[ex].a == b && ways[ex].b == a) { continue; }

        printf("{%d, %d}; {%d, %d} = %d\n", result.a, result.b, ways[ex].a,
          ways[ex].b, ex);
        // return 0;
      } else {
        ways[ex] = result;  
      }

    }
  }

  printf("No ways.\n");
  return 0;
}

output

λ ~/Desktop/ ./cubes
{9, 10}; {1, 12} = 1729
{9, 15}; {2, 16} = 4104
{10, 9}; {1, 12} = 1729
{15, 9}; {2, 16} = 4104
{15, 33}; {2, 34} = 39312
{16, 33}; {9, 34} = 40033
{18, 20}; {2, 24} = 13832
{18, 30}; {4, 32} = 32832
{19, 24}; {10, 27} = 20683
{20, 18}; {2, 24} = 13832
{22, 57}; {9, 58} = 195841
{22, 59}; {3, 60} = 216027
{24, 19}; {10, 27} = 20683
{24, 54}; {17, 55} = 171288
{26, 36}; {17, 39} = 64232
{27, 30}; {3, 36} = 46683
{27, 45}; {6, 48} = 110808
{29, 50}; {8, 53} = 149389
{30, 18}; {4, 32} = 32832
{30, 27}; {3, 36} = 46683
{30, 66}; {4, 68} = 314496
{30, 92}; {11, 93} = 805688
{31, 33}; {12, 40} = 65728