p1/izzivi/02 nedvoumna stevila/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Izziv: Nedvoumna števila\n",
    "\n",
    "Tale naloga je kar tako, za izziv. Če bo kdo kaj zanimivega počel in oddal, bom(o) komentiral(i). Naloga ni čisto brez matematičnega ozadja, zato predlagam, da jo rešujete brez preveč googlanja; če zgolj vpišete zaporedje v Google, boste hitro izvedeli preveč. Pa brez spoilerjev na forumu, prosim. :)\n",
    "\n",
    "1 in 2 sta nedvoumni števili. 3 = 1 + 2, torej je tudi nedvoumno. 4 je 1 + 3, torej je nedvoumno. 5 pa ni nedvoumno število, ker je enako 1 + 4 in 2 + 3. 6 je nedvoumno, ker je enako 2 + 4 (in ga ne moremo pridobiti na noben drug način -- 3 + 3 ne šteje). 7 ni nedvoumno, ker je enako 1 + 6 in 3 + 4.\n",
    "\n",
    "Število je torej nedvoumno, če ga lahko zapišemo na samo en način kot vsoto dveh nedvoumnih števil. Seznam nedvoumnih števil se tako začne z"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, ...\n",
    "```\n",
    "\n",
    "Izziv: čim hitreje naračunaj vsa nedvoumna števila, manjša od 100 000. V Pythonu. Uporabi, kar hočeš, tudi stvari, ki se jih še nismo učili.\n",
    "\n",
    "Če boste naložili kakšno rešitev, kliknite \"Oddaj\", da bom(o) obveščen(i) o tem in bom(o) pogledal(i), kaj ste počeli."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rešitev\n",
    "\n",
    "Najprej recimo bobu bob in Ulamovim številom [Ulamova števila](https://en.wikipedia.org/wiki/Ulam_number).\n",
    "\n",
    "\n",
    "### Seznami in dve zanki znotraj zanke"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ulam = [1, 2]\n",
    "\n",
    "for n in range(3, 5000):\n",
    "    nacinov = 0\n",
    "    for st1 in ulam:\n",
    "        for st2 in ulam:\n",
    "            if st2 >= st1:\n",
    "                break\n",
    "            elif st1 + st2 == n:\n",
    "                nacinov += 1\n",
    "                break\n",
    "    if nacinov == 1:\n",
    "        ulam.append(n)\n",
    "\n",
    "print(ulam)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V začetku imamo Ulamovi števili 1 in 2. Nato preskušamo vsa števila od 3 do 999 (`for i in range(3, 1000)`). Za vsako bomo preverili, na koliko načinov ga lahko sestavimo. V začetku postavimo `nacinov = 0` in potem gremo prek vseh parov -- `for st1 in ulam` in znotraj tega `for st2 in ulam`. No, ne prek čisto vseh parov. Da bo hitrejše, bomo zahtevali, naj bo drugo število manjše od prvega; če je `st2 >= st1`, bomo z `break` prekinili notranjo zanko. Vsakič, ko opazimo, da se števili seštejeta v `n`, povečamo števec načinov, na katere dobimo `n` -- `nacinov += 1`. Ko je vse prešteto, preverimo, ali smo število dobili le na en način in v tem primeru ga dodamo med Ulamova števila.\n",
    "\n",
    "Tole je bila najpogostejša rešitev - vsaj konceptualno. Namesto zank `for` so mnogi pisali `while` in potem uporabljali indekse. Tudi prav, `for`-a se dotlej niti nismo učili.\n",
    "\n",
    "Čemu služi drugi `break`? Ni potreben, le program pospeši. Ko enkrat vidimo, da smo našli število `st2`, ki se s `st1` sešteje v `n`, nima smisla, da iščemo, ali obstaja še kakšno. Števila v seznamu se ne ponavljajo, torej smemo notranjo zanko mirno prekiniti.\n",
    "\n",
    "Potem pa se domislimo, da nas niti ne zanima, na koliko načinov lahko dobimo posamezno število; če ga lahko dobimo na dva načina, nam je vseeno, ali jih bo na koncu pet ali dvanajst - ali pa bo morda ostalo pri dveh. Zato lahko tudi zunanjo zanko prekinemo, čim `nacinov` doseže 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690, 695, 720, 722, 732, 734, 739, 751, 781, 783, 798, 800, 820, 847, 849, 861, 864, 866, 891, 893, 905, 927, 949, 983, 986, 991, 3, 6, 11, 16, 26, 36, 48, 53, 72, 77, 82, 87, 97, 102, 114, 126, 131, 148, 175, 180, 197, 209, 219, 236, 241, 253, 258, 273, 319, 324, 339, 356, 363, 390, 400, 412, 429, 434, 451, 456, 483, 522, 544, 566, 605, 627, 688, 720, 732, 781, 798, 820, 847, 864, 891, 986, 991]\n"
     ]
    }
   ],
   "source": [
    "for n in range(3, 1000):\n",
    "    nacinov = 0\n",
    "    for st1 in ulam:\n",
    "        for st2 in ulam:\n",
    "            if st2 >= st1:\n",
    "                break\n",
    "            elif st1 + st2 == n:\n",
    "                nacinov += 1\n",
    "                break\n",
    "        if nacinov == 2:\n",
    "            break\n",
    "    if nacinov == 1:\n",
    "        ulam.append(n)\n",
    "        \n",
    "print(ulam)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pomembno je, da se pogoj `if nacinov == 2` nahaja v zunanji zanki `for` in ne notranji. `break` namreč prekine le najbolj notranjo zanko, v kateri se nahaja. V Pythonu ni načina, da bi na najbolj notranje nivoju (znotraj zanke `for st2 in ulam`) prekinili tudi zunanjo zanko (`for st1 in ulam`).\n",
    "\n",
    "Seveda se lahko kdo pritožuje, da je to neroden jezik. Je, to je neroden jezik za pisanje nerodnih programov. :) Poskusimo sprogramirati boljše. In hitrejše.\n",
    "\n",
    "Predtem pa morda poračunajmo, kako počasen je ta program. Tule sem najprej v resnici računal, a potem razmislil, da se boste morda ustrašili, zato naj bo le intuitivno: če imamo zanko, ki se obrne N-krat, znotraj te eno zanko, katere število korakov je sorazmerno številu korakov zunanje zanke, in znotraj te še eno tako, se bo vse skupaj odvrtelo $N\\times N\\times N$-krat. Čas izvajanja programa bo torej sorazmeren kubu, $N^3$.\n",
    "\n",
    "To nam pove, kaj moramo storiti: znebiti se moramo notranje zanke.\n",
    "\n",
    "### Množica in ena zanka znotraj zanke\n",
    "\n",
    "Kaj počne najbolj notranja zanka? Preverja, ali je v seznamu takšno število `st2`, da bo vsota `st1 + st2` enaka `n`. Obrnimo: zanima nas, ali seznam `ulam` vsebuje število `n - st1`.\n",
    "\n",
    "Če vemo kaj o seznamih (če še ne, pa bomo še izvedeli), vemo, da obstaja preprost način, da preverimo, ali le-ta vsebuje neko število."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690, 695, 720, 722, 732, 734, 739, 751, 781, 783, 798, 800, 820, 847, 849, 861, 864, 866, 891, 893, 905, 927, 949, 983, 986, 991]\n"
     ]
    }
   ],
   "source": [
    "ulam = [1, 2]\n",
    "\n",
    "for n in range(3, 1000):\n",
    "    nacinov = 0\n",
    "    for st1 in ulam:\n",
    "        if st1 >= n / 2:\n",
    "            break\n",
    "        if n - st1 in ulam:\n",
    "            nacinov += 1\n",
    "            if nacinov == 2:\n",
    "                break\n",
    "    if nacinov == 1:\n",
    "        ulam.append(n)\n",
    "        \n",
    "print(ulam)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prvi pogoj iz prejšnjega programa, `if st2 >= st1` se je zdaj spremenil v `if st1 >= n / 2`: če je `st1` večji od `n / 2`, bo `st2` manjši - česar pa ne pustimo. Če bi hoteli celoštevilsko deljenje, bi pisali `if st1 >= (n + 1) // 2`, saj `// 2` zaokroža navzdol.\n",
    "\n",
    "Nato z `if n - st1 in ulam` preverimo, ali je med Ulamovimi števili takšno, ki se bo seštelo v `n`.\n",
    "\n",
    "Notranje zanke smo se res znebili, a le navidez. Ko Python preverja pogoj `n - st1 in ulam`, mora iti prek seznama števil ... natančno tako, kot smo počeli v zanki. Zanka torej ostaja, le skrila se je v operator `in`. Program bo sicer hitrejši, saj to, skrito zanko izvede Python, ki je napisan v jeziku C, ki je bistveno hitrejši od Pythona. A hitrost izvajanja še vedno narašča s kubom števila števil.\n",
    "\n",
    "A če hočemo res pospešiti program, bomo namesto seznama uporabili množico."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690]\n"
     ]
    }
   ],
   "source": [
    "ulam = {1, 2}\n",
    "\n",
    "for n in range(3, 10000):\n",
    "    nacinov = 0\n",
    "    for st1 in ulam:\n",
    "        if st1 < n / 2 and n - st1 in ulam:\n",
    "            nacinov += 1\n",
    "            if nacinov == 2:\n",
    "                break\n",
    "    if nacinov == 1:\n",
    "        ulam.add(n)\n",
    "        \n",
    "print(sorted(ulam)[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Spremembe so skoraj kozmetične. Oglate oklepaje so zamenjali zaviti (namesto `[1, 2]` pišemo `{1, 2}`); namesto `ulam.append(n)` imamo `ulam.add(n)`, ker se v množicah piše tako; in namesto `print(ulam)` imamo `print(sorted(ulam))`, ker bodo elementi množice sicer izpisani pomešano. Izpisali pa smo le prvih 100 - da ni preveč.\n",
    "\n",
    "Razlika v hitrosti izvajanja pa je drastična. Kot se bomo učili, Python zdaj v `n - st1 in ulam` ne išče več po množici `ulam`, temveč kar v trenutku ve, ali je iskano število v množici ali ne.\n",
    "\n",
    "Namesto množic bi lahko tu uporabili kar seznam z 10000 elementi. Ali kaj podobnega.\n",
    "\n",
    "Če bi opazovali čas izvajanja tega programa pri različnem številu števil, bi videli, da narašča s kvadratom, saj imamo zdaj le dve gnezdeni zanki. \n",
    "\n",
    "\n",
    "### Slovarji in vsote vnaprej\n",
    "\n",
    "Vsakič, ko bomo odkrili novo Ulamovo število, bomo izračunali vsote tega števila z vsemi že prej znanimi Ulamovimi števili. In šteli, kolikokrat se pojavi katera vsota. `stevec_vsot[100]`, recimo, bo povedal, na koliko načinov se da dobiti vsoto 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690]\n"
     ]
    }
   ],
   "source": [
    "stevec_vsot = [0, 1, 1] + [0] * 999998\n",
    "ulam = [1]\n",
    "\n",
    "for n in range(2, 100001):\n",
    "    if stevec_vsot[n] == 1:\n",
    "        for e in ulam:\n",
    "            if n + e > 1000000:\n",
    "                break\n",
    "            stevec_vsot[n + e] += 1\n",
    "        ulam.append(n)\n",
    "print(ulam[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V začetku vemo, da ne moremo dobiti 0. 1 in 2 dobimo na 1 način. Vsa ostala števila pa, zaenkrat, na 0 načinov. Nato preskušamo števila od 2 naprej. Če je to število možno dobiti na en sam način, izračunamo vsote z vsemi znanimi Ulamovimi števili, in če so te vsote manjše od 100000 (če niso, reč takoj prekinemo), povečamo števec vsot. Nato še dodamo to število med Ulamova.\n",
    "\n",
    "Kot ste opazili, zdaj računamo števila do 100.000. Ker lahko.\n",
    "\n",
    "Še nekoliko hitrejše je tole."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690]\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "pojavitve = defaultdict(int)\n",
    "pojavitve.update({1: 1, 2: 1})\n",
    "ulam = [1]\n",
    "\n",
    "for n in range(2, 100001):\n",
    "    if pojavitve.pop(n, 0) == 1:\n",
    "        for e in ulam:\n",
    "            vsota = e + n\n",
    "            if vsota > 100000:\n",
    "                break\n",
    "            pojavitve[vsota] += 1\n",
    "        ulam.append(n)\n",
    "\n",
    "print(ulam[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Komentiral ne bom preveč. Uporablja defaultdict, ki ga bomo sicer enkrat omenili na predavanjih, vendar bi delovalo enako dobro tudi z običajnim slovarjem. Priznati moram še, da sem `if vsota > 100000: break` ukradel enemu od študentov; meni se to ni zdelo tako zelo pomembno, a seveda je.\n",
    "\n",
    "Kar nekaj študentov je oddalo zelo dobre rešitve, zato raje ne bi našteval imen, da ne bom koga izpustil. Zelo prav pa je, da povem, da je eden od študentov naredil tole odlično rešitev, ki je za tretjino hitrejša od moje. (V resnici je napisal malo drugače, a ideja je ista.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690]\n"
     ]
    }
   ],
   "source": [
    "pojavitve = {1: True, 2: True}\n",
    "ulam = [1]\n",
    "\n",
    "for n in range(2, 100001):\n",
    "    if pojavitve.get(n, False):\n",
    "        for e in ulam:\n",
    "            vsota = e + n\n",
    "            if vsota > 100000:\n",
    "                break\n",
    "            if vsota in pojavitve:\n",
    "                pojavitve[vsota] = False\n",
    "            else:\n",
    "                pojavitve[vsota] = True\n",
    "        ulam.append(n)\n",
    "\n",
    "print(ulam[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Njegova rešitev je podobna moji, le da ne šteje pojavitev temveč v slovar zabeleži `True`, ko vsoto vidi prvič, nato pa `False`. Nenavadno je, da je to toliko hitrejše, saj privarčuje le eno seštevanje in eno primerjavo.\n",
    "\n",
    "### C-jevski kazalci\n",
    "\n",
    "Posebne omembe je vreden tale program enega od študentov iz generacije 19/20."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, 309, 316, 319, 324, 339, 341, 356, 358, 363, 370, 382, 390, 400, 402, 409, 412, 414, 429, 431, 434, 441, 451, 456, 483, 485, 497, 502, 522, 524, 544, 546, 566, 568, 585, 602, 605, 607, 612, 624, 627, 646, 668, 673, 685, 688, 690]\n"
     ]
    }
   ],
   "source": [
    "nums = [1, 2]\n",
    "\n",
    "def findMatches(x):\n",
    "    match = 0 #najdenih parov\n",
    "    l = 0 #levi index\n",
    "    r = len(nums)-1 #desni index\n",
    "    #iteriraj skozi tabelo, ko se 2 števili seštejeta v željeno vrednost, in če povečamo levo število, je vsota kvečjem večja, torej zmanjšamo desno\n",
    "    #če pomanjšamo desno lahko dobimo željeno število kvečjem da povečamo levo \n",
    "    while l < r:\n",
    "        #par najden, nadaljuj z manjšim inkrementom ne večjim kot, če bi premaknili desni index\n",
    "        if nums[l] + nums[r] == x: \n",
    "            match += 1\n",
    "            l += 1\n",
    "        elif nums[l] + nums[r] < x:\n",
    "            l += 1\n",
    "        else:\n",
    "            r -= 1\n",
    "        #čim je najden dodaten par je brezveze iskati dalje\n",
    "        if match > 1:\n",
    "            break\n",
    "\n",
    "    return match\n",
    "\n",
    "for i in range(100000):\n",
    "    if findMatches(i) == 1:\n",
    "        nums.append(i)\n",
    "\n",
    "print(nums[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kudos. Sploh, če povem še, da je dotični napisal to rešitev med predavanji, na telefon. :)\n",
    "\n",
    "Ta rešitev sicer ni najhitrejša v Pythonu (vseeno pa je kar hitra!), saj ne uporablja hitrih podatkovnih struktur (množic, slovarjev), ki so vgrajeni vanj. Pač pa bi bila to zelo dobra rešitev v C-ju. Takole, recimo, bi to izgledalo v C++.\n",
    "\n",
    "```cpp\n",
    "#include <iostream>\n",
    "#include <vector>\n",
    "\n",
    "int main() {\n",
    "    std::vector<int> ulam{1, 2};\n",
    "    ulam.push_back(1);\n",
    "    ulam.push_back(2);\n",
    "    for(auto x = 0; x < 100000; x++) {\n",
    "        auto down = ulam.begin();\n",
    "        auto up = ulam.end();\n",
    "        up--;\n",
    "        int matches = 1;\n",
    "        while (up != down) {\n",
    "            if ((*up + *down == x) && (++matches == 2))\n",
    "                break;\n",
    "            if (*up + *down < x)\n",
    "                down++;\n",
    "            else\n",
    "                up--;\n",
    "        }\n",
    "        if (matches == 1)\n",
    "            ulam.push_back(x);\n",
    "    }\n",
    "\n",
    "    for(auto it = ulam.begin(); it != ulam.end(); it++)\n",
    "        std::cout << *it << ' ';\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Numpy: Python s (skoraj) hitrostjo C-ja\n",
    "\n",
    "`numpy` je knjižnica za Python, ki zna delati s poljubno dimenzionalnimi tabelami poljubnih tipov. Zanke izvaja v C-ju, zato so hitre, kolikor le morejo biti. Konkretno, z njim je mogoče narediti tole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 7  4  7 15]\n"
     ]
    }
   ],
   "source": [
    "# navadno ga uvozimo tako z `import numpy as np`, da lahko potem pišemo kar `np` namesto `numpy`\n",
    "import numpy as np  \n",
    "\n",
    "a = np.array([2, 3, 5, 7])\n",
    "b = np.array([5, 1, 2, 8])\n",
    "print(a + b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ta program sešteje obe tabeli po elementih, zato je rezultat `[7, 4, 7, 15]`. In to je tudi vse, kar potrebujemo za rešitev te naloge.\n",
    "\n",
    "Spodnji program se izvede v desetinki ali dveh, odvisno od hitrosti računalnika."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  1   2   3   4   6   8  11  13  16  18  26  28  36  38  47  48  53  57\n",
      "  62  69  72  77  82  87  97  99 102 106 114 126 131 138 145 148 155 175\n",
      " 177 180 182 189 197 206 209 219 221 236 238 241 243 253 258 260 273 282\n",
      " 309 316 319 324 339 341 356 358 363 370 382 390 400 402 409 412 414 429\n",
      " 431 434 441 451 456 483 485 497 502 522 524 544 546 566 568 585 602 605\n",
      " 607 612 624 627 646 668 673 685 688 690]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "pojavitve = np.zeros(100001, dtype=int)\n",
    "pojavitve[1:3] = 1\n",
    "\n",
    "for n in range(2, 100001):\n",
    "    if pojavitve[n] == 1:\n",
    "        up = min(2 * n, 100000)\n",
    "        pojavitve[n:up] += pojavitve[:up - n]\n",
    "    else:\n",
    "        pojavitve[n] = 0\n",
    "\n",
    "ulam = np.flatnonzero(pojavitve)\n",
    "print(ulam[:100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ideja je praktično enaka kot v onem od gornjih programov, ki je vzdrževal tabelo, na koliko načinov je mogoče sestaviti posamično število (`pojavitve[n]` predstavlja število načinov, na katerega lahko dobimo število `n`) in je ob vsakem novem zanesljivem številu le-tega prištel k vsem doslej znanim zanesljivim številom in povečal ustrezni element tabele. Bistvena razlika je, da se notranja zanka zgodi v numpy-ju. \n",
    "\n",
    "Tabela `pojavitve` v bistvu vsebuje dve različni stvari. Vzemimo nek `n`, recimo 13. V elementih od 0 do 12, tabela `pojavitve[e]` vsebuje `1`, če je število `e` Ulamovo in `0`, če ni. V elementih od 14 naprej pa tabela vsebuje število različnih vsot, na katere lahko pridelamo `i`.\n",
    "\n",
    "Ko pridemo do števila 13, je začetek tabele videti tako:\n",
    "\n",
    "```\n",
    "#0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27\n",
    "[0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]\n",
    "```\n",
    "\n",
    "Pred trinajstim elementom so enice na indeksih 1, 2, 3, 4, 6, 8, 11 -- to so zanesljiva števila. Enica je tudi pri 13, saj lahko 13 naračunamo na en zam način (2 + 11, a to ni pomembno, niti se iz tabele ne vidi). Ostane tabele pove, na koliko načinov lahko naračunamo posamično število. 14 lahko naračunamo na dva načina (3 + 11 in 6 + 8), 15 na enega (4 + 11), 16 pa ne moremo.\n",
    "\n",
    "Zdaj, v tem trenutku, ugotovimo, da je 13 zanesljivo število. Torej je potrebno povečati število načinov, na katere lahko naračunamo 13 + 1, 13 + 2, 13 + 3, 13 + 4, 13 + 6, 13 + 8 ... Z drugimi besedami: povečati je potrebno elemente, ki se nahajajo na indeksu `13 + e`, če je element `pojavitve[e]` enak 1. S tretjimi besedami, sešteti je potrebno tole\n",
    "\n",
    "```\n",
    "# 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27\n",
    "[ 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]\n",
    "+                                       [0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0]\n",
    "=[0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 3, 2, 1, 2, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0]\n",
    "```\n",
    "\n",
    "Po tem, ko dodamo 13, lahko 14 dobimo na tri načine (pridružil se je še 13 + 1), 15 na 2 (dodamo 13 + 2), 16 na enega (13 + 3), 17 na 2 (13 + 4), 18 pa še vedno ne moremo dobiti, saj je `pojavitve[5]` enak 0 (5 ni zanesljivo število).\n",
    "\n",
    "V drugi vrstici je samo za 13 (se pravi: za `n`) elementov zamaknjena prva vrstica. To naredimo približno z\n",
    "\n",
    "```\n",
    "pojavitve[n:] += pojavitve\n",
    "```\n",
    "\n",
    "K vsem elementom od n-tega naprej prištej, kar je v `pojavitve`.\n",
    "\n",
    "To ne bi delovalo, ker tabeli, ki ju seštevamo (po elementih) nista enako dolgi. Zato bi morali napisati\n",
    "\n",
    "```\n",
    "pojavitve[n:] += pojavitve[:-n]\n",
    "```\n",
    "\n",
    "To pomeni, k tabeli, ki se začne pri n-tem elementu, prištej vsebino taiste tabele brez zadnjih n-elementov (a od začetka, seveda).\n",
    "\n",
    "Vendar so v tabeli večinoma ničle. Največje število, ki bi utegnilo še biti v tabeli, je `2 * n`. Torej bi lahko pisali `pojavitve[n: 2 * n]`. Vendar je `2 * n` lahko več od 100000. Zato `up = min(2 * i, 100000)` in prištevamo k `pojavitve[n:up]`.\n",
    "\n",
    "To storimo le, če je `n` zanesljivo število. Če ni, pa je `pojavitve[n]` bodisi 0 (vsote ni mogoče dobiti) ali več kot 1 (dobimo jo lahko na več kot 1 način). V obej primerih nastavimo `pojavitve[n]` na 0, da označimo, da `n` ni zanesljivo število, tako da v naslednjih korakih ne bo prispevalo k število možnih vsot.\n",
    "\n",
    "Program je tako hiter, ker se seštevanje tabel (ki smo ga v tistem od prejšnjih programov, ki je že uporabljal to strategijo \"seštevanja naprej\", izvedli z gnezdeno zanko `for`) dogaja v C-ju. Na mojem, kar starem in počasnem prenosniku potrebuje ta program dve desetinki sekunde. Ekvivalenten program v C-ju potrebuje eno desetinko. Vseeno je to kar odlično.\n",
    "\n",
    "Zanimivo je, kaj se zgodi, če poskusimo desetkrat več števil, torej števila do milijon. Namesto dveh desetink sekunde potrebuje dvajset sekund. To je popolnoma pravilno: še vedno imamo dve gnezdeni zanki (čeprav je ena v Pythonu, ena v C-ju), torej bo za desetkrat večji problem potreboval stokrat več časa.\n",
    "\n",
    "### Matematiki\n",
    "\n",
    "Če hočemo biti še hitrejši, vzamemo hitrejši jezik (Python za take reči ni ravno hiter) ali, predvsem, pogledamo, ali so matematiki odkrili kak trik, ki normalnemu človeku ne bi prišel na misel. Seveda so. [Uživajte v branju](https://pdfs.semanticscholar.org/30a6/3d149c235ca2d90d13cce7bc9d62e9629e3d.pdf)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}