Build a pair of spies that will throw stones into a river Recently at the newly released Puzzling.SE, there was a problem about spies throwing stones into a river that was actually quite challenging:

Two spies must pass each other two secret numbers (one number per spy), unnoticed by their enemies. They have agreed on a method for doing this using only 26 indistinguishable stones in advance.
They meet at a river, where there is a pile of 26 stones. Starting with the first spy, they take turns throwing a group of stones into the river: the first spy throws some number of stones, then the second one, then the first one again...
Each spy must throw at least one stone on his turn, until all the stones are gone.
They observe all throws and diverge when there are no more stones. They keep silence all the time and no information is exchanged except number of stones thrown at each turn.
How can they exchange the numbers successfully if the numbers can be from 1 to M?

Your task is to build a pair of programs, spy1 and spy2, that can solve this problem for the highest possible M.
Your programs will each take a number from 1 to your chosen M as input. Then, spy1 will output a number representing the number of stones it throws into the river, which will be input to spy2 which will also output a number to be input to spy1, and so on until the numbers output add up to 26. At the end of throwing, each program will output the number it believes the other program had, which must match the number that was actually input to the other program.
Your program must work for all possible ordered pairs of numbers (i, j) where both i and j can vary from 1 to M.
The program that works for the largest M will be the winner, with the first answer to be posted breaking a tie. Additionally, I will award a +100 reputation bounty to the first solution that is proven to work for M &gt;= 2286, and +300 to the first solution that is proven to work for M &gt;= 2535.
C#, M = 2535

This implements* the system which I described mathematically on the thread which provoked this contest. I claim the 300 rep bonus. The program self-tests if you run it either without command-line arguments or with --test as a command-line argument; for spy 1, run with --spy1, and for spy 2 with --spy2. In each case it takes the number which I should communicate from stdin, and then does the throws via stdin and stdout.

* Actually, I've found an optimisation which makes a massive difference (from several minutes to generate the decision tree, to less than a second); the tree which it generates is fundamentally the same, but I'm still working on a proof of that. If you want a direct implementation of the system which I described elsewhere, see revision 2, although you might want to backport the extra logging from Main and the better inter-thread comms from TestSpyIO.

If you want a test case which completes in less than a minute, change N to 16 and M to 87.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading;

namespace CodeGolf
{
    internal class Puzzle625
    {
        public static void Main(string[] args)
        {
            const int N = 26;
            const int M = 2535;

            var root = BuildDecisionTree(N);

            if (args.Length == 0 || args[0] == "--test")
            {
                DateTime startUtc = DateTime.UtcNow;
                Console.WriteLine("Built decision tree in {0}", DateTime.UtcNow - startUtc);
                startUtc = DateTime.UtcNow;

                int ok = 0;
                int fail = 0;
                for (int i = 1; i &lt;= M; i++)
                {
                    for (int j = 1; j &lt;= M; j++)
                    {
                        if (Test(i, j, root)) ok++;
                        else fail++;
                    }
                    double projectedTimeMillis = (DateTime.UtcNow - startUtc).TotalMilliseconds * M / i;
                    Console.WriteLine("Interim result: ok = {0}, fail = {1}, projected test time {2}", ok, fail, TimeSpan.FromMilliseconds(projectedTimeMillis));
                }
                Console.WriteLine("All tested: ok = {0}, fail = {1}, in {2}", ok, fail, DateTime.UtcNow - startUtc);
                Console.ReadKey();
            }
            else if (args[0] == "--spy1")
            {
                new Spy(new ConsoleIO(), root, true).Run();
            }
            else if (args[0] == "--spy2")
            {
                new Spy(new ConsoleIO(), root, false).Run();
            }
            else
            {
                Console.WriteLine("Usage: Puzzle625.exe [--test|--spy1|--spy2]");
            }
        }

        private static bool Test(int i, int j, Node root)
        {
            TestSpyIO io1 = new TestSpyIO("Spy 1");
            TestSpyIO io2 = new TestSpyIO("Spy 2");
            io1.Partner = io2;
            io2.Partner = io1;

            // HACK! Prime the input
            io2.Output(i);
            io1.Output(j);

            Spy spy1 = new Spy(io1, root, true);
            Spy spy2 = new Spy(io2, root, false);

            Thread th1 = new Thread(spy1.Run);
            Thread th2 = new Thread(spy2.Run);
            th1.Start();
            th2.Start();

            th1.Join();
            th2.Join();

            // Check buffer contents. Spy 2 should output spy 1's value, so it's lurking in io1, and vice versa.
            return io1.Input() == i &amp;&amp; io2.Input() == j;
        }

        private static Node BuildDecisionTree(int numStones)
        {
            NodeValue[] trees = new NodeValue[] { NodeValue.Trivial };
            for (int k = 2; k &lt;= numStones; k++)
            {
                int[] prev = trees.Select(nv =&gt; nv.Y).ToArray();
                List&lt;int&gt; row = new List&lt;int&gt;(prev);
                int cap = prev.Length;
                for (int i = 1; i &lt;= prev[0]; i++)
                {
                    while (prev[cap - 1] &lt; i) cap--;
                    row.Add(cap);
                }

                int[] next = row.OrderByDescending(x =&gt; x).ToArray();
                NodeValue[] nextTrees = new NodeValue[next.Length];
                nextTrees[0] = trees.Last().Reverse();
                for (int i = 1; i &lt; next.Length; i++)
                {
                    int cp = next[i] - 1;
                    nextTrees[i] = trees[cp].Combine(trees[i - prev[cp]]);
                }

                trees = nextTrees;
            }

            NodeValue best = trees.MaxElement(v =&gt; Math.Min(v.X, v.Y));
            return BuildDecisionTree(numStones, best, new Dictionary&lt;Pair&lt;int, NodeValue&gt;, Node&gt;());
        }

        private static Node BuildDecisionTree(int numStones, NodeValue val, IDictionary&lt;Pair&lt;int, NodeValue&gt;, Node&gt; cache)
        {
            // Base cases
            // NB We might get passed val null with 0 stones, so we hack around that
            if (numStones == 0) return new Node(NodeValue.Trivial, new Node[0]);

            // Cache
            Pair&lt;int, NodeValue&gt; key = new Pair&lt;int, NodeValue&gt;(numStones, val);
            Node node;
            if (cache.TryGetValue(key, out node)) return node;

            // The pair-of-nodes construction is based on a bijection between
            //     $\prod_{i&lt;k} T_i \cup \{(\infty, 0)\}$
            // and
            //     $(T_{k-1} \cup \{(\infty, 0)\}) \times \prod_{i&lt;k-1} T_i \cup \{(\infty, 0)\}$

            // val.Left represents the element of $T_{k-1} \cup \{(\infty, 0)\}$ (using null for the $(\infty, 0)$)
            // and val.Right represents $\prod_{i&lt;k-1} T_i \cup \{(\infty, 0)\}$ by bijection with $T_{k-1} \cup \{(\infty, 0)\}$.
            // so val.Right.Left represents the element of $T_{k-2}$ and so on.
            // The element of $T_{k-i}$ corresponds to throwing $i$ stones.
            Node[] children = new Node[numStones];
            NodeValue current = val;
            for (int i = 0; i &lt; numStones &amp;&amp; current != null; i++)
            {
                children[i] = BuildDecisionTree(numStones - (i + 1), current.Left, cache);
                current = current.Right;
            }
            node = new Node(val, children);

            // Cache
            cache[key] = node;
            return node;
        }

        class Pair&lt;TFirst, TSecond&gt;
        {
            public readonly TFirst X;
            public readonly TSecond Y;

            public Pair(TFirst x, TSecond y)
            {
                this.X = x;
                this.Y = y;
            }

            public override string ToString()
            {
                return string.Format("({0}, {1})", X, Y);
            }

            public override bool Equals(object obj)
            {
                Pair&lt;TFirst, TSecond&gt; other = obj as Pair&lt;TFirst, TSecond&gt;;
                return other != null &amp;&amp; object.Equals(other.X, this.X) &amp;&amp; object.Equals(other.Y, this.Y);
            }

            public override int GetHashCode()
            {
                return X.GetHashCode() + 37 * Y.GetHashCode();
            }
        }

        class NodeValue : Pair&lt;int, int&gt;
        {
            public readonly NodeValue Left;
            public readonly NodeValue Right;

            public static NodeValue Trivial = new NodeValue(1, 1, null, null);

            private NodeValue(int x, int y, NodeValue left, NodeValue right) : base(x, y)
            {
                this.Left = left;
                this.Right = right;
            }

            public NodeValue Reverse()
            {
                return new NodeValue(Y, X, this, null);
            }

            public NodeValue Combine(NodeValue other)
            {
                return new NodeValue(other.X + Y, Math.Min(other.Y, X), this, other);
            }
        }

        class Node
        {
            public readonly NodeValue Value;
            private readonly Node[] _Children;

            public Node this[int n]
            {
                get { return _Children[n]; }
            }

            public int RemainingStones
            {
                get { return _Children.Length; }
            }

            public Node(NodeValue value, IEnumerable&lt;Node&gt; children)
            {
                this.Value = value;
                this._Children = children.ToArray();
            }
        }

        interface SpyIO
        {
            int Input();
            void Output(int i);
        }

        // TODO The inter-thread communication here can almost certainly be much better
        class TestSpyIO : SpyIO
        {
            private object _Lock = new object();
            private int? _Buffer;
            public TestSpyIO Partner;
            public readonly string Name;

            internal TestSpyIO(string name)
            {
                this.Name = name;
            }

            public int Input()
            {
                lock (_Lock)
                {
                    while (!_Buffer.HasValue) Monitor.Wait(_Lock);

                    int rv = _Buffer.Value;
                    _Buffer = null;
                    Monitor.PulseAll(_Lock);
                    return rv;
                }
            }

            public void Output(int i)
            {
                lock (Partner._Lock)
                {
                    while (Partner._Buffer.HasValue) Monitor.Wait(Partner._Lock);
                    Partner._Buffer = i;
                    Monitor.PulseAll(Partner._Lock);
                }
            }
        }

        class ConsoleIO : SpyIO
        {
            public int Input()
            {
                return Convert.ToInt32(Console.ReadLine());
            }

            public void Output(int i)
            {
                Console.WriteLine("{0}", i);
            }
        }

        class Spy
        {
            private readonly SpyIO _IO;
            private Node _Node;
            private bool _MyTurn;

            internal Spy(SpyIO io, Node root, bool isSpy1)
            {
                this._IO = io;
                this._Node = root;
                this._MyTurn = isSpy1;
            }

            internal void Run()
            {
                int myValue = _IO.Input() - 1;
                int hisValue = 1;

                bool myTurn = _MyTurn;
                Node n = _Node;
                while (n.RemainingStones &gt; 0)
                {
                    if (myTurn)
                    {
                        if (myValue &gt;= n.Value.X) throw new Exception("Internal error");
                        for (int i = 0; i &lt; n.RemainingStones; i++)
                        {
                            // n[i] allows me to represent n[i].Y values: 0 to n[i].Y - 1
                            if (myValue &lt; n[i].Value.Y)
                            {
                                _IO.Output(i + 1);
                                n = n[i];
                                break;
                            }
                            else myValue -= n[i].Value.Y;
                        }
                    }
                    else
                    {
                        int thrown = _IO.Input();
                        for (int i = 0; i &lt; thrown - 1; i++)
                        {
                            hisValue += n[i].Value.Y;
                        }
                        n = n[thrown - 1];
                    }

                    myTurn = !myTurn;
                }

                _IO.Output(hisValue);
            }
        }
    }

    static class LinqExt
    {
        // I'm not sure why this isn't built into Linq.
        public static TElement MaxElement&lt;TElement&gt;(this IEnumerable&lt;TElement&gt; e, Func&lt;TElement, int&gt; f)
        {
            int bestValue = int.MinValue;
            TElement best = default(TElement);
            foreach (var elt in e)
            {
                int value = f(elt);
                if (value &gt; bestValue)
                {
                    bestValue = value;
                    best = elt;
                }
            }
            return best;
        }
    }
}


Instructions for Linux users

You'll need mono-csc to compile (on Debian-based systems, it's in the mono-devel package) and mono to run (mono-runtime package). Then the incantations are

mono-csc -out:codegolf31673.exe codegolf31673.cs
mono codegolf31673.exe --test


etc.