Omkar_Pradhan_10Feb_Programming Tasks.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 77"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "53\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "\"It is possible to write ten as the sum of primes in exactly five different ways:\n",
    "7 + 3\n",
    "5 + 5\n",
    "5 + 3 + 2\n",
    "3 + 3 + 2 + 2\n",
    "2 + 2 + 2 + 2 + 2\n",
    "What is the first value which can be written as the sum of primes in over five thousand different ways?\"\n",
    "'''\n",
    "primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79] #80 can be presented as 10000 units\n",
    "\n",
    "L, target = 1000, 11\n",
    "while True:\n",
    "    ways = [1] + [0]*target\n",
    "    for p in primes:\n",
    "        for i in range(p, target+1):\n",
    "            ways[i] += ways[i-p]\n",
    "    if ways[target] > L: break    \n",
    "    target += 1\n",
    "    \n",
    "print(target)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 78"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55374\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "\"Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.\n",
    "OOOOO\n",
    "OOOO   O\n",
    "OOO   OO\n",
    "OOO   O   O\n",
    "OO   OO   O\n",
    "OO   O   O   O\n",
    "O   O   O   O   O\n",
    "Find the least value of n for which p(n) is divisible by one million.\"\n",
    "'''\n",
    "#!/usr/bin/env python\n",
    "from itertools import *\n",
    "\n",
    "def pentagonal(n):\n",
    "    return n*(3*n - 1) / 2\n",
    "\n",
    "partitions = {}\n",
    "generalized_pentagonals = sorted(map(pentagonal, list(range(-250, 250))))[1:]\n",
    "def partition(n):\n",
    "    if n <= 1: return 1\n",
    "    if n not in partitions:\n",
    "        signs = cycle([1, 1, -1, -1])\n",
    "        pentagonals = takewhile(lambda p: p <= n, generalized_pentagonals)\n",
    "        partitions[n] = sum(sign * partition(n - p) for sign, p in zip(signs, pentagonals))\n",
    "\n",
    "    return partitions[n]\n",
    "\n",
    "print(next((n for n in count(0) if partition(n) % 1000000 == 0)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "369f2c481f4da34e4445cda3fffd2e751bd1c4d706f27375911949ba6bb62e1c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}