public
Last active

code for math.stackexchange question 107694 (http://math.stackexchange.com/a/107784): does division allow shorter arithmetic expressions with single digits as operands?

  • Download Gist
Question107694.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
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);
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.