{ "metadata": { "name": "", "signature": "sha256:13a32a490a3f284eb7f7cab61e955ad3c4c61b5072279005b85eef93c65e18c1" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "#Gaps in prime powers\n", "## David Radcliffe\n", "\n", "A *prime power* is a number of the form $p^k$ where $p$ is prime and $k \\ge 1$. We say that two prime powers are *consecutive* if there exists no other prime power between them.\n", "\n", "For each positive integer $k$, let $a(k)$ be the least integer $N$ so that $N$ and $N+k$ are consecutive prime powers, if one exists.\n", "\n", "This Python script computes all values of $a(k)$ so that $a(k) + k < 10^9$. The prime powers are stored in a min-heap and generated as needed." ] }, { "cell_type": "code", "collapsed": false, "input": [ "from sympy import primerange\n", "from heapq import heappush, heappop\n", "\n", "top = 10**9\n", "heap = [(3, 3), (4, 2)]\n", "last = 2\n", "primes = primerange(5, top)\n", "seen = {}\n", "\n", "while heap:\n", " n, p = heappop(heap)\n", " gap = n - last\n", " if not (gap in seen):\n", " seen[gap] = last\n", " last = n\n", " m = n * p\n", " if m < top:\n", " heappush(heap, (m, p))\n", " if n == p:\n", " try:\n", " m = primes.next()\n", " if m < top:\n", " heappush(heap, (m, m))\n", " except:\n", " pass\n", "\n", "for x, y in sorted(seen.items()):\n", " print \"a(%d) = %d\" % (x, y)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "a(1) = 2\n", "a(2) = 5\n", "a(3) = 13\n", "a(4) = 19\n", "a(5) = 32\n", "a(6) = 53\n", "a(7) = 1024\n", "a(8) = 89\n", "a(9) = 512\n", "a(10) = 139\n", "a(11) = 536870912\n", "a(12) = 199\n", "a(14) = 293\n", "a(15) = 65521\n", "a(16) = 1831\n", "a(17) = 8192\n", "a(18) = 1069\n", "a(20) = 887\n", "a(21) = 524288\n", "a(22) = 1129\n", "a(24) = 4177\n", "a(26) = 2477\n", "a(27) = 16384\n", "a(28) = 2971\n", "a(29) = 131072\n", "a(30) = 1331\n", "a(32) = 5591\n", "a(34) = 8467\n", "a(35) = 33554432\n", "a(36) = 9551\n", "a(38) = 30593\n", "a(39) = 33554393\n", "a(40) = 19333\n", "a(42) = 16141\n", "a(43) = 16777216\n", "a(44) = 15683\n", "a(46) = 81463\n", "a(48) = 28229\n", "a(50) = 31907\n", "a(52) = 19609\n", "a(54) = 35617\n", "a(56) = 82073\n", "a(57) = 268435399\n", "a(58) = 44293\n", "a(60) = 43331\n", "a(62) = 34061\n", "a(64) = 89689\n", "a(66) = 162143\n", "a(68) = 134513\n", "a(70) = 173359\n", "a(72) = 31397\n", "a(74) = 404597\n", "a(76) = 212701\n", "a(78) = 188029\n", "a(80) = 542603\n", "a(82) = 265621\n", "a(84) = 461717\n", "a(86) = 155921\n", "a(88) = 544279\n", "a(90) = 404851\n", "a(92) = 927869\n", "a(94) = 1100977\n", "a(96) = 360653\n", "a(98) = 604073\n", "a(100) = 396733\n", "a(102) = 1444309\n", "a(104) = 1388483\n", "a(106) = 1098847\n", "a(108) = 2238823\n", "a(110) = 1468277\n", "a(112) = 370261\n", "a(114) = 492113\n", "a(116) = 5845193\n", "a(118) = 1349533\n", "a(120) = 1895359\n", "a(122) = 3117299\n", "a(124) = 6752623\n", "a(126) = 1671781\n", "a(128) = 3851459\n", "a(130) = 5518687\n", "a(132) = 1357201\n", "a(134) = 6958667\n", "a(136) = 6371401\n", "a(138) = 3826019\n", "a(140) = 7621259\n", "a(142) = 10343761\n", "a(144) = 11981443\n", "a(146) = 6034247\n", "a(148) = 2010733\n", "a(150) = 13626257\n", "a(152) = 8421251\n", "a(154) = 4652353\n", "a(156) = 17983717\n", "a(158) = 49269581\n", "a(160) = 33803689\n", "a(162) = 39175217\n", "a(164) = 20285099\n", "a(166) = 83751121\n", "a(168) = 37305713\n", "a(170) = 27915737\n", "a(172) = 38394127\n", "a(174) = 52721113\n", "a(176) = 38089277\n", "a(178) = 39389989\n", "a(180) = 17051707\n", "a(182) = 36271601\n", "a(184) = 79167733\n", "a(186) = 147684137\n", "a(188) = 134065829\n", "a(190) = 142414669\n", "a(192) = 123454691\n", "a(194) = 166726367\n", "a(196) = 70396393\n", "a(198) = 46006769\n", "a(200) = 378043979\n", "a(202) = 107534587\n", "a(204) = 112098817\n", "a(206) = 232423823\n", "a(208) = 192983851\n", "a(210) = 20831323\n", "a(212) = 215949407\n", "a(214) = 253878403\n", "a(216) = 202551667\n", "a(218) = 327966101\n", "a(220) = 47326693\n", "a(222) = 122164747\n", "a(224) = 409866323\n", "a(226) = 519653371\n", "a(228) = 895858039\n", "a(230) = 607010093\n", "a(232) = 525436489\n", "a(234) = 189695659\n", "a(236) = 216668603\n", "a(238) = 673919143\n", "a(240) = 391995431\n", "a(242) = 367876529\n", "a(244) = 693103639\n", "a(246) = 555142061\n", "a(248) = 191912783\n", "a(250) = 387096133\n", "a(252) = 630045137\n", "a(260) = 944192807\n", "a(276) = 649580171\n", "a(282) = 436273009\n" ] } ], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }