An optimization challenge with strange coins
Score = 26/14 ~= 1.857

import java.util.*;

public class LembikWeighingOptimisation {

    public static void main(String[] args) {
        float best = 0;
        int opt = 1;
        for (int n = 6; n &lt; 32; n+=2) {
            long start = System.nanoTime();
            System.out.format("%d\t", n);
            opt = optimise(n, n / 2 + 1);
            float score = n / (float)opt;
            System.out.format("%d\t%f", opt, score);
            if (score &gt; best) {
                best = score;
                System.out.print('*');
            }
            System.out.format(" in %d seconds", (System.nanoTime() - start) / 1000000000);
            System.out.println();
        }
    }

    private static int optimise(int numCoins, int minN) {
        MaskRange.N = numCoins;
        Set&lt;MaskRange&gt; coinSets = new HashSet&lt;MaskRange&gt;();
        coinSets.add(new MaskRange(0, 0));

        int allCoins = (1 &lt;&lt; numCoins) - 1;

        for (int n = minN; n &lt; numCoins; n++) {
            for (int startCoins = 1; startCoins * 2 &lt;= numCoins; startCoins++) {
                for (int mask = (1 &lt;&lt; startCoins) - 1; mask &lt; (1 &lt;&lt; numCoins); ) {
                    // Quick-reject: in n turns, do we cover the entire set?
                    int qr = (1 &lt;&lt; (n-1)) - 1;
                    for (int j = 0; j &lt; n; j++) qr |= mask &lt;&lt; j;
                    if ((qr &amp; allCoins) == allCoins &amp;&amp; canDistinguishInNTurns(mask, coinSets, n)) {
                        System.out.print("[" + Integer.toBinaryString(mask) + "] ");
                        return n;
                    }

                    // Gosper's hack to update
                    int c = mask &amp; -mask;
                    int r = mask + c;
                    mask = (((r^mask) &gt;&gt;&gt; 2) / c) | r;
                }
            }
        }

        return numCoins;
    }

    private static boolean canDistinguishInNTurns(int mask, Set&lt;MaskRange&gt; coinsets, int n) {
        if (n &lt; 0) throw new IllegalArgumentException("n");
        int count = 0;
        for (MaskRange mr : coinsets) count += mr.size();
        if (count &lt;= 1) return true;
        if (n == 0) return false;

        // Partition.
        Set&lt;MaskRange&gt;[] p = new Set[Integer.bitCount(mask) + 1];
        for (int i = 0; i &lt; p.length; i++) p[i] = new HashSet&lt;MaskRange&gt;();
        for (MaskRange range : coinsets) range.partition(mask, p);

        for (int d = 0; d &lt; 2; d++) {
            boolean ok = true;
            for (Set&lt;MaskRange&gt; s : p) {
                if (!canDistinguishInNTurns((mask &lt;&lt; 1) + d, s, n - 1)) {
                    ok = false;
                    break;
                }
            }

            if (ok) return true;
        }

        return false;
    }

    static class MaskRange {
        public static int N;
        public final int mask, value;

        public MaskRange(int mask, int value) {
            this.mask = mask;
            this.value = value &amp; mask;
            if (this.value != value) throw new IllegalArgumentException();
        }

        public int size() {
            return 1 &lt;&lt; (N - Integer.bitCount(mask));
        }

        public void partition(int otherMask, Set&lt;MaskRange&gt;[] p) {
            otherMask &amp;= (1 &lt;&lt; N) - 1;

            int baseline = Integer.bitCount(value &amp; otherMask);
            int variables = otherMask &amp; ~mask;
            int union = mask | otherMask;
            partitionInner(value, union, variables, baseline, p);
        }

        private static void partitionInner(int v, int m, int var, int baseline, Set&lt;MaskRange&gt;[] p) {
            if (var == 0) {
                p[baseline].add(new MaskRange(m, v));
            }
            else {
                int lowest = var &amp; (1 + ~var);
                partitionInner(v,          m, var &amp; ~lowest, baseline, p);
                partitionInner(v | lowest, m, var &amp; ~lowest, baseline + 1, p);
            }
        }

        @Override
        public String toString() {
            return String.format("(x &amp; %x = %x)", mask, value);
        }
    }
}


Save as LembikWeighingOptimisation.java, compile as javac LembikWeighingOptimisation.java, run as java LembikWeighingOptimisation.

Many thanks to Mitch Schwartz for pointing out a bug in the first version of the quick-reject.

This uses some fairly basic techniques which I can't rigorously justify. It brute-forces, but only for starting weighing operations which use at most half of the coins: sequences which use more than half of the coins aren't directly transferable to the complementary weighings (because we don't know the total weight), but on a hand-wavy level there should be about the same amount of information. It also iterates through starting weighings in order of the number of coins involved, on the basis that that way it covers dispersed weighings (which hopefully give information about the top end relatively early) without first crawling through a bunch which start with a dense subset at the bottom end.

The MaskRange class is a massive improvement on the earlier version in terms of memory usage, and removes GC from being a bottleneck.

20      [11101001010] 11        1.818182* in 5364 seconds
22      [110110101000] 12       1.833333* in 33116 seconds
24      [1000011001001] 13      1.846154* in 12181 seconds                                                                                                            
26      [100101001100000] 14    1.857143* in 73890 seconds