prime_indexed_numbers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Definition\n",
    "\n",
    "Let $\\mathbb{P}$ be the set of all prime numbers.\n",
    "\n",
    "Define the set of prime indexed primes as:\n",
    "\n",
    "$$X = \\{ p \\in \\mathbb{P} | \\exists q \\in \\mathbb{P} \\text{ such that } p = \\mathbb{P}_q\\}$$\n",
    "\n",
    "Where:\n",
    "    $\\mathbb{P}_q$ is the $q^{th}$ prime number.\n",
    "    $p$ ranges over the prime numbers.\n",
    "    $q$ also ranges over the prime numbers.\n",
    "\n",
    "In words, $X$ is the set containing prime number $p$, if and only if, there exists a prime number $q$ such that $p$ is the $q^{th}$ prime number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Task"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Write a function that takes an integer ($n \\ge 1$) as its input and returns ``True`` if the number is prime and ``False`` otherwise.\n",
    "\n",
    "b. Write a function that takes an integer $M$ as its input and prints the set of prime-indexed prime numbers smaller than or equal to $M$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 is not prime\n",
      "2 is prime\n",
      "3 is prime\n",
      "4 is not prime\n",
      "5 is prime\n",
      "6 is not prime\n",
      "7 is prime\n",
      "8 is not prime\n",
      "9 is not prime\n",
      "10 is not prime\n",
      "11 is prime\n",
      "12 is not prime\n",
      "13 is prime\n",
      "14 is not prime\n",
      "15 is not prime\n",
      "16 is not prime\n",
      "17 is prime\n",
      "18 is not prime\n",
      "19 is prime\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "def is_prime(n: int):\n",
    "    if n >= 2:\n",
    "        for i in range(2, int(np.sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return False\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "check_numbers = range(1, 20)\n",
    "for i in check_numbers:\n",
    "    if is_prime(i):\n",
    "        print(f\"{i} is prime\")\n",
    "    else:\n",
    "        print(f\"{i} is not prime\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found    3 at index    2\n",
      "Found    5 at index    3\n",
      "Found   11 at index    5\n",
      "Found   17 at index    7\n",
      "Found   31 at index   11\n",
      "Found   41 at index   13\n",
      "Found   59 at index   17\n",
      "Found   67 at index   19\n",
      "Found   83 at index   23\n",
      "Found  109 at index   29\n",
      "Found  127 at index   31\n",
      "Found  157 at index   37\n",
      "Found  179 at index   41\n",
      "Found  191 at index   43\n",
      "Found  211 at index   47\n",
      "Found  241 at index   53\n",
      "Found  277 at index   59\n",
      "Found  283 at index   61\n",
      "Found  331 at index   67\n",
      "Found  353 at index   71\n",
      "Found  367 at index   73\n",
      "Found  401 at index   79\n",
      "Found  431 at index   83\n",
      "Found  461 at index   89\n",
      "Found  509 at index   97\n",
      "Found  547 at index  101\n",
      "Found  563 at index  103\n",
      "Found  587 at index  107\n",
      "Found  599 at index  109\n",
      "Found  617 at index  113\n",
      "Found  709 at index  127\n",
      "Found  739 at index  131\n",
      "Found  773 at index  137\n",
      "Found  797 at index  139\n",
      "Found  859 at index  149\n",
      "Found  877 at index  151\n",
      "Found  919 at index  157\n",
      "Found  967 at index  163\n",
      "Found  991 at index  167\n"
     ]
    }
   ],
   "source": [
    "def prime_indexed_numbers(M: int):\n",
    "    index = 1\n",
    "    prime_numbers = set()\n",
    "    for number in range(2, M + 1):\n",
    "        if is_prime(number):\n",
    "            if index in prime_numbers:\n",
    "                print(f\"Found {number:4d} at index {index:4d}\")\n",
    "            prime_numbers.add(number)\n",
    "            index += 1\n",
    "            \n",
    "prime_indexed_numbers(1000)"
   ]
  }
 ],
 "metadata": {
  "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.11.5"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}