Work: Differences Among Women

Jeffreys Copeland & Haemer

(SunExpert, February 1999)



Plus ça change, plus c'est la même chose.
                        --- The French


Vive la différence
                        --- Also the French


They say that nothing ever changes. Well, we've had a first.

Two months ago, we did a column entitled ``A Short History of Reading.'' It had some novel features.


The seventy-five columns we've now done have gotten us a lot of e-mail. Some folks express appreciation, some pick at our errors, some do both. We've had responses from all over the world and from all sorts of folks. But from a woman? Never.

(In fact, the first two responses on the column were from women.)

Think about this. Okay, we've never gotten a reader response from Antarctica either, but, even without consulting a world almanac, we're willing to chalk this up to the fact that there are very few people in Antarctica to respond in the first place. (Hey, Antarctica. Anyone out there read SunExpert?)

This is food for thought for us Jeffs, fathers between us of four daughters. More about this in a moment. First, though we want to talk a little about a math problem that Zoe Haemer brought home from third grade.


Differences, differences, differences
Here 'tis.

Start with any four integers: we'll use (0,1,4,11) to create a simple example.

Next, take the absolute value of the differences of adjacent numbers (consider it a circular list): (2,4,8,12)

Repeat this process until all the numbers are the same: 


(2,4,8,16) -> (2,4,8,12) -> (2,4,4,10) ->
        (2,0,6,8) -> (2,6,2,6) -> (4,4,4,4)

That took five steps. Zoe's challenge was to find one that took six. The book her teacher got the problem from said that no one had ever found an example that required more than six.

We think this is a great problem for a third grader for several reasons, at least the first three of which are that it requires a lot of subtracting.

It is also a great problem, as posed, for parents who program because it takes very little programming to find four-tuples that generate more than six steps. Our personal favorite is (0,1,4,9) -- not only are they the first four squares, they're all single digits. Look: 


(0,1,4,9) -> (1,3,5,9) -> (2,2,4,8) ->
        (0,2,4,6) -> (2,2,2,6) -> (0,0,4,4) ->
        (0,4,0,4) -> (4,4,4,4)

Seven steps.

It really impresses your third-grader when you show her you can do something that her math book says no one's ever been able to do before.

But discovering that something is unusual when it should be commonplace piques the curiosity. You understand: it's like getting your first reader response from a woman. Jeff Haemer went in to talk to his daughter's math teacher to investigate further.

The teacher's first response? ``Several fathers got interested in that problem and sent in solutions with seven steps.'' We note right away that's not ``several parents.''

We'll return to this math problem in a moment. Patience.


Where are the missing women?

So where are the women in these pictures? We're not sure, but let's knock down some commonly advanced straw men. (Oh, stop it. You know good-and-well what we mean.)


Get the picture? We have our own pet theories: probably no better, but at least they're different. Here are a couple.


We have complete confidence that you have some pet theories that are just as silly as these, and that you will mail them to us. If you're male.


Subtracting performance

Enough editorializing and idle speculation, let's talk code. We wrote a program to do an exhaustive search for solutions to Zoe's problem, and find beginning numbers that generated a cycle of six or more steps. We actually ended up writing several versions of programs to generate solutions.

The first one was in Perl. Even though the problem is an arithmetic problem, the arithmetic isn't hard. Add to this that it uses lots of lists and we like to program in Perl. Our Perl solution turned out to be ugly, slow as the dickens, and made our hard disk sound like our computer was home to a click beetle convention.

Okay, maybe C still is good for something. Besides, we didn't have a FORTRAN compiler. (And anyway, as Copeland's wife has been heard to observe ``A good FORTRAN programmer can write FORTRAN in any language.'')

Here's our second cut. 

/* $Id: steps.c,v 1.1 1998/12/01 04:54:06 jsh Exp jsh $ */

#include <stdio.h>
#include <stdlib.h>

int nmax = 10;
int lim = 6;

int
steps(int a, int b, int c, int d) {
 int n = 0;
 int a0;

 while(1) {
  if ((a == b) && (a == c) && (a == d))
   return n;
  a0 = a;
     a = abs(b-a); b = abs(c-b); c = abs(d-c); d = abs(a0-d);
  n++;
 }
}

int
main(int argc, char *argv[]) {

 int i, j, k, l, n;

 int lim = 6;  /* don't print anything with under lim steps */
 int nmax = 9; /* maximum integer in a 4-tuple */

 if (argc > 3) {
  fprintf(stderr, "usage: %s [cutoff] [maxint]\n", argv[0]);
  exit(1);
 }
 if (argc == 3)
  nmax = atoi(argv[2]);
 if (argc > 1)
  lim = atoi(argv[1]);

 for (i = 0; i<=nmax; i++)
  for (j = 0; j<=nmax; j++)
   for (k = 0; k<=nmax; k++)
    for (l = 0; l<=nmax; l++) {
     if ((n = steps(i, j, k, l)) >= lim)
      printf("%d %d %d %d : %d \n",
       i, j, k, l, n);
    }
 exit(0);
}

We weren't content to leave well enough alone (is any programmer?) so we decided we'd look for ways to speed it up.

Our first optimization came from realizing that the problem can be solved recursively, like factorials. We can figure out the number of steps for (1,1,1,3) by figuring out that it takes one more step than (0,0,2,2),

Not only can we write a recursive version, but we can use the common trick used in factorial functions of caching away each answer to prevent having to calculate it again.

A second optimization cuts our work even further. All circular permutations of a list take the same number of steps. So does the reverse of each of these. As soon as we calculate and store the number of steps for (1,2,3,4) we can also immediately store the number of steps for seven others: (2,3,4,1), (3,4,1,2), (4,1,2,3), (4,3,2,1), (3,2,1,4), (2,1,4,3), and (1,4,3,2).

Clever, eh? (Reader quiz: there's a second set of eight that can also be stored. What is it?)

Here's our clever, optimized version: 

/* $Id: optimized_steps.c,v 1.1 1998/12/01 04:54:34 jsh Exp jsh $ */

#include <stdio.h>
#include <stdlib.h>

#define UNDEF -1
int ****S;

/* create a 4d cube of width "len" */
int ****
make_4d_cube(int len)
{
 int i, j, k, l;
 int *s;
 int **r;
 int ***q;
 int ****p;

 p = malloc(len * sizeof(int ***));
 for (i=0; i<len; i++) {
  q = malloc(len * sizeof(int **));
  p[i] = q;
  for (j=0; j<len; j++) {
   r = malloc(len * sizeof(int *));
   q[j] = r;
   for (k=0; k<len; k++) {
    s = malloc(len * sizeof(int));
    r[k] = s;
    for (l=0; l<len; l++) {
     s[l] = UNDEF; /* initialize all entries to UNDEF */
    }
   }
  }
 }
 return p;
}

int
steps(int a, int b, int c, int d)
{
 int x = S[a][b][c][d];
 if (x != UNDEF) return x;

 /* all circular permutations of this 4-tuple and their reverses
  have the same number of steps */
 x =
 S[a][b][c][d] = S[b][c][d][a] = S[c][d][a][b] = S[d][a][b][c] =
 S[d][c][b][a] = S[c][b][a][d] = S[b][a][d][c] = S[a][d][c][b] =
     steps(abs(b-a), abs(c-b), abs(d-c), abs(a-d)) + 1;
 return x;
}

int
main(int argc, char *argv[])
{
 int i, j, k, l, n;

 int lim = 6;  /* don't print anything with under lim steps */
 int nmax = 9; /* maximum integer in a 4-tuple */

 if (argc > 3) {
  fprintf(stderr, "usage: %s [cutoff] [maxint]\n", argv[0]);
  exit(1);
 }
 if (argc == 3)
  nmax = atoi(argv[2]);
 if (argc > 1)
  lim = atoi(argv[1]);

 S = make_4d_cube(nmax+1);

 /* entries like (3,3,3,3) have 0 steps */
 for (i = 0; i<=nmax; i++)
  S[i][i][i][i] = 0;

 /* now figure out the number of steps for each 4-tuple */
 for (i = 0; i<=nmax; i++)
  for (j = 0; j<=nmax; j++)
   for (k = 0; k<=nmax; k++)
    for (l = 0; l<=nmax; l++) {
     if ((n = steps(i, j, k, l)) >= lim)
      printf("%d %d %d %d : %d \n",
       i, j, k, l, n);
    }
 exit(0);
}

But how clever is it? Not very, as it turns out. When the integers in the lists are small, either program is fast enough. By the time we permit large numbers in the 4-tuples -- say, up to 100 -- the original, brute-force method is actually faster! Why? The chattering of our disk reminds us that with integers this big, the array we're allocating to cache the steps for each 4-tuple is 4*100*100*100*100 bytes. We're pretty cavalier about space on today's machines -- an old programmer is someone who remembers when a kilobyte wasn't just an archaic name for a millimeg (and why kilobytes were used to measure something called ``core'') -- but a 400 megabyte array is still big enough to cause paging.


Minus the answers

We can use either version of this program to find 4-tuples that give us large numbers of steps. (0,1,4,9) is the first 4-tuple with 7 steps. To get the first 4-tuple with 8 steps, you need to allow integers up to 11: (0,2,5,11). You want 9 steps? The first one is (0,2,6,13).

Here's a table of the lowest integers that you need to permit in 4-tuples to get specific numbers of steps: 

Steps   Integers
1       1
2       1
3       1
4       3
5       3
6       4
7       9
8       11
9       13
10      31
11      37
12      44
13      105
14      125
15      149

Doesn't it seem odd that it's easy to find 7-, 8-, and 9-step examples with low integers, yet you have to go all the way up to 4-tuples containing 31 to find a 10-step example? And look at that jump that it takes to go from 12 to 13. And why do these seem to cluster in groups of three? We don't know.

Can we just keep going? Are there 4-tuples with arbitrarily large numbers of steps? If we go high enough, can we find 4-tuples that don't stabilize at all, that have an infinite number of steps? We don't know.

Computers, with their brute-force solutions, often raise as many questions as they answer. This started out as a math problem. Can we answer our questions by deriving a mathematical foundation for all this -- say, from the calculus of finite differences? We don't know.

In fact, why don't we say anything about 4-tuples that take more than 15 steps? Because we haven't been able to generate one yet. No, wait. That's ``No one has ever found an example that takes more than fifteen steps.''

We'll report the sex-ratio of reader responses in a future column. Until then, happy trails.