{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Goulib](../notebook.ipynb).math2\n",
    "more math, without numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Goulib.notebook import * #useless here for now\n",
    "from Goulib.math2 import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vectors and Matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "50"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v1=[1,2,3]\n",
    "v2=[7,8,9]\n",
    "dot(v1,v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[14, 38, 50]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m1=[[1,2,3],[5,6,7],[7,8,9]]\n",
    "dot(m1,v1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[14, 38, 50], [38, 110, 146], [50, 146, 194]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m2=transpose(m1)\n",
    "dot(m1,m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1.0, -2.0)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quad(1,3,2) # solves x^2+3*x+2 = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((-1+1.4142135623730951j), (-1-1.4142135623730951j))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quad(1,2,3,allow_complex=True) # solves x^2+2*x+3 = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1431655765 -1431655766]\n",
      " [ 1431655765  1431655766]]\n",
      "[[845100400152152934331135470251, 845100400152152934331135470250], [422550200076076467165567735125, 422550200076076467165567735126]]\n"
     ]
    }
   ],
   "source": [
    "# in fact numpy.linalg.matrix_power has a bug for large powers\n",
    "# https://github.com/numpy/numpy/issues/5166\n",
    "import numpy as np\n",
    "print(np.linalg.matrix_power([[1,2],[1,0]],100))\n",
    "\n",
    "#but Goulib.math2.matrix_power is correct:\n",
    "print(matrix_power([[1,2],[1,0]],100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integer sequences\n",
    "see [OEIS](../examples/oeis.ipynb) example with many sequences calculated from math2 functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "209783453"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibonacci(int(1E18),1000000007) # 1'000'000'000'000'000'000-th fibonacci number almost instantaneously"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Number Theory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "151"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(163231, 152057, 135749) # gcd of n numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7, -112399, 10282, True)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#extended GCD\n",
    "#https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm\n",
    "x,y=158179,1729154\n",
    "gcd,a,b=xgcd(x,y)\n",
    "gcd,a,b, a*x+b*y==gcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes(10) # n first primes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,\n",
       " 3,\n",
       " 5,\n",
       " 7,\n",
       " 11,\n",
       " 13,\n",
       " 17,\n",
       " 19,\n",
       " 23,\n",
       " 29,\n",
       " 31,\n",
       " 37,\n",
       " 41,\n",
       " 43,\n",
       " 47,\n",
       " 53,\n",
       " 59,\n",
       " 61,\n",
       " 67,\n",
       " 71,\n",
       " 73,\n",
       " 79,\n",
       " 83,\n",
       " 89,\n",
       " 97,\n",
       " 101,\n",
       " 103,\n",
       " 107,\n",
       " 109,\n",
       " 113,\n",
       " 127,\n",
       " 131,\n",
       " 137,\n",
       " 139,\n",
       " 149,\n",
       " 151,\n",
       " 157,\n",
       " 163,\n",
       " 167,\n",
       " 173,\n",
       " 179,\n",
       " 181,\n",
       " 191,\n",
       " 193,\n",
       " 197,\n",
       " 199,\n",
       " 211,\n",
       " 223,\n",
       " 227,\n",
       " 229,\n",
       " 233,\n",
       " 239,\n",
       " 241,\n",
       " 251,\n",
       " 257,\n",
       " 263,\n",
       " 269,\n",
       " 271,\n",
       " 277,\n",
       " 281,\n",
       " 283,\n",
       " 293,\n",
       " 307,\n",
       " 311,\n",
       " 313,\n",
       " 317,\n",
       " 331,\n",
       " 337,\n",
       " 347,\n",
       " 349,\n",
       " 353,\n",
       " 359,\n",
       " 367,\n",
       " 373,\n",
       " 379,\n",
       " 383,\n",
       " 389,\n",
       " 397,\n",
       " 401,\n",
       " 409,\n",
       " 419,\n",
       " 421,\n",
       " 431,\n",
       " 433,\n",
       " 439,\n",
       " 443,\n",
       " 449,\n",
       " 457,\n",
       " 461,\n",
       " 463,\n",
       " 467,\n",
       " 479,\n",
       " 487,\n",
       " 491,\n",
       " 499,\n",
       " 503,\n",
       " 509,\n",
       " 521,\n",
       " 523,\n",
       " 541,\n",
       " 547,\n",
       " 557,\n",
       " 563,\n",
       " 569,\n",
       " 571,\n",
       " 577,\n",
       " 587,\n",
       " 593,\n",
       " 599,\n",
       " 601,\n",
       " 607,\n",
       " 613,\n",
       " 617,\n",
       " 619,\n",
       " 631,\n",
       " 641,\n",
       " 643,\n",
       " 647,\n",
       " 653,\n",
       " 659,\n",
       " 661,\n",
       " 673,\n",
       " 677,\n",
       " 683,\n",
       " 691,\n",
       " 701,\n",
       " 709,\n",
       " 719,\n",
       " 727,\n",
       " 733,\n",
       " 739,\n",
       " 743,\n",
       " 751,\n",
       " 757,\n",
       " 761,\n",
       " 769,\n",
       " 773,\n",
       " 787,\n",
       " 797,\n",
       " 809,\n",
       " 811,\n",
       " 821,\n",
       " 823,\n",
       " 827,\n",
       " 829,\n",
       " 839,\n",
       " 853,\n",
       " 857,\n",
       " 859,\n",
       " 863,\n",
       " 877,\n",
       " 881,\n",
       " 883,\n",
       " 887,\n",
       " 907,\n",
       " 911,\n",
       " 919,\n",
       " 929,\n",
       " 937,\n",
       " 941,\n",
       " 947,\n",
       " 953,\n",
       " 967,\n",
       " 971,\n",
       " 977,\n",
       " 983,\n",
       " 991,\n",
       " 997]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sieve(50) # primes up to n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_prime(4547337172376300111955330758342147474062293202868155909489)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 3, 43]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(prime_factors(1548))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 2), (3, 2), (43, 1)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(factorize(1548)) # group prime factors in a^b tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 6, 9, 12, 18, 36, 43, 86, 129, 172, 258, 387, 516, 774, 1548]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(list(divisors(1548)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2504730781961"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from Goulib.itertools2 import first\n",
    "first(filter(is_pandigital,fibonacci_gen())) #nice, isn't it ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distances and Norms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "levenshtein('hello','world')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sets_levenshtein(set('hello'),set('world'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Misc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'one thousand five hundred and forty-eight'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_cardinal_name(1548)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}