Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
code for math.stackexchange question 107694 (http://math.stackexchange.com/a/107784): does division allow shorter arithmetic expressions with single digits as operands?
import java.util.Map;
import java.util.TreeMap;
public class Question107694 {
final static int n = 7;
static boolean handle (Map<Integer,String> newExpressions,String ej,String ek,int result,char op) {
boolean isNew = !newExpressions.containsKey (result);
if (isNew)
newExpressions.put (result,"(" + ej + ")" + op + "(" + ek + ")");
return isNew;
}
public static void main (String [] args) {
Map<Integer,String> expressions = new TreeMap<Integer,String> ();
for (int d = 1;d <= 9;d++)
expressions.put (d,String.valueOf (d));
int length = 2;
for (int i = 0;i < n;i++) {
Map<Integer,String> newExpressions = new TreeMap<Integer,String> (expressions);
for (Integer j : expressions.keySet ())
for (Integer k : expressions.keySet ())
if (j >= k) {
String ej = expressions.get (j);
String ek = expressions.get (k);
if (ej.length () + ek.length () == length) {
handle (newExpressions,ej,ek,j + k,'+');
if (j != k)
handle (newExpressions,ej,ek,j - k,'-');
handle (newExpressions,ej,ek,j * k,'*');
if (j % k == 0 && !newExpressions.containsKey (j / k))
// since we're iterating in order, expressions without division would already have been found
System.out.println ("new result from division: (" + ej + ")/(" + ek + ") = " + j / k);
}
}
length += 6;
expressions = newExpressions;
int leastInexpressible = 0;
while (expressions.containsKey (++leastInexpressible))
;
System.out.println ((i + 1) + " operations: " + expressions.size () + " values, least inexpressible value: " + leastInexpressible);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.