Further On An Arithmetical Pursuit

| 0 Comments

Arithmetical Pursuit

You will recall that my fellow students and I have been investigating the properties of arithmetical pursuit[1]; a game that we often play at afternoon tea in which the goal is to take six randomly chosen integers and create an arithmetical formula comprised of additions, subtractions, multiplications and/or divisions to yield an integer as close as possible to a randomly chosen target between one and one thousand.
Those integers are provided by a deal of six cards, of which the pips represent their face value, the Jacks represent twenty five, the Queens fifty and the Kings one hundred and the target is chosen by rolling three twenty sided dice, upon which the digits zero to nine are marked twice apiece and where three zeros represent one thousand.

We progressed as far as proving that there were no targets that could not be hit provided a fortunate hand of cards were dealt and that the number of admissible formulae that might arise during the game is somewhere between \(149,955,465,707,008\) and \(631,536,888,413,860\), with our expectation being that it is very much closer to the former than to the latter.
This we deduced from the fact that fractional results could only arise through division and that the number of formulae that might arise using \(n\) cards and \(m\) of the arithmetical operators of addition, subtraction, multiplication and division is given by
\[ \frac{(2n-1)! \times 52! \times m^{n-1}}{(2n-1) \times (n-1)! \times n! \times (52-n)!} \]
where the exclamation mark stands for the factorial of the value before it, and thence summing over \(n\) from one to six for \(m\) equal to three for formulae that only admit addition, subtraction and multiplication and equal to four for those that also admit division.

We concluded that, whilst we were unable to deduce exactly how close to the former figure the number of admissible formulae might be and whilst they were far too numerous to test exhaustively, we should like to at least gain a rough notion of it.

Sampling The Formulae

We decided instead to test a subset of the possible formulae to gain some insight into how frequently they resulted in fractions. The first thing that we noted was that the overwhelming majority of them use all six cards, as demonstrated by deck 1.

Deck 1: The Number Of Formulae

We can therefore figure a reasonable approximation of the correct result if we limit our experimentation to these most numerous cases. To be sure that we don't inadvertently introduce some kind of bias into our testing it will be necessary to choose the formulae at random, which we can achieve by again exploiting reverse Polish notation, or RPN, in which the arithmetical operators appear after the numbers upon which they act rather than between them. For example, we would write
\[ 3 \times 10 + 2 \]
as
\[ 3 \; 10 \; \times \; 2 \; + \]
which we read as take three and ten and multiply them, then take the result and two and add them. The general rule for interpreting RPN formulae is

Reading from left to right, whenever you come across an arithmetical operator apply it to the two numbers that precede it, then scrub out both them and the operator and write in their place the result and begin again, until there is but a single number left.

Recall that when figuring the number of formulae having \(n\) arguments we divided them into subsets of varying general structure by using \(x\) as a place-holder for a number and \(o\) as a place-holder for one of the arithmetical operators of addition, subtraction, multiplication and division. The above formula is a member of the \(xxoxo\) subset, for example, as is
\[ 3 \; 10 \; + \; 2 \; \times \]
The great advantage of RPN is that it entirely does away with the need to employ parentheses to change the order in which the operators are applied. Furthermore, we can easily determine whether a formula involving only addition, subtraction, multiplication and division is valid by simply checking that there is one more number than there are operators and that at no point when reading from left to right does the count of the operators equal or exceed that of the numbers. We have already proven that as a direct consequence there were, for \(n\) numbers
\[ \frac{(2n-1)!}{(2n-1) \times (n-1)! \times n!} \]
of our subsets of RPN formulae, and for six numbers this works out to be
\[ \frac{(2 \times 6 - 1)!}{(2 \times 6 - 1) \times (6-1)! \times 6!} = \frac{11!}{11 \times 5! \times 6!} = \frac{39,916,800}{11 \times 120 \times 720} = \frac{39,916,800}{950,400} = 42 \]
To randomly generate a formula we may therefore simply select one of those forty two subsets at random and replace each of its \(o\) symbols with a randomly chosen operator and its \(x\) symbols with numbers determined by the first six cards of a well shuffled deck.

Enumerating The RPN Subsets

At first glance it may not seem obvious how we might go about identifying the RPN subsets, but there's a simple trick with which we can do so; given a subset with \(n\) \(x\) symbols, we simply read from left to right replacing each of them in turn with the symbols \(xxo\), which represents formulae that immediate yield a single number, to create \(n\) new subsets having \(n+1\) \(x\) symbols! For example, starting with \(xxoxo\) we produce \(xxoxoxo\), \(xxxooxo\) and \(xxoxxoo\).
Essentially, we are applying the rule for reading RPN formulae backwards and if, starting with but a single \(x\) symbol, we also apply the transformation to new subsets as they are produced we shall surely enumerate every RPN subset that contains formulae that resolve to a single number. Of course, we shall have to cease applying it to subsets that have as many numbers as we have to work with or we shall never bring the process to a conclusion.
Note that it is entirely possible to arrive at a subset via different routes, so we must take care to ignore those we have visited already, as is done by the student.rpnSubsets function given in listing 1.

Listing 1: student.rpnSubsets
function rpnSubsets(current, subsets, n) {
 var i, next;

 if(subsets.indexOf(current)<0) {
  subsets.push(current);
  if(n>1) {
   i = current.indexOf('x');
   while(i>=0) {
    next = current.slice(0, i) + 'xxo' + current.slice(i+1);
    rpnSubsets(next, subsets, n-1);
    i = current.indexOf('x', i+1);
   }
  }
 }
}

student.rpnSubsets = function(n) {
 var subsets = [];
 n = ak.floor(n);
 if(n>0) rpnSubsets('x', subsets, n);
 subsets.sort(function(s1, s2){return s1.length-s2.length;});
 return subsets;
};

Here n is the count of numbers upon which the formulae may operate and the subsets recursively produced by the rpnSubsets helper function are sorted by their size upon completion, as demonstrated by deck 2.

Deck 2: The RPN Subsets

Note that the number of subsets of each size are precisely in accordance with our formula
\[ \begin{align*} \frac{(2 \times 1 - 1)!}{(2 \times 1 - 1) \times (1-1)! \times 1!} &= \frac{1!}{1 \times 0! \times 1!} = \frac{1}{1 \times 1 \times 1} = \frac{1}{1} = 1\\ \\ \frac{(2 \times 2 - 1)!}{(2 \times 2 - 1) \times (2-1)! \times 2!} &= \frac{3!}{3 \times 1! \times 2!} = \frac{6}{3 \times 1 \times 2} = \frac{6}{6} = 1\\ \\ \frac{(2 \times 3 - 1)!}{(2 \times 3 - 1) \times (3-1)! \times 3!} &= \frac{5!}{5 \times 2! \times 3!} = \frac{120}{5 \times 2 \times 6} = \frac{120}{60} = 2\\ \\ \frac{(2 \times 4 - 1)!}{(2 \times 4 - 1) \times (4-1)! \times 4!} &= \frac{7!}{7 \times 3! \times 4!} = \frac{5040}{7 \times 6 \times 24} = \frac{5040}{1008} = 5 \end{align*} \]
Now, since we shall only be interested in the forty two RPN formulae subsets for six numbers we shall need to discard the rest before the experiment, as illustrated by deck 3.

Deck 3: The Six Number RPN Subsets

Filling In The Place-Holders

To select the six numbers we must simulate the shuffling of a deck of cards, which we typically do by randomly reordering an array of numbers, strings or other identifiers representing them. To do this we might select one card at random, remove it from the deck and repeat until we have taken them all. Creating a new array containing all but the selected card at each step would be a somewhat costly proposition but fortunately there is a far more efficient scheme; rather than remove the card we instead swap it with the one that we are currently seeking to randomise. Note that it is vitally important that the card that we select at random come only from those that have not yet been shuffled, including the card that we are currently shuffling.
For example, if we had but the four cards

          

we might begin by selecting the third and swapping it with the first

          

then selecting the second and swapping it with itself

          

then selecting the fourth and and swapping it the third

          

until finally we must leave the fourth card where it is

     

Given that we only require six numbers for our arithmetical pursuit, we can spare ourselves some effort by ceasing the shuffle after the first six cards, as is done by student.shuffle6 in listing 2.

Listing 2: student.shuffle6
student.shuffle6 = function(deck) {
 var n = deck.length;
 var i, j, c;

 for(i=0;i<n-1 && i<6;++i) {
  j = i+ak.floor(Math.random()*(n-i));
  c = deck[j];
  deck[j] = deck[i];
  deck[i] = c;
 }
};

Note that, much as when shuffling an actual deck of cards, the order of the cards before the shuffle doesn't impact the randomness of the result and consequently we do not need to put them back in order before the next shuffle.

Having drawn our cards we should immediately replace them with the numbers that they stand for and so we would do well to create a deck of the numbers themselves so as to cut out a step of the process, as is done by the student.arithmeticalPursuitDeck function given in listing 3.

Listing 3: student.arithmeticalPursuitDeck
student.arithmeticalPursuitDeck = function() {
 var deck = new Array(52);
 var card = 0;
 var i, j;

 for(i=0;i<4;++i) {
  for(j=1;j<=10;++j) deck[card++] = j;
  deck[card++] = 25;
  deck[card++] = 50;
  deck[card++] = 100;
 }
 return deck;
};

Randomly selecting the four arithmetical operators is a much easier task since each choice has no bearing whatsoever upon any of the others so we can simply randomly pick one of the integers zero, one, two and three and use them to indicate addition, subtraction, multiplication and division respectively.

Given a string representing one of our subsets of RPN formulae and arrays of the numbers and operators that should replace the \(x\) and \(o\) symbols respectively, we can easily transform them into an array representing a RPN formula, as shown by student.rpnFill in listing 4.

Listing 4: student.rpnFill
student.rpnFill = function(subset, numbers, operators) {
 var n = 0;
 var o = 0;
 var f = new Array(subset.length);
 var i;

 for(i=0;i<subset.length;++i) {
  f[i] = subset.charAt(i)==='x' ? numbers[n++] : operators[o++];
 }
 return f;
};

Testing The Formulae

The student.rpnCalc function presented in listing 5 applies the rule for interpreting RPN formulae, utilising the stack array to keep track of the numbers that have not yet been scrubbed out rather than updating the formula f itself.

Listing 5: student.rpnCalc
student.rpnCalc = function(f) {
 var stack = [];
 var n = f.length;
 var i, arg, x1, x2;

 for(i=0;i<n;++i) {
  arg = f[i];
  if(ak.nativeType(arg)===ak.STRING_T) {
   x2 = stack.pop();
   x1 = stack.pop();
   switch(arg) {
    case '+': stack.push(x1+x2);
              break;
    case '-': stack.push(x1-x2);
              break;
    case '*': stack.push(x1*x2);
              break;
    case '/': if(x1%x2!==0) return ak.NaN;
              stack.push(x1/x2);
              break;
    default:  return ak.NaN;
   }
  }
  else stack.push(arg);
 }
 return stack.length===1 ? stack[0] : ak.NaN;
};

Note that, since fractions are not permitted in the game, this function returns ak.NaN if a division operation should happen to yield one.

Armed with these functions it is a simple matter to randomly sample the arithmetical pursuit formulae so as to estimate the proportion that involve fractions, as demonstrated by deck 4.

Deck 4: The Proportion Of Fractional Formulae

From this experiment we may expect that approximately sixty seven percent of the formulae involve fractions, as compared to the roughly seventy six percent that involve division and consequently might do so.
We can therefore conclude that there are something of the order of \(210,000,000,000,000\) admissible formulae that might arise during the game.
\(\Box\)

References

[1] On An Arithmetical Pursuit, www.thusspakeak.com, 2015.

Based upon an article I wrote for ACCU's Overload magazine.

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+