Project Euler Q25 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "830b82ae-eee6-4258-83ed-d28379a8a478",
   "metadata": {},
   "source": [
    "### Q25\n",
    "What is the first term in the Fibonacci sequence to contain 1000 digits?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "cd131292-2bf5-4c03-976c-cae34f2be514",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibonacci(first, second, n_term = False, max_value = False):\n",
    "    result = [first, second]\n",
    "    if not n_term and not max_value:\n",
    "        print(\"At least one of 'n_term','max_value' argument is needed.\")\n",
    "        return\n",
    "    while True:\n",
    "        if n_term and len(result) >= n_term:\n",
    "            break\n",
    "        if max_value and result[-1] > max_value:\n",
    "            result.pop()\n",
    "            break\n",
    "        result.append(result[-1]+result[-2])\n",
    "    return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "72a732bb-975b-49b9-89ca-1c5adefd0f7a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 874 µs, sys: 202 µs, total: 1.08 ms\n",
      "Wall time: 1.08 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "sum(fibonacci(1,1,max_value=10**(1000-1))[-2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "983a8292-4423-4c5a-8bfd-7675ac47ce3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_num_string(num_string_a,num_string_b):\n",
    "    num_digits = 0\n",
    "    if len(num_string_a) >= len(num_string_b):\n",
    "        num_digits = len(num_string_a)\n",
    "        num_string_b = \"0\"*(num_digits-len(num_string_b))+num_string_b\n",
    "    else:\n",
    "        num_digits = len(num_string_b)\n",
    "        num_string_a = \"0\"*(num_digits-len(num_string_a))+num_string_a \n",
    "    sum_digits = [0]*num_digits\n",
    "    carry = 0\n",
    "    for i in range(num_digits)[::-1]:\n",
    "        temp_sum = int(num_string_a[i])+int(num_string_b[i])+carry\n",
    "        sum_digits[i] = temp_sum % 10\n",
    "        carry = temp_sum//10\n",
    "    return ''.join([str(i) for i in [carry]+sum_digits]).lstrip(\"0\")\n",
    "\n",
    "def fibonacci_string_exceed(first, second, n_digits):\n",
    "    result = [str(first), str(second)]\n",
    "    while True:\n",
    "        if len(result[-1]) > n_digits:\n",
    "            return result[-1]\n",
    "        result.append(sum_num_string(result[-1],result[-2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "41a71863-e557-4f35-9465-bf98bc81b34a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 536 ms, sys: 0 ns, total: 536 ms\n",
      "Wall time: 533 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "int(fibonacci_string_exceed('1','1',999))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b09f8c4-2833-49c9-ba2e-27c82eaa60de",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

Loading