euler_625_v2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from eulerlib.numtheory import gcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_gcds(N):\n",
    "    gcds = np.zeros((N,N), dtype=int)\n",
    "    for j in xrange(1,N+1):\n",
    "        for i in xrange(1,j+1):\n",
    "            gcds[i-1,j-1] = gcd(i,j)\n",
    "    return gcds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1,2,4,6,10,12,18,22,28,32,42,46,58,64,72,80,96,102,120,128\n",
      "2 0,1,1,2,2,4,4,6,6,10,10,12,12,18,18,22,22,28,28,32\n",
      "3 0,0,1,1,1,2,2,2,4,4,4,6,6,6,10,10,10,12,12,12\n",
      "4 0,0,0,1,1,1,1,2,2,2,2,4,4,4,4,6,6,6,6,10\n",
      "5 0,0,0,0,1,1,1,1,1,2,2,2,2,2,4,4,4,4,4,6\n",
      "6 0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,4,4,4\n",
      "7 0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2\n",
      "8 0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2\n",
      "9 0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2\n",
      "10 0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2\n"
     ]
    }
   ],
   "source": [
    "num_terms = 20\n",
    "for j in xrange(1, 11):\n",
    "    counts = []\n",
    "    for N in xrange(1,num_terms+1):\n",
    "        gcds = all_gcds(N)\n",
    "        counts.append(np.sum(gcds==j))\n",
    "    print j, ','.join(map(str, counts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_terms = 10**3\n",
    "counts = []\n",
    "for N in xrange(1,num_terms+1):\n",
    "    gcds = all_gcds(N)\n",
    "    counts.append(np.sum(gcds==1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def seq_large_n(n):\n",
    "    return 3 * n**2 / np.pi**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "30.3963550927\n",
      "32\n",
      "100\n",
      "3039.63550927\n",
      "3044\n",
      "1000\n",
      "303963.550927\n",
      "304192\n"
     ]
    }
   ],
   "source": [
    "for p in xrange(1,4):\n",
    "    n = 10**p\n",
    "    print n\n",
    "    print seq_large_n(n)\n",
    "    print counts[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def a(k, n):\n",
    "    return counts[n/k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "122\n"
     ]
    }
   ],
   "source": [
    "total = 0\n",
    "for k in xrange(1,11):\n",
    "    total += k * a(k,10)\n",
    "print total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}