{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools\n",
    "from sympy.ntheory.residue_ntheory import primitive_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def has_3AP(p,m,g):\n",
    "    X0 = {pow(g, i, p) for i in range(0, p-m, m) }\n",
    "    X0prime = X0 - set([1]) # remove 1 from X0\n",
    "    gX0 = {(2 - x) % p for x in X0prime}\n",
    "    if bool(X0prime.intersection(gX0)):\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "def psieve():\n",
    "    for n in [2, 3, 5, 7]:\n",
    "        yield n\n",
    "    D = {}\n",
    "    ps = psieve()\n",
    "    next(ps)\n",
    "    p = next(ps)\n",
    "    assert p == 3\n",
    "    psq = p*p\n",
    "    for i in itertools.count(9, 2):\n",
    "        if i in D:      # composite\n",
    "            step = D.pop(i)\n",
    "        elif i < psq:   # prime\n",
    "            yield i\n",
    "            continue\n",
    "        else:           # composite, = p*p\n",
    "            assert i == psq\n",
    "            step = 2*p\n",
    "            p = next(ps)\n",
    "            psq = p*p\n",
    "        i += step\n",
    "        while i in D:\n",
    "            i += step\n",
    "        D[i] = step\n",
    "        # print D\n",
    "        \n",
    "        \n",
    "        \n",
    "def p_m_sieve(m):\n",
    "    primes = psieve()\n",
    "    next(primes)\n",
    "    for p in primes:\n",
    "        if (p-1) % m == 0:\n",
    "            yield p\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "mikerange = range(2,41)\n",
    "\n",
    "with open('3AP.csv', 'a') as f:        \n",
    "    for mike in mikerange:\n",
    "        primes = p_m_sieve(mike)\n",
    "        prime = next(primes)\n",
    "        current_value = has_3AP(prime,mike,primitive_root(prime))\n",
    "        prev_prime = prime\n",
    "        while prime < mike**4 + 5:\n",
    "            # print prime\n",
    "            prev_value, current_value = current_value, has_3AP(prime,mike,primitive_root(prime))\n",
    "            # print prime, current_value\n",
    "            if current_value and not prev_value:\n",
    "                p_under, p_over = prev_prime, prime\n",
    "            prev_prime, prime = prime, next(primes)\n",
    "       \n",
    "        print  (mike, p_under, p_over)\n",
    "        f.write(str(mike) + ', ' + str(p_under) + ', ' + str(p_over) + '\\n')"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}