34.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5e9e39b6-62af-42d3-ba53-ba368db775cd",
   "metadata": {},
   "source": [
    "# Digit Factorials"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e47b4c0-f1e8-4f82-95b0-d71247fc043f",
   "metadata": {},
   "source": [
    "## Problem 34"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48886304-c49b-4790-860c-38607b14e34f",
   "metadata": {},
   "source": [
    "145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. As 1! = 1 and 2! = 2 are not sums they are not included.\n",
    "\n",
    "Find the sum of all numbers which are equal to the sum of the factorial of their digits."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d051f73c-ed2a-49c5-ad39-4c7cb5f3ee18",
   "metadata": {},
   "source": [
    "### Solution\n",
    "The difficulty of this task is to find the upper bound for checking if numbers are curious."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13ee0610-dfc6-4c00-aa3c-a8bb2729866a",
   "metadata": {},
   "source": [
    "Let's first create a function calculating sum of factorials of digits of any number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7082ae33-eda0-40c9-8d2d-1fbd29a124a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function calculating factorial\n",
    "def factorial(n):\n",
    "    if n < 0:\n",
    "        raise Exception(\"Value must be non-negative\")\n",
    "    factorial_n = 1\n",
    "    for i in range(1, n+1):\n",
    "        factorial_n *= i\n",
    "    return factorial_n\n",
    "'''\n",
    "Alternatively, use Python library:\n",
    "import math\n",
    "math.factorial(n)\n",
    "'''\n",
    "\n",
    "# Hash table with a factorial of digits 1-9 - to save computing time\n",
    "digit_factorials = {i: factorial(i) for i in range(10)}\n",
    "\n",
    "# Function calculating sum of digit factorials\n",
    "def factorial_sum(n):\n",
    "    return sum(digit_factorials[int(digit)] for digit in str(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "150068d8-9ad4-40af-a7cb-918dac3007ac",
   "metadata": {},
   "source": [
    "Now, let's check maximum value of sums of digit factorials for numbers with 2, 3, 4, ..., 10 digits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "eca4e478-6674-4b87-a572-da602ef03fa5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max sums of digit factorials for max 1, 2, 3..., 10-digit numbers:\n",
      "{1: 362880, 2: 725760, 3: 1088640, 4: 1451520, 5: 1814400, 6: 2177280, 7: 2540160, 8: 2903040, 9: 3265920, 10: 3628800}\n",
      "\n",
      "Therefore, max lengths of sums of digit factorials for 1, 2, 3..., 10-digit numbers are:\n",
      "{1: 6, 2: 6, 3: 7, 4: 7, 5: 7, 6: 7, 7: 7, 8: 7, 9: 7, 10: 7}\n"
     ]
    }
   ],
   "source": [
    "# Generate max number for each length (1 to 10 digits)\n",
    "max_digits_nums = [(10 ** k) - 1 for k in range(1, 11)]  # 9, 99, 999, ..., 9999999999\n",
    "\n",
    "# Find sum of digit factorials for max numbers with 1, 2, 3, ..., 10 digits\n",
    "max_factorial_sums = {len(str(n)): factorial_sum(n) for n in max_digits_nums}\n",
    "print(\"Max sums of digit factorials for max 1, 2, 3..., 10-digit numbers:\")\n",
    "print(max_factorial_sums)\n",
    "\n",
    "# Calculate number of digits for each factorial sum and compare lengths\n",
    "lengths_factorial_sums = {n: len(str(factorial_sum)) for n, factorial_sum in max_factorial_sums.items()}\n",
    "print(\"\\nTherefore, max lengths of sums of digit factorials for 1, 2, 3..., 10-digit numbers are:\")\n",
    "print(lengths_factorial_sums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "826323f6-776d-443e-b159-7643ae29ce78",
   "metadata": {},
   "source": [
    "Since for > 8-digit numbers we can only construct sum of digit factorials which is max 7-digit long, the upper bound for finding curious numbers is the max factorial sum for number with 7-digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f2adbe87-5c2b-4f00-9862-607af19289df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2540160\n"
     ]
    }
   ],
   "source": [
    "upper_bound = max_factorial_sums[7]\n",
    "print(upper_bound)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dccd78e3-00ea-49c7-92a7-c777461a13a0",
   "metadata": {},
   "source": [
    "Having established the upper bound = 2540160, let's the sum of all curious numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0cb057c5-70c4-4471-9fbf-10dbf6348dc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function for checking computing time\n",
    "import time\n",
    "\n",
    "# Function to calculate execution time\n",
    "def compute_time(func):\n",
    "    start_time = time.time()\n",
    "    result = func()\n",
    "    end_time = time.time()\n",
    "    total_time = end_time - start_time\n",
    "    return result, total_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "8cbff598-0c87-4c0a-91ce-f52944b8543e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your main function that finds curious numbers\n",
    "def find_curious_numbers():\n",
    "    curious_nums = {factorial_sum(n) for n in range(3, upper_bound + 1) if factorial_sum(n) == n}\n",
    "    all_curious_nums_sum = sum(curious_nums)\n",
    "    return curious_nums, all_curious_nums_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4c4bd88e-74d7-4341-84ad-4ec29185cbda",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The set of all curious numbers is: {145, 40585} and its sum is 40730.\n",
      "Computation time: 3.58 s\n"
     ]
    }
   ],
   "source": [
    "# Call compute_time to measure the execution of find_curious_numbers\n",
    "result, elapsed_time = compute_time(find_curious_numbers)\n",
    "\n",
    "# Unpack the results\n",
    "curious_nums, all_curious_nums_sum = result\n",
    "\n",
    "# Print the results\n",
    "print(f\"The set of all curious numbers is: {curious_nums} and its sum is {all_curious_nums_sum}.\")\n",
    "print(f\"Computation time: {elapsed_time:.2f} s\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2cdac169-98f1-4974-9b9c-32fc86ba0518",
   "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.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}