Working-out for the lowest-entry-not-in-an-arithmetic-sequence with other entries competition

mathsjam-2018-compo-compo-compo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sequences(ns):\n",
    "    \"\"\" \n",
    "        Find an element not in an arithmetic sequence with two other elements.\n",
    "        For each a and b, if b+(a-b) is in the set, then all of a,b and c are ruled out.\n",
    "    \"\"\"\n",
    "    ns = sorted(ns)\n",
    "    bad = set()\n",
    "    for a,i in zip(ns,range(len(ns))):\n",
    "        if a in bad:\n",
    "            continue\n",
    "        for b in ns[i+1:]:\n",
    "            c = 2*b-a\n",
    "            if c in ns:\n",
    "               bad = bad.union([a,b,c]) \n",
    "        if a not in bad:\n",
    "            yield a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import shuffle,choice\n",
    "def test(limit):\n",
    "    \"\"\" When picking 100 numbers in the range 1 to limit, how many are not in an arithmetic sequence?\"\"\"\n",
    "    ns = [choice(range(1,limit+1)) for i in range(100)]\n",
    "    return len(list(sequences(ns)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mean(seq):\n",
    "    seq = list(seq)\n",
    "    return sum(seq)/len(seq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some stats to work out what range of numbers I should pick from to get a good number of not-in-an-arithmetic sequence entries, even if all of them are used"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\t0.23\t0.23\n",
      "150\t0.31\t0.13777777777777778\n",
      "200\t0.5\t0.125\n",
      "250\t0.65\t0.10400000000000001\n",
      "300\t0.9\t0.1\n",
      "350\t0.99\t0.08081632653061224\n",
      "400\t1.3\t0.08125\n",
      "450\t1.56\t0.07703703703703704\n",
      "500\t1.76\t0.0704\n",
      "550\t2.25\t0.0743801652892562\n",
      "600\t2.54\t0.07055555555555555\n",
      "650\t2.82\t0.06674556213017752\n",
      "700\t2.94\t0.06\n",
      "750\t3.28\t0.058311111111111105\n",
      "800\t3.92\t0.06125\n",
      "850\t3.4\t0.047058823529411764\n",
      "900\t4.2\t0.05185185185185186\n",
      "950\t4.57\t0.05063711911357341\n",
      "1000\t5.0\t0.05\n"
     ]
    }
   ],
   "source": [
    "for lim in range(100,1000+1,50):\n",
    "    score = mean(test(lim) for i in range(100))\n",
    "    print('{}\\t{}\\t{}'.format(lim,score,score/(lim/100)**2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pick a set of numbers with more than 1 not-in-a-sequence element, at least one of which is less than 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[266, 96, 248, 213, 429, 61, 390, 44, 374, 276, 91, 111, 282, 70, 437, 18, 137, 354, 204, 352, 102, 387, 68, 297, 488, 436, 387, 312, 417, 367, 392, 359, 231, 199, 193, 2, 387, 362, 70, 69, 340, 15, 128, 256, 456, 205, 35, 164, 312, 283, 171, 90, 474, 493, 356, 171, 45, 234, 128, 234, 153, 68, 348, 461, 210, 219, 377, 351, 472, 108, 320, 9, 463, 376, 492, 234, 66, 455, 193, 335, 148, 413, 152, 202, 298, 225, 195, 478, 67, 176, 45, 282, 9, 193, 335, 335, 234, 205, 128, 9, 276]\n",
      "101\n",
      "[15, 374, 437, 461, 488]\n",
      "80\n"
     ]
    }
   ],
   "source": [
    "best = None\n",
    "while True:\n",
    "    ns = [choice(range(1,500)) for i in range(90)]\n",
    "    ns = ns + [choice(ns) for i in range(11)]\n",
    "    nons = list(sequences(ns))\n",
    "    if len(nons)>1 and min(nons)<100:\n",
    "        print(ns)\n",
    "        print(len(ns))\n",
    "        print(nons)\n",
    "        print(len(set(ns)))\n",
    "        best = ns\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make the PDFs for the entry sheets, based on the template"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "import subprocess\n",
    "root = '/home/christian/Documents/mathsjam-2018-compo-compo-compo'\n",
    "fname = 'mathsjam-2018-compo-compo-compo.svg'\n",
    "os.chdir(root)\n",
    "with open(fname) as f:\n",
    "    body = f.read()\n",
    "for n in best:\n",
    "    out = body.replace('>789<','>{}<'.format(n))\n",
    "    with open('thing.svg','w') as f:\n",
    "        f.write(out)\n",
    "    subprocess.call(['inkscape','thing.svg','--export-pdf=entry-{}.pdf'.format(n)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "collect all the entry PDFs into one file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shuffle(best)\n",
    "subprocess.call(['pdftk']+['entry-{}.pdf'.format(n) for n in best]+['cat','output','compo.pdf'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are the numbers that were actually entered"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-298, 15, 312, 387, 413, 455, 488]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entries = \"\"\"\n",
    "-298\n",
    "128\n",
    "128\n",
    "312\n",
    "276\n",
    "493\n",
    "9\n",
    "356\n",
    "108\n",
    "362\n",
    "67\n",
    "199\n",
    "225\n",
    "377\n",
    "15\n",
    "202\n",
    "283\n",
    "335\n",
    "152\n",
    "256\n",
    "91\n",
    "68\n",
    "387\n",
    "213\n",
    "231\n",
    "392\n",
    "354\n",
    "195\n",
    "66\n",
    "164\n",
    "205\n",
    "18\n",
    "90\n",
    "359\n",
    "193\n",
    "171\n",
    "35\n",
    "488\n",
    "45\n",
    "69\n",
    "111\n",
    "137\n",
    "193\n",
    "102\n",
    "455\n",
    "68\n",
    "2\n",
    "234\n",
    "335\n",
    "413\n",
    "9\n",
    "210\n",
    "204\n",
    "297\n",
    "45\n",
    "70\n",
    "193\n",
    "\"\"\"\n",
    "entries = [int(x) for x in entries.strip().split('\\n')]\n",
    "list(sequences(entries))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "57"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(entries)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}