An optimization challenge with strange coins You have n coins which each weigh either -1  or 1. Each is labelled from 0 to n-1 so you can tell the coins apart.  You have one (magic) weighing device as well. At the first turn you can put as many coins as you like on the weighing device which is able to measure both negative and positive weights and it will tell you exactly how much they weigh.

However, there is something really strange about the weighing device.  If you put coins x_1, x_2, ..., x_j on the device the first time, then the next time you have to put coins (x_1+1), (x_2+1) , ..., (x_j+1) on the scale with the exception that you of course can't put on a coin numbered higher than n-1.   Not only that, for every new weighing you get to choose if you also want to put coin 0 on the scale. 


  Under this rule, what is the smallest number of weighings that will always tell you
  exactly which coins weigh 1 and which weigh -1?


Clearly you could just put coin 0 on the device in the first turn and then it would take exactly n weighings to solve the problem.

Languages and libraries

You can use any language or library you like (that wasn't designed for this challenge). However, I would like to be able to test your code if possible so if you can provide clear instructions for how to run it in Ubuntu that would be very much appreciated.

Score

For a given n your score is n divided by the number of weighings you need in the worst case. Higher scores are therefore better.  There is no input to this puzzle but your goal is to find an n for which you can get the highest score.

If there is a tie, the first answer wins.  In the extremely unlikely situation where someone finds a way to get an infinite score, that person wins immediately.

Task

Your task is simply to write code that gets the highest score.  Your code will have to both choose an n cleverly and then also optimize the number of weighings for that n.

Leading entries


4/3 7/5 in Python by Sarge Borsch
26/14 in Java by Peter Taylor
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