Matematiska såll och deras tillämpningar En introduktion och algoritmisk implementation Mathematical Sieves and their Applications Examensarbete för kandidatexamen i matematik vid Göteborgs universitet Nils Alexandersson Erik Dagobert Coën Lorcan Olofsson Institutionen för Matematiska vetenskaper CHALMERS TEKNISKA HÖGSKOLA GÖTEBORGS UNIVERSITET Göteborg, Sverige 2021 Matematiska såll och deras tillämpningar En introduktion och algoritmisk implementation Examensarbete för kandidatexamen i matematik inom Matematikprogrammet vid Göteborgs universitet Nils Alexandersson Erik Dagobert Coën Lorcan Olofsson Handledare: Lucile Devin Anders Södergren Institutionen för Matematiska vetenskaper CHALMERS TEKNISKA HÖGSKOLA GÖTEBORGS UNIVERSITET Göteborg, Sverige 2021 Förord Denna kandidatrapport har skrivits i syfte att introducera några grundläggande idéer inom sållteori och koppla dessa till nutidens framsteg inom ämnet. Under arbetets utförande har en gruppdagbok, samt individuella loggböcker förts. Dessa loggböcker innehåller detaljer angående utvecklingen av rapportens övergripande struktur, mötesanteckningar, och individuella rapporteringar av hur tiden har tillbringats. Nedan listas huvudförfattare till rapportens respektive avsnitt. • Nils Alexandersson: Populärvetenskaplig presentation, 5 Bruns såll, 8 Datorimplementa- tion av Eratosthenes såll (inledningen), 8.2 Implementation av algoritmerna i Python, samt appendix B.3 och D med tillhörande kod. • Erik Dagobert: 2 Förberedelser, 3 Det allmänna sållproblemet, 4 Eratosthenes generalise- rade såll, 8.1 Grundläggande teori och algoritmer, samt appendix A, B.2 och C. • Coën Lorcan Olofsson: 1 Inledning, 6 Selbergs såll, 7 Diskussion av sållmetoder, 8.3 Tillämpningar och resultat, samt appendix B.1, B.4 och B.5. Vi vill också tacka våra handledare Anders Södergren och Lucile Devin för all den hjälp de har givit oss. Deras engagemang och vägledning har varit ovärderlig för detta arbete. Populärvetenskaplig presentation Primtal är förrädiskt oförutsägbara. De dyker upp när du minst anar det och kan till synes bete sig totalt oregelbundet. Trots detta är de helt deterministiska i sin natur och gränsen för vad som är och inte är ett primtal är mycket tydlig. Det är kanske just av denna anledning som primtalen, även i modern tid, är så intressanta att studera. Hur många primtal finns det? Svaret är att det finns oändligt många. Om vi istället frågar oss hur många primtal det finns som är mindre än en miljon, så är svaret inte lika lätt. Till att börja med vet vi att primtal, med undantag för talet 2, aldrig är jämna. Därför kan vi åtminstone utesluta vartannat tal och säga att svaret är mindre än en halv miljon. Hur går vi vidare härifrån? Ett naturligt andra steg vore att föra samma resonemang för talet 3; förutom just 3 så är primtal aldrig delbara med 3 och därmed borde vi kunna dra bort ytterligare en tredjedels miljon från svaret. Detta är dessvärre inte riktigt sant. Tal som både är jämna och delbara med 3 har ju uteslutits två gånger. Det har alltså skett en dubbelräkning av alla tal som kan delas med 6, men vi kan kompensera för detta genom att addera en sjättedels miljon till svaret. Denna uppskattning av svaret är bättre än den vi hade tidigare och givetvis kan vi fortsätta vi- dare med talet 5. På så sätt skulle vi komma ännu närmre det faktiska svaret, men vi skulle också be- höva hantera fler dubbelräkningar. Den generella idén här kallas för inklusions-exklusionsprincipen och illustreras nedan för tre mängder med hjälp av figur 1. A B C ABBC AC ABC Figur 1: Illustration av inklusions-exklusionsprincipen för tre stycken överlappande mängder A, B och C. Säg att vi vill beräkna den totala storleken för de överlappande mängderna A, B och C. Vi kan börja med att summera storleken på mängderna var för sig. Om vi betecknar storleken på A som |A| och gör på samma vis för de andra mängderna så kan vi skriva summan som |A| + |B| + |C|. Som bekant har det skett en dubbelräkning där mängderna överlappar varandra. Låt oss skriva AB när vi menar överlappet mellan A och B, och liknande för de andra överlappen. Precis som i tidigare exempel kompenserar vi för dubbelräkningen genom att dra bort dessa överlapp ifrån summan, vilket ger oss |A| + |B| + |C| − |AB| − |BC| − |AC|. Vidare har vi även ABC där alla tre mängderna överlappar varandra. Denna ingår i alla tidigare nämnda mängder och har därmed lagts till och dragits bort tre gånger om. Vi lägger till ABC en gång till och kommer fram till det slutgiltiga svaret |A|+ |B|+ |C| − |AB| − |BC| − |AC|+ |ABC|. Detta är inklusions-exklusionsprincipen och den kan användas för ett godtyckligt antal mängder. Metoden att använda denna princip för att räkna primtal kallas för Legendres såll och är funda- mental i teorin om matematiska såll. Ett (matematiskt) såll är i stora drag en metod för att rensa bort vissa tal ur en mängd heltal. Som ovan exempelvis, då vi använde Legendres såll för att sålla bort icke-primtal ur mängden av heltal upp till en miljon. I denna rapport presenteras tre stycken såll; Eratosthenes generaliserade såll, Bruns såll samt Selbergs såll som alla bygger på idéer liknande det vi har sett här. Gemensamt för de tre sållen är att de inte ger något exakt svar, eftersom ett sådant ofta är opraktiskt att jobba med. Istället nöjer vi oss med approximationer, vilket ändå kan vara användbart förutsatt att vi känner till storleken på uppskattningens fel. Dessa feltermer och deras beteende utgör en väsentlig skillnad mellan de olika sållen och en diskussion samt jämförelse av feltermerna är således relevant. Därför har detta tillägnats en egen del i rapporten vilken följer efter att de tre sållen presenterats. I rapportens sista avsnitt redogör vi för hur Harald Helfgott i [1] har utvecklat idéer från ett grundläggande såll för att skapa effektiva algoritmer som kan utföras med en dator. Därefter framlägger vi vår implementation av algoritmerna i ett program skrivet i Python. Avslutningsvis presenteras även några resultat som vi fått från att köra programmet, där ett av resultaten knyter an till frågan om att räkna primtal. Men istället för att som ovan, titta på tal mellan noll och en miljon, har vi valt att svara på frågan för ett intervall med mittpunkt i 1019 och en bredd på 2.5× 109. Sammanfattning Syftet med denna rapport är att ge läsaren en inblick i det matematiska delområdet sållteori genom att redogöra för dess grundläggande idéer och tillämpningar, samt att presentera en datorimplementation av Eratosthenes såll. I rapporten presenteras Eratosthenes generaliserade såll, samt Bruns och Selbergs såll. Först ges en kortfattad historisk kontext till sållen, följt av en översiktlig härledning, och därtill ett exempel på hur sållen kan tillämpas för att ge resultat om bland annat primtalstvillingar och primtal i aritmetiska serier. Efter att de tre sållen introducerats diskuteras och jämförs orsaken till deras feltermer. Avsikten med detta är att belysa de möjligheter och begränsningar som finns i sållen som verktyg. Efter att ha etablerat viss grundläggande teori övergår rapportens fokus till en algoritmisk implementation av Eratosthenes såll baserad på Harald Helfgotts arbete [1]. Här beskrivs de underliggande matematiska principerna till algoritmen och dess övergripande struktur. Däref- ter redovisas den metod som har använts, och väsentliga beslut som fattats för att översätta algoritmen till ett effektivt program skrivet i programmeringsspråket Python. I den sista delen av rapporten presenteras resultat utifrån kvantitativ data som genererats av programmet vid sållning av primtal i intervallet 1019± 1.25× 109. För att styrka denna datas giltighet jämförs den mot primtalssatsen och med stöd i detta undersöks den förmodade fördelningen av prim- talstvillingar, i förhållande till det som uppmätts i intervallet. Avslutningsvis betraktas datan med avseende på frekvensen av primtalsgap, följt av en kort diskussion om hur detta knyter an till framsteg som gjorts om primtalsgap i modern tid. Abstract This report aims to introduce the reader to the mathematical area of sieve theory through the elucidation of its fundamental principles and applications, as well as presenting an im- plementation in code of Eratosthenes sieving algorithm. We present the generalised sieve of Eratosthenes, as well as the sieves of Brun and Selberg; briefly describing their history and then focusing on outlining their general derivation as well as giving a thorough example of their application on sets such as the twin primes and primes in arithmetic progressions. Following the presentation of the sieves is a discussion which aims to focus the reader’s attention on the origins of the error terms attached to the various methods and the effects they have on the quality of estimations which can be made. Having presented the theory in some detail, we move our attention to an implementation of Eratosthenes original algorithm as based upon the work of Helfgott [1]. We present the underpinning mathematical principles and general algorithmic structure of Helfgott’s imple- mentation as well as our interpretation of his code and eventual improvements to the imple- mentation. Following that is a presentation of results regarding the distributions of the prime numbers, the twin primes, and the behaviour of prime gaps in the interval 1019 ± 1.25× 109. Through the comparison of our code with the prime number theorem as applied to this interval we bolster its legitimacy, which leads to our investigation of the conjectured distribution of twin primes in our interval. We conclude this report with an analysis of the frequency of the prime gaps in our interval and discuss briefly its connection to modern day advances in and about the theory. Innehåll 1 Inledning 1 2 Förberedelser 1 2.1 Multiplikativa funktioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Möbiusfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 Det allmänna sållproblemet 2 4 Eratosthenes generaliserade såll 3 4.1 Legendres såll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4.2 Eratosthenes generaliserade såll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.3 En högredimensionell tillämpning av Eratosthenes såll . . . . . . . . . . . . . . . . 5 5 Bruns såll 6 5.1 Beskrivning av sållet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5.2 En tillämpning av Bruns såll . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6 Selbergs såll 8 6.1 Beskrivning av sållet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.2 Selbergs såll och primtal i aritmetiska talföljder . . . . . . . . . . . . . . . . . . . . 10 7 Diskussion av sållmetoder 11 8 Datorimplementation av Eratosthenes såll 12 8.1 Grundläggande teori och algoritmer . . . . . . . . . . . . . . . . . . . . . . . . . . 13 8.2 Implementation av algoritmerna i Python . . . . . . . . . . . . . . . . . . . . . . . 15 8.3 Tillämpningar och resultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8.3.1 Fördelningen av primtal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8.3.2 Fördelningen av primtalstvillingar . . . . . . . . . . . . . . . . . . . . . . . 18 8.3.3 Frekvens av primtalsgap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 A Ordonotation 22 B Några användbara resultat 22 B.1 Partiell summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 B.2 Summan av primtalsreciproker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 B.3 Asymptotiskt beteende för W(z), ett specialfall . . . . . . . . . . . . . . . . . . . . 24 B.4 Ett lemma angående multiplikativa funktioner . . . . . . . . . . . . . . . . . . . . . 25 B.5 En variant på Möbius inverteringsformel . . . . . . . . . . . . . . . . . . . . . . . . 25 C Kedjebråk 26 D Python-kod tillhörande avsnitt 8 28 D.1 Vår förbättrade version av programmet . . . . . . . . . . . . . . . . . . . . . . . . 28 D.2 Några extra funktioner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1 Inledning Den som någon gång har funderat kring primtal, kanske har provat att ta en lista med naturliga tal upp till någon gräns och börjat försöka hitta de primtalen som finns. Efter en liten stund kanske man börjar lägga märke till mönster som uppträder; såsom att det finns vissa par av primtal som bara har ett tal mellan sig. Man kanske också börjar stryka igenom alla multipler av primtal för att ha något system för att uteslutta sammansatta tal. Så småningom kanske man inser att för att hitta alla primtal upp till ett visst tal behöver man bara alla primtal mindre än eller lika med kvadratroten av det talet. Idén bakom denna process, att hitta primtal i en lista av naturliga tal, har funnits sedan antikens grekland med en algoritm som har tillskrivits den grekiska polyhistorn Eratosthenes (ca. 276 - 194 f.v.t.). Algoritmen har följande struktur; 1. Börja en lista med talet 2 och lista alla naturliga tal upp till någon gräns. 2. Ringa in 2 och stryk över alla andra tal som är delbara med 2. 3. Ringa in nästa tal som inte är struket och stryk alla andra tal delbara med det nya inringade talet. 4. Upprepa steg 3 tills varje tal på listan är struket eller inringat. När algoritmen är avslutad så har varje primtal i listan blivit inringat och alla andra tal har strukits. Eratosthenes algoritm lade grunden för ämnet sållteori; ett område inom matematiken som försöker uppskatta storkleken på så kallade siktade mängder. En siktad mängd är en mängd där alla element är heltal och har någon gemensam egenskap som till exempel en mängd som består av endast primtal eller mängden av alla tal i en aritmetisk talföjld. Den största fördelen med den grundläggande sållteorin är att metoderna är relativt ele- mentära och flexibla, speciellt jämfört med andra metoder inom analytisk talteori. Det krävs inga idéer från komplex analys som till exempel Dirichlets L-funktioner eller serier för att ha använd- ning av de enklare sållen och om man kan formulera mängderna på ett korrekt sätt, går det att effektivt tillämpa metoderna på ett stort antal mängder. Effektiviteten innebär att trots sin enkla konstruktion, kan dessa matematiska såll fortfarande ge starka resultat, även om bättre resultat kan hittas genom att använda mer raffinerade analytiska metoder. Exempelvis gäller det att antalet primtal mindre än x har det asymptotiska beteendet av x/ log(x) vilket ges i primtalssatsen. Detta icke trivialaresultat kan nästan bevisas utan användning av zeta-funktioner eller då man utnyttjar Selbergs såll, dock så får man bara en övre gräns av x/ log(x) istället för det asymptotiska beteen- det. Mer avancerade sållmetoder har givit svar på frågor närliggande till primtalstvillingsförmodan i [2], och att det finns oändligt många par av primtal med maximalt 600 tal emellan sig [3]. Vår rapport fokuserar på små såll av både kombinatorisk och viktad form. Först, att sållen+ är små innebär det att deras sållning använder ett få antal restklasser modulo primtal. Näst, att ett såll är kombinatoriskt innebär att den använder sig av inklusion-exklusionsprincipen för att uppskatta mängdens storlek på ett lämpligt sätt. Slutligen, att ett såll är viktat innebär att någon viktfunktion används för att uppskatta storleken. Sållen vi håller oss till är Eratosthenes generaliserade såll, Bruns såll, och Selbergs såll. För varje såll ger vi en kortfattad härledning till dess formulering, där vi lyfter fram de centrala idéerna för dess konstruktion, och en förklaring till hur sållet används med exempel. En diskussion angående de sållens feletermerna följer sista teoretiska tillämpningen. Efteråt redovisar och analyserar vi en implementering i kod av Eratosthenes ursprungliga algoritm, vilket följer metoden som beskrivs i [1]. Med hjälp av de primtal som genereras av algoritmen undersökar vi slutligen vissa egenskaper hos primtalen såsom deras fördelning, fördelningen av primtalstvillingar, och frekvensen av olika stora avstånd mellan två på varandra följande primtal (primtalsgap). Dock, innan vi börjar redovisa något av sållen går vi igenom några förberedelser och förklarar det allmänna sållproblemet. 2 Förberedelser Den här texten lånar större delen av sin notation från boken An Introduction to Sieve Methods and their Applications av Alina Carmen Cojocaru och M. Ram Murty [4]. Exempelvis om inget annat 1 nämns skriver vi p, q när vi menar primtal, n, d, k för positiva heltal och x, y, z för positiva reella tal. Den största gemensamma delaren betecknas här (d, k) och pi(z) är antalet primtal mindre än eller lika med z. Nedanstående avsnitt ämnar till att etablera mer notation och tekniker som är vanligt förekommande i sållteori med utgångspunkt i [4]. 2.1 Multiplikativa funktioner En särskilt trevlig delmängd av alla funktioner i talteoretiska sammanhang är de multiplikativa funktionerna. Vi säger att en funktion f är multiplikativ om f(1) = 1 och f(mn) = f(m)f(n) då (m,n) = 1. Om detta håller för alla m,n så kallar vi f för fullständigt multiplikativ. Multiplikativa funktioner har fördelen att en viss typ av summor kan omskrivas till produkter, s.k. Eulerprodukter. Om f är multiplikativ så följer det av aritmetikens fundamentalsats att ∞∑ n=1 f(n) = ∏ p ∞∑ i=0 f(pi) så länge den första summan absolutkonvergerar. 2.2 Möbiusfunktionen En ytterst väsentlig multiplikativ funktion i sållteori är Möbiusfunktionen, µ(n) =    1, om n är ett kvadratfritt, naturligt tal med jämnt antal primtalsdelare −1, om n är ett kvadratfritt, naturligt tal med udda antal primtalsdelare 0, om n inte är kvadratfri där kvadratfri innebär att n saknar delare på formen pα för α > 1. Vi kommer se att Möbius- funktionen, bland annat, förenklar inklusion-exklusionsprincipen i nästa kapitel. Två andra viktiga egenskaper hos Möbiusfunktionen är ∑ d|n µ(d) = { 1, om n = 1 0, om n > 1 och Möbius inverteringsformel som säger f(n) = ∑ d|n g(d) =⇒ g(n) = ∑ d|n µ(d)f(n/d) (1) om f, g : N→ C. Det finns flera varianter av Möbius inverteringsformel, en annan som vi kommer ha användning av hittas i appendix B.6. 3 Det allmänna sållproblemet Det allmänna fallet i sållteori är att vi har en mängd heltal A, en mängd primtal P, samt delmäng- der Ap,∀p ∈ P och är intresserade av att sålla fram kardinaliteten S(A,P) := #(A\∪p∈PAp). Vi låter P (z) beteckna produkten av alla p < z i P med specialfallet P (z) = Pz då P är mängden av alla primtal. Med denna notation så skriver vi S(A,P, z) := #(A \ ∪p|P (z)Ap). För d, en kvadratfri produkt av element p ∈ P, definierar vi Ad = ∩p|dAp och A1 = A. Använder vi oss av inklusion-exklusionsprincipen, formulerad med hjälp av möbiusfunktionen, får vi då S(A,P, z) = ∑ d|P (z) µ(d)#Ad. (2) 2 Ett gemensamt drag hos de matematiska sållen diskuterade nedan är att låta X beteckna kardinaliteten av A och hitta δp så att #Ap = δpX +Rp (3) där δp ∈ [0, 1) kan betraktas som en uppskattning av andelen element i delmängden Ap och Rp som en felterm. Utvidgat, för ett kvadratfritt tal d = p1 · ... · pn, låter vi δd = δp1 · ... · δpn så att #Ad = δp1 · ... · δpnX +Rd. I avsnitt 4 om Eratosthenes generaliserade såll och avsnitt 5 om Bruns såll så kommer vi välja δp = ω(p)/p där ω(p) betecknar antalet utvalda restklasser modulo p vi vill sålla bort. Som följd låter vi i dessa fall Ap vara alla element som tillhör någon av dessa restklasser modulo p och för kvadratfria d låter vi ω(d) := ∏ p|d ω(p). Sätter vi in det här δd:t i (2) ser vi att vi får en huvudterm som är X multiplicerat med summan ∑ d|P (z) µ(d)ω(d)/d. Vi kan se att denna summa är lika med W (z) := ∏ p∈P p X vilket innebär att, väldigt grovt, y ≤ P (X). Att det andra antagandet gäller såg vi i föregående avsnitt ty {x/d} ≤ ω(d) = 1. Sist så ser vi att (5) håller genom att sätta in ω(p) = 1 och utnyttja att ∑ p≤n log p p = log n+O(1). (6) Vi börjar återigen med Legendres grundidé, inklusion-exklusionsprincipen, men infogar det mer generella uttrycket för #Ad i formeln S(A,P, z) = ∑ d|P (z) µ(d)#Ad = X ∑ d|P (z) d≤y ω(d) d µ(d) + ∑ d|P (z) d≤y µ(d)Rd, där trunkeringen av summan kommer av antagandet #Ad = 0,∀d > y. Studerar vi den första summan ovan ser vi att vi kan skriva om den som summan över alla d | P (z) minus summan över alla d | P (z) så att d > y. Med W (z) på summaformen från avsnitt 3 kan vi således dela upp den siktade mängden i en huvudterm och en rest på följande vis S(A,P, z) = XW (z) + ( −X ∑ d|P (z) d>y ω(d) d µ(d) + ∑ d|P (z) d≤y µ(d)Rd ) . De två summorna innanför parentesen i uttrycket ovan är vår felterm. Fokuserar vi på den andra summan så kan vi uppskatta dess storlek, först med hjälp av triangelolikheten och sedan med ∣ ∣µ(d) ∣ ∣ ≤ 1 och vårt antagande |Rd| = O(ω(d)), så att summanden ∣ ∣µ(d)Rd ∣ ∣ ≤ O(ω(d)). Flyttar vi in summan innanför ordo-tecknet så kan vi förenkla den med Rankins trick som, enligt [4, s.68] säger att indikatorfunktionen, 1n≤x ≤ xn . Därav skriver vi ∑ d|P (z) d≤y ω(d) = ∑ d|P (z) ω(d)(1d≤y)δ ≤ ∑ d|P (z) ω(d) (y d )δ för alla δ > 0. Eftersom ω(d)/dδ är multiplikativ kan vi skriva summan som en produkt yδ ∏ p|P (z) ( 1 + ω(p)pδ ) = exp ( δ log y + ∑ p|P (z) log ( 1 + ω(p)pδ ) ) ≤ exp ( δ log y + ∑ p|P (z) ω(p) pδ ) vari sista steget vi använder att log(1+x) ≤ x. Väljer vi nu δ = 1−1/ log z och utnyttjar olikheten ex ≤ 1 + xex, som gäller för x ≥ 0, och sist partiell summering av (5) får vi att ∑ d|P (z) d≤y ω(d) = O ( y log(z) (log(z)) κ+1 exp ( − log(y)log(z) )) . 4 På ett liknande sätt omvandlar vi den första summan i feltermen med partiell summering av antagandet (5) och sedan använder resultatet vi fick för den andra summan. Sammanställt, erhåller vi nästa sats, [4, sats 5.4.1]: Sats 4.1 (Eratosthenes generaliserade såll). Med notationen från avsnitt 3 och följande antaganden 1. #Ad = 0,∀d > y för något y ∈ R+, 2. |Rd| = O(ω(d)), 3. ∑ p|P (z) ω(p) log(p) p ≤ κ log(z) +O(1), så gäller att S(A,P, z) = XW (z) +O (( X + ylog z ) (log z)κ+1 exp ( − log ylog z )) . 4.3 En högredimensionell tillämpning av Eratosthenes såll Ett av målen med avsnitt 4.2 var att kunna använda Eratosthenes såll till att sålla bort flera kongruensklasser per primtal p. I det här avsnittet kommer vi utnyttja denna egenskap till att sålla fram primtalstvillinigar och sedan bevisa en variant av Bruns sats [4, korollarium 5.4.5], Sats 4.2 (Bruns sats). Summan av reciproker, ∑ p p+2 prima 1 p <∞. Satsen bevisades först av Brun 1919 i artikeln La série 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 + 1/29+1/31+1/41+1/43+1/59+1/61 . . . ou les dénominateurs sont «nombres premiers jumeaux »est convergente ou finie men vi kommer här följa ett annat bevis, ur [4, s.72f], som använder sig av sats 4.1. Primtalstvillingar i det här fallet är tal i mängden P2(x) := {p < x : p+ 2 är ett primtal}. För att hitta dessa tal så vill vi utesluta alla multiplar av primtal samt alla tal två mindre än dessa multiplar. Med andra ord väljer vi kongruensklasserna 0 och −2 modulo p i sålldefinitionen så att ω(2) = 1 och ω(p) = 2 för alla primtal p > 2 samt att dimensionen κ = 2. Det andra antagandet i sats 4.1 är en svagare variant av ett antagande i Bruns såll och verifieras i avsnitt 5.2. Vårt val av kongruensklasser ger att y = x+ 2 i det första antagandet av sats 4.1 som då säger att #P2(x) ≤ pi(z) + S(A,P, z) ≤ z + xW (z) +O ( x(log z)3 exp ( − log xlog z )) . Vi kan enkelt se att W (z) i huvudtermen är lika med ∏ p −1 i –riktningen och den andra riktningen visas i sats B.4 från appendix. Med en partiell summation av (6) (se sats B.3) erhåller vi att ∑ p≤z 1 p = log log z +O(1) som, när vi sätter in i (7), ger oss att W (z)  exp ( − 2 ∑ 2 0 som uppfyller ∑ w≤p 2, samt κ = 2. För att kunna använda (13) måste givetvis satsens alla antaganden vara uppfyllda. Sätt därför A1 := 2/3 så att antagandet ω(d) ≤ dA1 gäller. Härnäst kontrollerar vi att |Rd| ≤ ω(d) håller genom att visa det något starkare påståendet |Rp| ≤ ω(p). Med användning av (3) har vi att #Ap = ⌊x p ⌋ + ⌊x+ 2 p ⌋ ≤ 2px+ 2, för alla p > 2. En liknande beräkning ger oss att #Ap ≥ 2x/p vilket visar att |Rp| ≤ 2 för alla p > 2. I fallet då p = 2 har vi istället att #A2 = bx/pc som implicerar |R2| ≤ 1. Därmed kan vi dra slutsatsen att |Rp| ≤ ω(p), vilket implicerar att |Rd| ≤ ω(d) håller för alla kvadratfria tal d. Att det sista antagandet i sats 5.1 är uppfyllt kan vi se genom användning av (6) som tillsammans med ω(p) ≤ 2 ger oss att ∑ w≤p c3 − 1, har vi att feltermen går mot noll då x → ∞, och vi får slutligen: Sats 5.2. #T  x(log x)2 . Lägg märke att vi inte bara har bevisat påståendet att det finns oändligt många par av heltal (n, n+2) där båda talen har högst 7 primtalsfaktorer, uttrycket ovan ger oss även en undre gräns för det asymptotiska beteendet hos mängden ifråga. Härnäst riktas fokus mot denna rapports tredje och sista såll. 6 Selbergs såll Ett ytterligare perspektiv på sållmetoder gavs av en annan norsk matematiker, Atle Selberg (1917- 2007), under 1940 talet. Hans metod var av en kombinatorisk stil som liknade de tidigare. Dock använde han sig av en ny typ av vikt och en uppskattning av en summa av Möbiusfunktioner för att uppskatta kardinaliteten av A. Denna metod kallas för Selbergs såll och är ett exempel på ett viktat såll. I detta avsnitt så ges en beskrivning av sållets uppbyggnad följt av en tillämpning av sållet för att uppskatta antalet primtal i en aritmetisk talföljd. 6.1 Beskrivning av sållet Selbergs nya vikter, vilka motsvarar δd i (3), består av 1 f(n) , f(n) = ∑ d|n f1(d) där f(n) och f1(d) är multiplikativa funktioner och f1(d) är entydigt bestämd med hjälp av Möbius inverteringsformel. Det krävs också att f(p) > 1 för alla p ∈ P. Till exempel, om vi vill sålla bort alla tal i mängden Ad = {n ≤ x : n ≡ 0 (mod d)}, där x > 0, då blir #Ad = x/d + O(1) och dessutom f(d) = d. Föregående exempel är relativt enkelt men i mer komplexa fall kan en sådan mer allmän vikt ge sållteorin möjligheten att uppskatta nya typer av mängder som tidigare hade inte varit möjligt att uttrycka med endast restklasser modulo primtal. Enligt [4, s. 114], bestod grundläggande uppskattningen av Selbergs såll huvudsakligen av att för en given reell talföljd, (λd), med λ1 = 1, har vi att ∑ d|n µ(d) ≤ ( ∑ d|n λd )2 . För att förstå varför denna uppskattning av Möbiusfunktionens summa fungerar, erinrar vi den första egenskapen som redovisas i 2.2. Om n = 1 är både höger- och vänsterledet ovan lika med 1, 8 medan n = 0 ger att vänsterledet är 0 och högerledet är ickenegativt ty detta är en kvadrat. Slut- målet med sållets härledning blir att konstruera talföljden (λd) så att uppskattningen minimeras, vilket kommer göras senare. Med hjälp av talföljden (λd) kan vi nu uppskatta S(A,P, z) eftersom S(A,P, z) = ∑ a∈A a6∈Ap,∀p|P (z) 1 = ∑ d|P (z) µ(d) ∑ a∈Ad 1 = ∑ a∈A ( ∑ d|P (z) a∈Ad µ(d) ) ≤ ∑ a∈A ( ∑ d|P (z) a∈Ad λd )2 . (16) Låt oss nu anta att λd = 0 för alla d > z. Med antagandet kan vi nu skriva om kvadraten av summan som en summa över två olika d och omvandla (16) till S(A,P, z) ≤ ∑ a∈A ( ∑ d1|P (z) a∈Ad1 λd1 ∑ d2|P (z) a∈Ad2 λd2 ) = ∑ a∈A ∑ d1,d2|P (z) a∈A[d1,d2] λd1λd2 = ∑ d1,d2≤z d1,d2|P (z) λd1λd2#A[d1,d2] där [a, b] betecknar den minsta gemensamma multipeln av a och b. Vi kombinerar summorna av λd1 och λd2 ovan genom att inse att om a ∈ Ad1 och a ∈ Ad2 måste den vara ett element i A[d1,d2] på grund av definitionen av A. Med infogande av δd = 1/f(d) i (3) får vi uppskattningen som är grundläggande för Selbergs såll; S(A,P, z) ≤ X ∑ d1,d2≤z d1,d2|P (z) λd1λd2 f([d1, d2]) +O ( ∑ d1,d2≤z d1,d2|P (z) |λd1 ||λd2 ||R[d1,d2]| ) . (17) Vi kommer att fokusera vår härledning på huvudtermen av sållet eftersom den kräver att vi visar hur vi bestämmer talföjlden (λd) vilket är avgörande för sållets konstruktion. Med [4, s. 120] som utgångspunkt, börjar vi med att använda oss av ett lemma som låter oss skriva om multiplikativa funktioner av minsta gemensamma multipler, se Appendix B.5. Lemmat tillsammans med definitionen av f tillåter följande omskrivning: ∑ d1,d2≤z d1,d2|P (z) λd1λd2 f([d1, d2]) = ∑ d1,d2≤z d1,d2|P (z) λd1λd2 f(d1)f(d2) f((d1, d2)) = ∑ d1,d2≤z d1,d2|P (z) λd1λd2 f(d1)f(d2) ∑ δ|(d1,d2) f1(δ). (18) Nu byter vi summationsordningen i (18), genom att inse att om δ|(d1, d2) då är δ ≤ z och δ|P (z). Med detta, har vi också att d1 och d2 måste vara delbara med δ. Därför kan vi skriva om (18) till ∑ δ≤z δ|P (z) f1(δ) ∑ d1,d2≤z d1,d2|P (z) δ|(d1,d2) λd1λd2 f(d1)f(d2) = ∑ δ≤z δ|P (z) f1(δ) ( ∑ d≤z d|P (z) δ|d λd f(d) )2 . Sätter vi uδ = ∑ d≤z d|P (z) δ|d λd f(d) =⇒ ∑ δ≤z δ|P (z) f1(δ) ( ∑ d≤z d|P (z) δ|d λd f(d) )2 = ∑ δ≤z δ|P (z) f1(δ)u2δ . (19) Vi kan nu tillämpa en variant på Möbius inverteringsformel, se Appendix B.6, på uδ, vilket ger att λδ f(δ) = ∑ d≤z d|P (z) δ|d µ(d/δ)ud (20) Eftersom vi har diagonaliserat huvudtermen i (19) kan vi enkelt bestämma ett värde på uδ sådant att summan antar sitt minimivärde genom att använda kvadratkomplettering. Vi gör det- ta med hjälp av (20) och införandet av en ny funktion V (z) = ∑ d≤z, d|P (z) µ2(d) f1(d) , vilket direkt underlätter kvadratkompletteringen av summans termer. Det är också värt att påpeka att V (z) 9 är strikt positivt eftersom f1(d) alltid är större än noll. Detta gäller eftersom för varje primtal är f1(p) = ∑ d|p µ(d)f(p/d) = µ(1)f(p) + µ(p)f(1) = f(p) − 1 > 0. Dessutom har vi att f1 är multiplikativ och att d är kvadratfri vilket tillsammans med föregående resonemang medför att f1 > 0 för alla d i summan. Därför blir V (z) en summa av strikt positiva tal och därmed strikt positiv själv. Om vi sätter δ = 1 i (20) då får vi att 1 = λ1f(1) = ∑ d≤z d|P (z) µ(d)ud. vilket vi kan använda för att hitta en minimum på följande sätt: ∑ δ≤z δ|P (z) f1(δ)u2δ = ∑ δ≤z δ|P (z) f1(δ)u2δ + V (z) V (z)2 − 2 V (z) + 1 V (z) = ∑ δ≤z δ|P (z) f1(δ)u2δ + ∑ δ≤z δ|P (z) µ2(δ) f1(δ)V 2(z) − ∑ δ≤z δ|P (z) 2µ(δ)uδ V (z) + 1 V (z) . (21) Vi kan samla alla summor i (21) till en och då vi kvadratkompletterar summans termer har vi att ∑ δ≤z δ|P (z) f1(δ)u2δ = ∑ δ≤z δ|P (z) f1(δ) ( uδ − µ(δ) f1(δ)V (z) )2 + 1V (z) . Givetvis blir ovanstående summa noll då vi väljer uδ = µ(δ)f1(δ)V (z) , vilket måste vara en minimivärde eftersom f1(δ är strikt positiv. Det går också att bevisa att med detta val av uδ blir |λd||V (z)| ≤ |V (z)| [4, s. 122-123] och därför härleder vi följande sats. Sats 6.1 (Selbergs såll). Behåll notationen från tidigare i detta avsnitt och avsnitt 2. Då har vi att S(A,P, z) ≤ XV (z) +O ( ∑ d1,d2≤z d1,d2|P (z) |R[d1,d2]| ) . Ovanstående formulering är hur satsen redovisas i [4, sats 7.2.1]. Notera att i Selbergs såll har vi färre paratmetrar att bestämma än i de tidigare sållen, vilket hjälper en del med dess tillämpning. Ett exempel på hur sållet kan tillämpas redovisas i nästa avsnitt. 6.2 Selbergs såll och primtal i aritmetiska talföljder Med hjälp av Selbergs såll kan vi uppskatta antalet primtal som finns i en aritmetisk talföjld, det vill säga antalet primtal på formen p = a + tk där a, k är valda konstanter och t är godtyckligt. Det finns också ett krav på a och k, nämligen att de är relativt prima, utan det kravet så skulle maximalt ett primtal finnas i talföjlden. Slutligen antar vi att k är kvadratfritt, vilket kommer underlätta beräkningar senare. Om vi vill uppskatta antalet primtal på ovanstående form mindre än något x, då är det samma som att uppskatta; pi(x; k, a) = #{p ≤ x : p ≡ a (mod k)}. (22) Låt oss nu ta något z ≤ x, z ∈ R+ som vi kommer att bestämma senare. Då kan vi uppskatta (22) genom att dela upp mängden på följande sätt. pi(x; k, a) = pi(z; k, a) + #{z < p ≤ x : p ≡ a (mod k)} ≤ z + #{n ≤ x : n ≡ a (mod k), n 6≡ 0 (mod q), ∀q ≤ z}. (23) Uppskattningen av den andra kardinaliteten som utförs i (23) motsvarar en sållning av alla tal som finns i talföjlden med primtal mindre än z. Det är klart att det är en uppskattning eftersom om 10 det finns ett sammansatt tal i följden som endast är delbart med primtal större än z så kommer de inte sållas bort. Dock så behöver vi faktiskt inte sålla med avseende på alla primtal mindre än z, bara de som är relativt prima med k. Om till exempel k = 6 så får a inte vara delbar med varken 2 eller 3. Som konsekvens av det kommer inga element i talföjlden vara delbar med ks delare heller. Följaktligen ger detta oss att vi bara behöver primtal ur P = {p : (p, k) = 1} och kardinaliteten vi vill uppskatta är då S(A,P, z) = #{n ≤ x : n ≡ a (mod k), n 6≡ 0 (mod p), p ≤ z, (p, k) = 1}. För att kunna använda sållet så behöver vi bestämma A, Ad, X, f(d) samt f1(d), och Rd. Det är uppenbart att A = {n ≤ x : n ≡ a (mod k)} och dessutom att Ad = {n ≤ x : n ≡ a (mod k), n ≡ 0 (mod d)}. Eftersom k och d är relativt prima ger kinesiska restsatsen att det finns ett unikt tal modulo kd som är kongruent med n. Detta delar då upp intervalet [0, x] i bx/kdc stycken delintervall där det i varje delintervall finns ett element som ska sållas bort, vilket medför att #Ad = xkd + O(1). Vi erhåller X = xk , f(d) = d, och Rd = O(1). För att bestämma f1(d) använder vi oss av dess definition, att f är multiplikativ, och att varje d = p1p2...pj är kvadratfri. Detta görs på följande sätt: f1(d) = ∑ m|d µ(m)f(d/m) = ∑ m|p1...pj µ(m)f((p1...pj)/m) = 1∑ b1=0 ... 1∑ bj=0 µ(pb11 ...p bj j )f((p1...pj)/(pb11 ...p bj j )) = j∏ h=1 1∑ bh=0 µ(pbhh )f(ph/p bh h ) = j∏ h=1 ( f(ph)− 1 ) = j∏ h=1 ph ( 1− 1ph ) = d j∏ h=1 ( 1− 1ph ) = φ(d). (24) I (24) ser vi att f1(d) = φ(d) där φ(d) är Eulers φ-funktion. Tillsammans med 6.1 ger ovanstående att S(A,P, z) ≤ x/(kV (z)) +O(z2). För att uppskatta 1/V (z) tillämpar vi ett lemma från [4, lemma 7.2.3] som säger att f(P (z))V (z) ≥ f1(P (z)) ∑ δ≤z 1 f˜(δ) (25) där P (z) = ∏ p≤z, p 6∈P p och f˜(d) är en fullständigt multiplikativ funktion med f˜(p) = f(p) för alla primtal p. Eftersom de enda primtal som inte är i P är de som delar k har vi enligt (25) att kV (z) ≥ φ(k) ∑ δ≤z 1 δ = φ(k)(log z +O(1)) ⇐⇒ 1 V (z) ≤ k φ(k)(log z +O(1)) (26) där vi har använt oss av partiell summation vid likhetstecknet. Med hjälp av (26) har vi nu att pi(x; k, a) ≤ z + xφ(k)(log z +O(1)) +O(z 2) = xφ(k)(log z +O(1)) +O(z 2) där likheten gäller eftersom z1 absorberas av ordonotationen. Genom att likställa de två termerna kan vi bestämma z så att båda termerna har samma vikt. Vi följer förslaget på z i [4, s. 127] och tar z = (2x/k) 12−ε0 för något ε0 ∈ (0, 1). Detta val av z ger oss den slutliga uppskattningen pi(x; k, a) ≤ (2 + ε)xφ(k) log(2x/k) för alla ε > 0 och x större än något x0(ε) > 0. Resultatet är en variant på Brun-Titchmarshsatsen som bevisades först år 1930 av Titchmarsh [8] med hjälp av Bruns såll. Varianten som vi har härledt ovan är en starkare form än vad om bevisades av Titchmarsh vilket i viss mån beror på skillnaden mellan storleken på feltermerna i Bruns och Selbergs såll. Denna idé kommer utvecklas mer i nästa avsnitt. 7 Diskussion av sållmetoder Som nämndes i inledningen kan sållmetoder, även om de är användbara, kräva en stor del arbete eller förfining för att spegla de resultat vilka ges av mer analytiska metoder. En uppenbar orsak till 11 detta är feltermerna kopplade till de sållmetoder som används. Det är ett återkommande tema i sållmetoder som helhet att försöka minska dessa feltermer för att förbättra de slutliga uppskattning- arna. Feltermens påverkan på dessa uppskattningar kan enkelt upptäckas i alla tillämpningsdelar i de föregående avsnitten. Den har störst påverkan i det kritiska steget då z bestäms till någon funktion av x vilket i sin tur förenar huvudtermen och feltermen. Av de sållmetoderna vi har redo- visat är skillnaden mellan feltermerna störst mellan Eratosthenes generaliserade såll och de andra två sållmetoderna. För att visa påverkan av denna skillnad redovisar vi ett sista exempel. Låt oss nu återgå till en av sållteorins musor som är att uppskatta storleken på pi(x). Som nämn- des i 4.1 motsvarar problemet en linjär sållning av A = {n ≤ x : n ∈ N} med Ad = {n ≤ x : n ≡ 0 (mod d)}. Vi tillämpar Eratosthenes såll på problemet genom att välja y = x ,och κ = 1. Med detta val av parametrar erhåller vi en felterm av storleksordning O(x(log z)2 exp(− log x/ log z)). Vi jämför den nu emot feltemerna för både Bruns och Selbergs såll, och vad för uppskattning av pi(x) man kan få från de. Vi tillämpar Bruns såll genom att sätta b = 1 och, återigen, κ = 1. Vi sätter λ = 0.26, för att minska potensen av feltermen och då får vi att c3 ≤ 9 och storleksordningen på feltermen är O(z9). För att tillämpa Selbergs såll inser vi att #Ad = x/d+O(1) vilket medför att feltermen i Selbergs såll av storleksordning O(z2), precis som i tillämpningen i avsnitt 6.2. Skillnaden mellan felen i Bruns och Selbergs såll kan ses lätt men hur de jämförs med Eratosthenes är inte lika uppenbart. För att förstå skillnaden blandar vi in huvudtermen, vilket är av storleks- ordning O(x/ log z) för alla tre sållmetoder. Vi kan förena huvud och feltermen för båda Bruns och Selbergs såll genom att sätta z = x1/u, med u > 9 respektive u > 2 och både ger uppskattningen pi(x) x/ log x. Dock så kan vi inte välja z på samma stil när vi tillämpar Eratosthenes allmänna såll. I det fallet måste vi välja log z = log x/C log log x för något liten konstant C sådan att fel- termen och huvudtermen har samma vikt. Med en sådan z erhåller vi från Eratosthenes allmänna såll att pi(x)  x log log x/ log x. Att både Brun och Selbergs såll når resultat som börjar likna primtalssatsen men inte Eratosthenes generaliserade såll exemplifierar hur feltermerna påverkar kvalitén av slutsatsen som kan dras från de olika metoderna. Var och en av sållmetoderna har olika faktorer som påverkar storleken på deras feltermer. Det finns dock åtminstone en gemensam faktor mellan de tre metoderna som är värt att nämna, vilket är hur de olika metoderna hanterar Möbiusfunktionen. Som utgångpunkt har vi Eratosthenes allmänna såll som uppskattar Möbiusfunktionen med |µ(d)| ≤ 1 då vi kommer till feltermen. Bruns såll gör lite mer med Möbiusfunktionens och (10) kan formuleras på ett sådant sätt på grund av Möbiusfunktionen och en tillämpning av Möbius inverteringsformeln på den och funktionen g. Selbergs såll går ett steg vidare och baserar en stor del av hela sin härledning på en uppskattning av en summa av Möbiusfunktioner. Att sållet som försöker hårdast att undvika Möbiusfunktionen är oftast metoden som ger bäst resultat av de tre påpekar hur svårhanterat Möbiusfunktionen är. I själva verket, enligt Tao [9], är Möbiusfunktionen roten till en ännu mer central utmaning för sållteorin än att minimera feltermer, nämligen paritetsproblemet. Detta problem säger i huvudsak att för specifika typer av mängder kommer sållmetoder antingen att ge övre gränser som är för stora med faktor av minst två eller undre gränser som är triviala. Detta kan ses bero på den binära karaktären hos Möbiusfunktionen vilket leder till att för många kardinaliteter tas bort eller för många läggs tillbaka då man trunkerar Möbiusfunktionen, det vill säga uppskattar den. Moderna sållmetoder såsom de utvecklade av Friedlander och Iwaniec [10] försöker undvika paritetsproblemet för vissa mängder av primtal. Deras metoder har haft succé med att visa att det finns oändlig många primtal på formen a2 + b4 och även ger en asymptotisk formel för det. 8 Datorimplementation av Eratosthenes såll I numeriska sammanhang är Eratosthenes såll ett kraftfullt verktyg. Sållet ger oss en metod för att sålla bland eller faktorisera alla tal upp till något N , där förhållandet mellan N och antalat beräkningar som krävs är nära linjärt [1, s.333]. I detta avsnitt utforskas de idéer och algoritmer baserade på Eratosthenes såll som presenteras i An Improved Sieve of Eratosthenes av Harald Helf- gott [1], samt en datorimplementation av detta skriven i programmeringsspråket Python. Avsnittet består av tre delar. I den första delen beskrivs algoritmernas funktion och deras underliggande ma- tematiska principer. Del två är en metoddel där vi beskriver vilka beslut som gått in i att skriva ett snabbt och välfungerande program baserat på dessa algoritmer. Slutligen visar vi hur pro- 12 grammet kan användas för att ge resultat om fördelningen av primtalstvillingar och frekvensen av primtalsgap. 8.1 Grundläggande teori och algoritmer När Eratosthenes först formulerade sitt såll var det, som vi såg i inledningen, på formen av en algoritm. Det är med utgångspunkt i Eratosthenes ursprungliga idé som [1] utvecklar algoritmen för att optimera processen till en effektiv kod som kan leta efter primtal i ett intervall, [n−∆, n+∆] ⊂ R+. Delvis gör [1] detta med algoritmen SimpleSiev, vilken är nära en direkt översättning av Eratosthenes klassiska såll. Vi ser i Algorithm 1 exakt hur sållet implementerats i pseudokod. Algoritmen startar med att sålla bort alla jämna tal från en lista och går sedan igenom resterande tal, kontrollerar om de sållats bort och om inte så tas alla multiplar av talet bort från listan. Resultatet blir en lista av alla primtal upp till ett givet tal N . Denna metoden fungerar väl för små N men vill vi hitta primtal i ett intervall [n − ∆, n + ∆] för något stort n och relativt litet ∆ så ger algoritmen oss betydligt mer information än vad vi behöver och kräver mer tid och minnesutrymme. Algorithm 1 En implementation av Eratosthenes såll från [1] 1: function SimpleSiev(N) Ensure: for 1 ≤ n ≤ N , Pn = 1, if n is prime, Pn = 0 otherwise 2: P1 ← 0, P2 ← 1, Pn ← 0 for n ≥ 2 even, Pn ← 1 for n ≥ 3 odd 3: m← 3, n← m ·m 4: while n ≤ N do 5: if Pm = 1 then 6: while n ≤ N do 7: Pn ← 0, n← n + 2m . sieves out multiples ≥ m2 of m 8: m← m + 2, n← m ·m 9: return P Flaggskeppet i [1], algoritmen NewSegSiev, löser problemet genom att dela upp talen vi vill sålla bort multiplar av i två fall — tal som är så pass små att vi är garanterade att det finns en multipel av dessa i vårt intervall och större tal som har högst en multipel i intervallet. Med den här uppdelningen kan vi behandla de två fallen olika för att spara tid och precis som i Eratosthenes såll behöver vi inte sålla med tal större än √ n+ ∆. I figur 2 ser vi ett flödesschema av NewSegSiev med den ovannämnda uppdelningen — först sållar algoritmen bort multiplar av små primtal innan kriterium A och sedan går den in i den andra loopen för att hantera multiplar av större tal. Eftersom vi kan vara säkra på att alla tal mindre än längden av intervallet (det vill säga m ≤ 2∆ + 1) har en multipel i intervallet så börjar vi att sålla med dessa. Algoritmen gör detta för några fler m än de vi kan vara säkra på har en multipel i intervallet — för alla m ≤ K∆ — bara så att nästa steg med m > K∆ ska gå smidigt. Vi behöver som bekant inte sålla för alla tal utan det räcker med att vi utesluter multiplar av primtal från intervallet. Processen i NewSegSiev för p ≤ K∆ sköts av funktionen SubSegSiev som delar upp dessa primtal i segment [M ′i ,M ′i + ∆′], där M ′0 = 1,∆′ = b √ K∆c och M ′i = M ′i−1 + ∆′ + 1, och sållar sedan bort alla multiplar av dessa i vårt intervall. Primtalen i intervallen [M ′i ,M ′i + ∆′] ges i sin tur av en annan funktion, SimpleSegSiev, som på samma vis sållar segmentet med en lista av primtal p ≤ b √ M ′i + ∆′c. Sista pusselbiten, listan av primtal, erhålls med den tidigarenämnda algoritmen SimpleSiev på klassiskt vis. Givetvis hade vi kunnat sålla intervallet med p ≤ K∆ utan att segmentera primtalen i intervall och bara genererat alla primtal upp till och med K∆ direkt med SimpleSiev. Tidskomplexiteten är enligt [1] samma för båda metoderna men anledningen till att vi segmenterar sållet är för att bespara minneskomplexitet — O( √ K∆ + 2∆) för SubSegSiev gentemot O(K∆ + 2∆) för SimpleSegSiev. Nästa steg, huvudalgoritmen iNewSegSiev, kräver mer matematisk eftertanke. Uppgiften som kvarstår för funktionen efter SubSegSiev är att sålla intervallet [n − ∆, n + ∆] med resterande primtal, p ≥ K∆ där K ≥ 5/2. Problemet är löst genom att leta efter alla multiplar av m ≥ K∆ 13 START SubSegSiev SimpleSegSiev SimpleSiev SimpleSegSiev A B NewSegSiev B’ DiophAppr STOP NEJ JA NEJ JA NEJ JA Figur 2: Ett övergripande flödesschema för algoritmen NewSegSiev. Observera att det finns två huvudloopar i algoritmen, en där kriterium A är uppfyllt när intervallet [n − ∆, n + ∆] sållats med alla primtal p ≤ K∆ och den andra där kriterium B’ är uppfyllt då algoritmen sållat för resterande tal upp till √ n+ ∆. Slutligen är kriterium B i koden identiskt med B’ men illustrerar i flödesschemat möjligheten för programmet att aldrig gå in i den andra loopen vilket inträffar då ∆ > √ n+ ∆/K. i vårt intervall. Låt `m vara en sådan multipel, då ser vi att n−∆ ≤ `m ≤ n+ ∆⇐⇒ −∆m ≤ n m − ` ≤ ∆ m ⇐⇒ { n m } ∈ [ −∆m, ∆ m ] mod 1, (27) där [ − ∆m , ∆m ] mod 1 = ⋃ k∈Z [ k− ∆m , k+ ∆m ] . Med den här presentationen av problemet gör [1] två approximationer – först en Taylorutveckling och därefter en diofantisk approximation. Den första approximationen syftar till att ersätta hyperbeln f(m) := nm med en (diskontinuer- lig) mängd tangenter till kurvan givna av en Taylorapproximation vid olika punkter m0, f(m) = f(m0 + r) = n m0 − nm20 r +O ( n m3− r2 ) där m− = min(m,m0). Eftersom hyperbeln planar ut för större m så kan vi approximera större och större intervall av kurvan med samma linjesegment utan att förstora feltermen. Mer specifikt så låter [1] approximera kurvan med tangenter till kurvan på mitten, m0, av intervallet [Mi,Mi+2Ri] där Mi+1 = Mi + 2Ri + 1 med M0 = bK∆c+ 1 och Ri = ⌊√ ∆/(4n)Mi ⌋ . Vi delar in kurvan i segment [M,M + 2R] tills vi har täckt alla tal m ∈ [bK∆c + 1, √ n+ ∆]. Orsaken till att [1] väljer att definiera M,m0 och R som ovan är så att restermen inte övertar storleken på intervallet, med andra ord är resttermen . nr2/m3− ≤ nR2/M3 = ∆/(4M). Tar vi hänsyn till feltermen i problemformuleringen, (27), så har vi omformulerat problemet till att hitta r ∈ [−R,R] så att P (r) = ( nm0 − n m20 r) ∈ [−5∆/(4M), 5∆/(4M)] mod 1. Helfgotts val av K ≥ 5/2 fyller nu två syften: R ≥ 1 så att intervallen vi söker inte är tomma och 5∆/(4M) < 1/2 så att intervallet vi försöker pricka inte är hela R. Vi kan ställa ytterligare krav på r ∈ [−R,R] för att slippa gå över hela intervallet. Vad [1] gör är att hitta en approximation för α1 := −n/m20 på formen a/q där a, q är två relativt prima heltal med ett krav på nämnaren, q ≤ 2R. Detta är precis funktionen av en så kallad diofantisk approximation och för att förstå den här processen krävs förkunskaper om kedjebråk som kan hittas i appendix C. Med kedjebråksnotationen från appendix så vill vi omformulera α1 till ett enkelt kedjebråk, 〈a0, a1, . . . 〉. Följer vi algoritmen i [11, sats 21.5] så ges a0 av bα1c och om inte α1 är ett heltal, i vilket fall vi är färdiga, så blir resten 0 < α1− a0 < 1. Detta ger oss ξ1 := 1/(α1− a0) > 1 och vi kan återupprepa samma steg: låt a1 = bξ1c och ξ2 := 1/(ξ1 − a1) > 1. Genom att fortsätta på samma vis får vi en algoritm som genererar ett enkelt kedjebråk. Vi kan vara säkra på att algoritmen slutar av sig självt eftersom vi utvecklar kedjebråket av ett rationellt tal, α1 = −n/m20, som därav är ett ändligt kedjebråk (se [11, sats 21.5]) men vi vill 14 sannolikt avbryta processen redan tidigare. Vårt mål är att hitta en rationell approximation till α1 med nämnare q ≤ 2R och eftersom (qn)n>0 är en växande följd så kan vi välja att stoppa algoritmen när qn ≤ 2R men qn+1 > 2R. Del 2 av sats C.2 garanterar att vår approximation blir bättre för varje iteration och, för sådant n, så är ∣ ∣ ∣α1 − aq ∣ ∣ ∣ ≤ 1q·2R . Till sist observerar vi att konvergenterna, pn, qn, är relativt prima då del 2 av sats C.1 ger oss att (pn−1, qn−1) är en heltalslösning till den diofantiska ekvationen ax+ by = 1 där a = (−1)nqn, b = (−1)n−1pn, vilket endast är möjligt om högerledet, som här är lika med 1, är en multipel av största gemensamma nämnaren, (a, b), (ett resultat från elementär talteori, se förslagsvis [11, sats 3.1]). Ovanstående algoritm heter DiophAppr i [1] och beräknar en diofantisk approximation a/q av den ledande koefficienten α1 i P (r) med kravet på q som vi nämnde tidigare. Algoritmen returnerar täljare och nämnare separat samt passar på att beräkna a−1 (mod q) då del 2 av sats C.1 ger oss en möjlighet att räkna ut inversen i termer av konvergenterna. Målet med att introducera DiophAppr är så att vi kan gå från att leta lösningar till (27) i r ∈ [−R,R] till att endast leta bland ett urval av heltal. Vi har redan hittat en rationell approximation av den ledande koefficienten, α1, i P (r). Vi kan också approximera konstantkoefficienten α0 := n/m0 med bråket bα0q + 1/2c/q := c/q. Således ser vi att ∣ ∣q · P (r)− (c+ ar) ∣ ∣ = ∣ ∣ ∣ ∣ ∣ ( α1 − a q ) qr + (α0q − c) ∣ ∣ ∣ ∣ ∣ ≤ ∣ ∣ ∣ ∣α1 − a q ∣ ∣ ∣ ∣ q|r|+|α0q − c| ≤ 1q · 2R · qR+ 1 2 = 1 tack vare noggrannheten av den diofantiska approximationen, hur vi definierade c och att r ∈ [−R,R]. Därav, om P (r) ∈ [−5∆/(4M), 5∆/(4M)] mod 1 så medför det att c+ ar ∈ {−k − 1,−k, ..., k, k + 1} mod q där k = bq · 5∆/(4M)c. Det räcker alltså att sålla med r ≡ −a−1(c + j) (mod q) för heltal j ∈ [−k − 1, k + 1], där den multiplikativa inversen av a (mod q) tillhandahålls av DiophAppr. Vi har alltså sett hur [1] först sparar minnesplats genom att segmentera första delen av algo- ritmen och sedan tid i den andra delen genom att vara selektiv med vilka tal som vi sållar bort multiplar av. I det senare fallet finns som mest en multipel i intervallet, per konstruktion av K∆, och vi har visat att alla m = m0 + r med en multipel i intervallet har r ≡ −a−1(c + j) (mod q), för a, c, j definierade ovan. Däremot har vi inte visat det motsatta och det kan vara så att vissa r som genereras är falska lösningar orsakade av Taylor- och den diofantiska approximationen. Därför behöver vi kontrollera att multipeln av m ingår i intervallet, det vill säga att `m ∈ [n−∆, n+ ∆] och `m > m. (28) I nästa avsnitt kommer vi se vilka val som gick in i Python-implementationen av pseudokoden samt studera tidsbesparingar och möjliga förbättringar från originalalgoritmen. 8.2 Implementation av algoritmerna i Python Algoritmerna i [1] presenteras i form av pseudokod som för att kunna användas, måste översättas till något programmeringsspråk. Vår implementation av algoritmerna är skrivna i språket Python. Det var möjligt att översätta pseudokoden mer eller mindre ordagrant, vilket gjordes och resulterade i en första version av programmet. Därefter kunde flera förbättringar av koden göras för att korta ned dess körningstid. Vissa av förbättringarna var möjliga då pseudokoden i [1] är skriven i syfte att tydligt illustrera algoritmerna, och är således inte ämnad till att vara färdig, optimerad kod. Andra förbättringar var språkspecifika och åstadkoms genom att jämföra beräkningstiden hos olika funktioner och metoder i Python, för att sedan implementera de som visade sig vara snabba. Den förbättrade versionen av koden finns bifogad i appendix. Nedan följer, utan inbördes ordning, några av de gjorda förbättringar som har haft större inverkan. 15 • I den ursprungliga pseudokoden representeras den sållade mängden av en vektor bestående av booleaner, vilken vi har ersatt med en bitsträng. Denna idé föreslås redan i [1] och sparar i första hand minne, som i sin tur kan leda till snabbare beräkningar på grund av bättre användning av cache. Här användes Python-biblioteket Bitarray. • På vissa ställen har det varit möjligt att flytta ut beräkningar utanför loopar så att samma beräkning inte behöver göras flera gånger. Dessutom har flera beräkningar kunnat kortas ned eller skrivas ihop för att undvika temporära variabler. • I Python kan operatorn x//y användas för division utan rest. Denna har visat sig vara snabbare än sammansättningen floor(x/y) och har därför fått ersätta den senare där det varit möjligt. På ett liknande sätt har ceil(x/y) ersatts med -(x//-y). En ytterligare förbättring kunde göras genom att titta närmare på (28). För att en lösning m ska vara en äkta lösning måste alla villkor i (28) hålla och detta bör således kontrolleras i algoritmen. Men i själva verket är det överflödigt att kontrollera alla tre villkoren. Algoritmen konstruerar nämligen multipeln `m genom att sätta ` := b(n+∆)/mc, vilket direkt implicerar att `m ≤ n + ∆ alltid är uppfyllt. Vidare inspekterar vi villkoret `m > m, där vi har att `m > m ⇐⇒ ⌊n+ ∆ m ⌋ > 1 ⇐⇒ ⌊n+ ∆ m ⌋ ≥ 2 ⇐⇒ (n+ ∆)/2 ≥ m. Men m väljs ur intervallet [M,M + 2R] så det räcker med att undersöka vilka förhållanden som M + 2R ≤ (n + ∆)/2 är uppfyllt under: Vi har att M ≤ √ n+ ∆, R = bM √ ∆/4nc samt ∆ ≤ n vilket ger oss att M + 2R ≤ 2 √ n+ ∆. Detta är i sin tur mindre eller lika med (n + ∆)/2 om n+ ∆ ≥ 16. Att sålla efter primtal i en lista av positiva heltal mindre än 16 är ointressant. Därför kan vi rimligtvis introducera kravet n + ∆ ≥ 16 i början av NewSegSiev, så att `m > m alltid håller och därmed inte behöver testas senare i algoritmen. Det har följaktligen visat sig att av de tre villkor i (28), är två av dem alltid uppfyllda och behöver därmed inte kontrolleras. Det totala antalet gånger som detta steg utförs är O ( ∆ log n+ √ n/∆(log n)2 ) , enligt [1, s.346] och vi sparar således en betydande mängd tid på att reducera antalet beräkningar här till en tredjedel av det ursprungliga. För att visa att de förändringar som gjorts i koden, faktiskt har haft inverkan så lät vi utföra tester. Testerna gjordes på en hemdator och jämförde körningstid mellan den första versionen av programmet, mot en senare version där förbättringarna har införts. Som tidigare nämnts så sållar algoritmen fram primtal i ett angivet intervall [n − ∆, n + ∆] och dess tillvägagångssätt varierar något beroende på förhållandet mellan ∆ och n. Av denna anledning utfördes två stycken tester där detta förhållande sattes till att vara så stort som möjligt respektive så litet som möjligt. I det första testet valdes således ∆ := n och tre mätningar utfördes för n = 5 · 103, 5 · 105, 5 · 107. I det andra testet valdes ∆ := 3√n och n fick anta värdena 109, 1012 respektive 1015. För alla mätningar visade sig den förbättrade versionen vara minst 10 gånger så snabb som den ursprungliga versionen, dessutom visar mätningarna på en antydan till att denna faktor ökar då n växer. De uppmätta tiderna finnes i tabell 1. Givetvis är programmet inte perfekt och det finns flera knep som kan utforskas ifall ytterli- gare förbättring av koden eftertraktas. I den ursprungliga artikeln [1] nämns ett fåtal eventuella förbättringar, här ges ytterligare två stycken. • Istället för att flera gånger om låta SimpleSiev(M) generera en lista med alla primtal upp till M kan det eventuellt spara tid att generera en godtycklig lista vid start av programmet. Värdet på M överskrider inte √ K∆ + √ K∆, vilket gör denna taktik rimlig. Exempelvis tar en lista med alla primtal upp till en miljard omkring 1GB att spara och kan användas för n ≤ 1035, så länge som vi håller oss till något mindre interval där ∆ ≤ √n. Detta handlar självklart om en avvägning mellan hur snabbt det går att läsa in sparad data mot hur snabbt det går att beräkna den från grunden och bör undersökas mer innan idén tillämpas. • Flera beräkningar kan utföras parallellt, vilket redan föreslås i [1]. I synnerhet kan detta nyttjas i andra delen av NewSegSiev där oberoende beräkningar utförs för varje j ∈ [−k− 16 1, k + 1]. Dessa beräkningar är alla enkla och på samma form, och det kan således vara gynnsamt att överlåta dessa till datorns grafikkort. Detta eftersom grafikkortet ofta visar sig snabbare än processorn på att utföra denna typ av uppgifter. Tabell 1: Uppmätta körningstider för den första, respektive den förbättrade versionen av program- met. Programmet sållade fram alla primtal i ett intervall på formen [n−∆, n+ ∆] där ∆ = n för de tre första mätningarna och ∆ = 3√n för de tre sista. Den förbättrade versionen var snabbare än den första versionen med en faktor på minst 10, för alla mätningar. Intervall Körningstid i sekunder Utan förbättringar Med förbättringar [ 0, 104 ] 0.0236 0.0018 [ 0, 106 ] 1.9253 0.1002 [ 0, 108 ] 179.7834 9.2633 [ 109 ± 103 ] 0.1489 0.0142 [ 1012 ± 104 ] 2.4071 0.2319 [ 1015 ± 105 ] 78.1001 3.2894 I nästkommande avsnitt presenteras diverse resultat som erhållits ifrån körning av programmet. 8.3 Tillämpningar och resultat Genom rapportens gång har vi hänvisat till, och uppskattat fördelningen av, ett antal klasser av primtal och deras egenskaper. Nu kommer vi att redovisa några resultat som ovan nämnda Python- program givit. Vi börjar med att räkna primtal i ett intervall och jämföra det med primtalssatsen, detta i syftet att övertyga oss om kodens validitet. Sedan undersöker vi trovärdigheten hos en för- modad fördelning för mängden av primtalstvillingar. Slutligen redovisas frekvensen av primtalsgap, och mönster som uppstår från detta. 8.3.1 Fördelningen av primtal Vi börjar med att jämföra antalet primtal som hittats med NewSegSiev, mot fördelningen som ges av primtalssatsen, nämligen pi(x) ∼ Li(x) = ∫ x 2 1 log tdt. (29) För att skapa figur 3 använder vi vår implementering av Helfgotts kod och en enkel räknefunktion. Som vi ser i vänstra grafen av figur 3 är skillnaden mellan kurvorna nästan osynlig på makronivå, och eftersom primtalssatsen gäller är det troligt att vårt program har hittat det korrekta antalet primtal i intervallet. Att de inte ligger exakt på varandra är huvudsakligen beroende på felet vilket inte visas i (29). Notera att vi normaliserar felet vid början av intervallet eftersom vi betraktar skillnaden Li(x)− Li(n−∆), x ∈ [n−∆, n+ ∆]. Att vår kod hittar ungefär 100 färre primtal än förväntat efter 20 000 heltal och ungefär 2000 färre primtal efter 2.5× 109 heltal är mycket rimligt då felet i (29) kan som bäst vara O(2∆)1/2+ε), ε > 0, under antagandet att Riemannhypotesen stämmer [12, kap. 5]. Värdet på n valdes till 1019 för att detta är stort nog för att vara intressant men inte så stort att programmets körningstid blir orimlig1. Vi valde ∆ till 1.25× 109 får att nyttja de tidbesparingar som fås av att gå in i den andra loopen i NewSegSiev. Slutligen valde vi K till 2.5 för att det är minsta möjliga värde per konstruktion av algoritmen. Vi kommer nu att studera den data som programmet gav efter körning med ovanstående parametervärden. 1Att n inte valdes större i detta fallet är på grund av körningstiden för koden. 17 0.0 0.5 1.0 1.5 2.0 2.5Antal heltal som betraktasi intervallet 1019 ± 1.25× 109 ×109 0 1 2 3 4 5 6 Antal primta l ×107 Primtalsra¨knare vs. PrimtalssatsenNewSegSievPrimtalssatsen 0 2500 5000 7500 10000 12500 15000 17500 20000Antal heltal som betraktas i intervallet0 100 200 300 400 500 Antal primta l Skillnaden vid bo¨rjan av intervalletNewSegSievPrimtalssatsen 2.4999800 2.4999825 2.4999850 2.4999875 2.4999900 2.4999925 2.4999950 2.4999975 2.5000000Antal heltal som betraktas i intervallet ×109 5.71420 5.71425 5.71430 5.71435 5.71440 Antal primta l ×107 Skillnaden vid slutet av intervallet NewSegSievPrimtalssatsen Figur 3: I figuren till vänster redovisas antalet primtal som förväntas enligt primtalssatsen, orange, och antalet primtal som hittades enligt NewSegSiev, blå, då n = 1019, ∆ = 1.25·109, ochK = 2.5. Notera att kurvorna ligger nästan på varandra. I grafen till höger redovisas inzoomade versioner av grafen till vänster för att visa skillnaden mellan vår mätning och det som förväntas vid början av intervallet, där algoritmen returnerar kring 100 färre primtal än förväntat, och vid slutet av intervallet, där algoritmen returnerar kring 2000 färre. Dock att kurvorna inte ligger på varandra är väntat eftersom det finns ett fel i 29 vilket inte visas. 8.3.2 Fördelningen av primtalstvillingar Med hjälp av de primtal vi hittade i 8.3.1, vänder vi oss nu till primtalstvillingar. Det finns ingen sats för primtalstvillingar motsvarande primtalssatsen, dock så finns det en förmodan framlagd av Hardy och Littlewood [13, Förmodan B]. Den lyder pi2(x) ∼ 2C2 · Li2(x) = 2C2 ∫ x 2 1 (log t)2 dt (30) där C2 = 0.66016... är primtalstvillingskonstanten [14]. Jämför vi den hypotetiska fördelningen emot antalet primtalstvillingar vi har genererat, så får vi figur 4. Datan i figur 4 ger oss några intressanta insikter angående primtalstvillingar. Den första är att datan ger stöd till den hypotetiska fördelningen av primtalstvillingar. Kurvorna ligger mycket nära varandra och stödjer därmed hypotes 30, eftersom vi nu litar på vårt program. Skillnaden mellan det förväntade antalet primtalstvillingar och antalet som hittades är som mest ungefär 500, och hittas vid slutet av intervallet. I sammanhanget av ett intervall av längd 2.5 × 109 så är en skillnad av 500 ekvivalent med en avvikelse av 2 × 10−7 mer primtalstvillingar per heltal än vad som förväntades. Att antalet primtalstvillingar blir större än det hypotetiskt förväntade antalet vid slutet på intervallet beror möjligen på att vi avrundar C2 till 0.66 i kombination med att vi normaliserar felet vid början av intervallet precis som i föregående tillämpning. Dock så kunde avrundningen av C2 tillsammans med normaliseringen av felet också ha ökat antalet förväntade primtalstvillingar till mer än vad det egentligen skulle vara. I sin tur leder detta till att förmodan verkar stödjas av vår implementering mer än vad den borde. Den andra insikten som grafen ger är kopplad till avsnitt 4.3 där vi visade att primtalstvil- lingarna är en relativt liten andel av primtalen. Låt oss undersöka detta genom att jämföra figur 3 och 4. Vi ser direkt att bland de första 20 000 heltalen som betraktas, så finns det drygt 400 primtal och 14 primtalstvillingar. Detta är en faktor på ungefär 30, och tittar vi istället vid slutet av intervallet ser vi att denna faktor ökat till ungefär 33. 18 0.0 0.5 1.0 1.5 2.0 2.5Antal heltal som betraktasi intervallet 1019 ± 1.25× 109 ×109 0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 Antal primta lstvilli ngar ×106 Primtalstvillingra¨knare vs.Hypotestisk Fo¨rdelningNewSegSiev + FilterPrimtalstvillingsfo¨rmodan 0 2500 5000 7500 10000 12500 15000 17500 20000Antal heltal som betraktas i intervallet0 2 4 6 8 10 12 14 Antal primta lstvilli ngar Skillnaden vid bo¨rjan av intervalletNewSegSiev + FilterPrimtalstvillingsfo¨rmodan 2.4999800 2.4999825 2.4999850 2.4999875 2.4999900 2.4999925 2.4999950 2.4999975 2.5000000Antal heltal som betraktas i intervallet ×109 1.7242 1.7243 1.7244 1.7245 1.7246 Antal primta lstvilli ngar ×106 Skillnaden vid slutet av intervallet NewSegSiev + FilterPrimtalstvillingsfo¨rmodan Figur 4: I grafen till vänster redovisas antalet primtalstvillingar som förväntas enligt den hypo- tetiska fördelningen, orange, och de primtalstvillingar som hittades enligt NewSegSiev, blå, då n = 1019, ∆ = 1.25 × 109, och C2 har avrundats till 0.66. Notera återigen att kurvorna ligger nästan på varandra. I graferna till höger så redovisas inzoomade versioner av grafen till vänster. Översta grafen till höger visar skillnaden mellan antalet primtalstvilling vi har hittat och antalet som förväntas vid slutet av intervallet, där algoritmen returnerar 500 fler primtalstvillingar. Ef- ter de första 20 000 heltalen i intervallet så har algoritmen genererat nästan det exakta antalet primtalstvillingar som förväntas. Vi kan inte använda vår kod som bevis för den förmodade fördelningen av primtalstvillingar. Dock så ger den oss en känsla för om fördelningen verkar rimlig på detta intervall, vilket den gör. Vi kan också få en känsla för hur få primtalstvillingar det finns jämfört med antalet primtal, vilket kan göra det lättare att acceptera Bruns sats (sats 5.2). 8.3.3 Frekvens av primtalsgap Vi fortsätter undersöka och illustrera egenskaper hos vår genererade data, genom att studera fre- kvensen av primtalsgap. Ett primtalsgap är avståndet mellan ett primtal och det efterföljande primtalet. Det går att visa, med hjälp av primtalssatsen, att det förväntade avståndet mellan ett primtal pn och nästa, pn+1, är log pn. Vi jämför nu detta med den data som vi genererat, se figur 5. I figur 5 får vi några insikter kring beteendet av primtalsgap i vårt intervall. En kanske överas- kande aspekt av grafen är hur rak den är efter logaritmering av y-axeln. Detta antyder att frekven- sen på primtalsgap minskar exponentiellt då dess längd ökar. Vi ser att det vanligaste storleken på ett primtalsgap i intervallet är 6 och att det störta gapet är 668. En detalj som är svår att utläsa från figuren är att det för varje jämnt tal upp till och inklusive 560, finns ett primtalsgap i intervallet med denna storlek. Enligt primtalssatsen är den förväntade storleken på ett primtalsgap i intervallet ungefär 43.7491, och om vi beräknar den genomsnittliga storleken på primtalsgap i vårt intervall så får vi det till 43.7505. Återigen stödjer detta resultat legitimiteten av vår kod eftersom datan reflekterar vad som har bevisats i primtalssatsen. Om vi återgår till primtalstvillingar så säger figuren även något om dem. Dessa representeras av primtalsgap med storlek 2, vilket är det sjunde vanligaste primtalsgapet och utgör 3 procent av alla gap i intervallet. Till sist ger figur 5 intuition för en sats som omnämndes kortfattat i inledningden och säger att det finns oändligt många par av primtal med maximalt 600 steg emellan sig. Detta betyder attdet 19 0 25 50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 500 525 550 575 600 625 650 675 700Storlek p˚a primtalsgap 100 101 102 103 104 105 106 Frekve ns Frekvensen av primtalsgap i intervallet Figur 5: I figuren redovisas frekvensen av primtalsgap i intervallet [n − ∆, n + ∆], då n = 1019 och ∆ = 1.25 · 109. Notera att y-axeln är logaritmerad på grund av den höga frekvensen av små primtalsgap. De orange prickarna anger frekvensen på primtalsgap vars storlek är en primorial (en produkt av de första n primtalen). Röda linjen markerar den genomsnittliga storleken på primtalsgap i vårt intervall vilket är 43.705. även för stora primtal finns så finns det relativt små primtalsgap. I vårt intervall är nästan alla primtalsgap mindre än 600, trots att talen i intervallet är stora. Satsen bevisades med hjälp av nya sållmetoder, specifikt Goldston-Pintz-Yıldırım-metoder utvecklades som år 2005 [15]. I Maynards artikel används vikter liknande de som finns i Selbergs såll, fast på en ännu mer allmän form. Sedan 2005 så har 600 steg reducerades ned till 246. Ett mål med att fortsätta minska längden är att en dag reducera det till 2 och därmed bevisa primtalstvillingshypotesen. Såsom mycket annat angående primtal, finns det även en förmodan kopplad till dessa frekvenser ovan och vilket primtalsgap som är mest frekvent upp till en given gräns. Som vi ser i figur 5 är 6 (den andra orange pricken) den mest frekventa storleken på primtalsgap i vårt intervall, och speciellt med talet 6 är att det är produkten av de första två primtalen. Vi ser också att 30 (den tredje orange pricken) vilket är produkten av de första 3 primtalen, hoppar upp lite från översta delen av bandet, och på samma vis är 210 (den fjärde orange pricken) nästa tal med detta beteende. Förmodan är då att varje primorial, produkten av de första m primtalen, någon gång blir "hoppmästare". Förmodan har undersökts direkt med hjälp av numeriska uppskattningsmetoder [16] som har lyckats visa att 6 är hoppmästaren fram till ≈ 1.74 · 1035 och att 30 sedan tar över titeln fram till ≈ 10425. 20 Referenser 1. Helfgott HA. An Improved Sieve Of Eratosthenes. Mathematics Of Computation 2020; 89(321):333–50. doi: 10.1090/mcom/3438 2. Chen JR. On the representation of a large even integer as the sum of a prime and the product of at most two primes. Kexue Tongbao 1966; 11(9):385–6 3. Maynard J. Small gaps between primes. Annals of Mathematics 2015; 181(1):383–413. doi: 10.4007/annals.2015.181.1.7 4. Cojocaru AC, Murty MR. An Introduction to Sieve Methods and Their Applications. Cam- bridge: Cambridge University Press, 2005 5. Friedlander J, Iwaniec H. Opera de cribro. Providence, Rhode Island: American Mathematical Society, 2010 6. Tenenbaum G. Introduction à la théorie analytique et probabiliste des nombres. (Français) [Introduction to Analytic and Probabilistic Number Theory]. 3. utg. Providence, Rhode Is- land: American Mathematical Society, 2015 7. O’Connor JJ, Robertson EF. Maths history, Viggo Brun. 2014 Mar. [citerad 2021-05-14]. Hämtad från: https://mathshistory.st-andrews.ac.uk/Biographies/Brun/ 8. Titchmarsh EC. A divisor problem. Rend. Circ. Mat. Palermo 1930; 54:414–29 9. Tao T. 254A, Notes 1: Elementary multiplicative number theory. 2014 Nov. [citerad 2021-05-14]. Hämtad från: https://terrytao.wordpress.com/2014/11/23/254a-notes- 1-elementary-multiplicative-number-theory/#more-7855 10. Friedlander J, Iwaniec H. The Polynomial X2 + Y4 Captures Its Primes. Annals of Mathe- matics 1998 Nov; 148(3):945–1040. doi: 10.2307/121034 11. Lindahl LÅ. Elementär talteori. Uppsala, 2012 12. Hildebrand AJ. Introduction to Analytic Number Theory. 2005. [citerad 2021-05-14]. Hämtad från: http://www.math.uiuc.edu/~hildebr/ant 13. Hardy G, Littlewood J. Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes. Acta Mathematica 1923; 44:1–70. doi: 10.1007/BF02403921 14. Inc. OF. The On-Line Encyclopedia of Integer Sequences. 2019. [citerad 2021-05-14]. Hämtad från: https://oeis.org/A005597 15. Goldston DA, Pintz J, Yildirim CY. Primes in Tuples I. Annals Of Mathematics 2009; 170:819–57 16. Odlyzko A, Rubinstein M, Wolf M. Jumping Champions. Experimental Mathematics 1999; 8(2):107–9 21 A Ordonotation I den här uppsatsen gör vi flitig användning av ordonotation för att beteckna olika asymptotiska gränser. För D ⊂ C och två funktioner, f : D → C och g : D → R+ skriver vi f(x) = O(g(x)) om det finns A > 0 så att ∣ ∣f(x) ∣ ∣ ≤ Ag(x),∀x ∈ D. Omväxlande skriver vi även f(x) g(x) med samma betydelse som ovan. Om vi har att f(x) g(x) och g(x)  f(x) så skriver vi f(x)  g(x). Sist så kallar vi f(x) och g(x) för asymptotiskt ekvivalenta och skriver f(x) ∼ g(x) om g(x) är nollskild för alla x > x0, för någon konstant x0, och limx→∞ f(x)g(x) = 1. B Några användbara resultat B.1 Partiell summation Följande sats är hämtad från [4, Sats 1.3.1] dock så ger vi lite mer förklaring i beviset. Sats B.1. Låt c1, c2, ... vara en foljd av komplexa tal och sätt S(x) := ∑ n≤x cn. Låt n0 vara ett fixt positivt heltal. Om cj = 0 för j < n0 och f : [n,∞) −→ C har en kontinuerlig derivata i [n0,∞), då för något heltal x > n0 har vi att ∑ n≤x cnf(n) = S(x)f(x)− ∫ x n0 S(t)f ′(t)dt. Bevis. Vi bevisar satsen genom att först inse att cn = S(n)− S(n− 1). Vi kan därför skriva om vänsterleden i satsen till ∑ n≤x cnf(n) = ∑ n≤x (S(n)− S(n− 1))f(n) = ∑ n≤x S(n)f(n)− ∑ n≤x−1 S(n)f(n+ 1) = S(x)f(x) + ∑ n≤x−1 S(n)f(n)− ∑ n≤x−1 S(n)f(n+ 1) = S(x)f(x)− ∑ n≤x−1 S(n)(f(n+ 1)− f(n)) = S(x)f(x)− ∑ n≤x−1 S(n) ∫ n+1 n f ′(t)dt = S(x)f(x)− ∫ x n0 S(t)f ′(t)dt Att vi kan flytta in S(x) i integralen beror på att S(x) är en stegfunktion och är konstant på intervaller på formen [n, n+ 1). B.2 Summan av primtalsreciproker Avsnitt 4.1 introducerar dimensionen av ett såll, κ, som ska uppfylla (5). Vi visar här ett resultat tillskrivet Tjebysjov, hämtat ur [4, Sats 1.4.3], som hjälper till vid kontroll av detta. 22 Sats B.2. ∑ p≤n log p p = log n+O(1). Bevis. Nyckeln till beviset av ovanstående sats i [4] är två observationer om fakultetfunktionen, n! = 1 · 2 · ... · n. Först vill vi omformulera n! som en produkt av primtalspotenser. Eftersom det finns bn/pαc multiplar av pα som är mindre än eller lika med n och inga sådana multiplar av pα för α > log n/ log p, ser vi att den bidragande faktorn för varje p ≤ n kan skrivas som ∏ pα||k k≤n pα = ∏ pα≤n pbn/pαc = pbn/pc+bn/p2c+...+bn/pblogn/ log pcc där pα || k betyder att α är den största heltalsexponenten så att pα delar k. Detta ger oss att log n! = ∑ p≤n (⌊n p ⌋ + ⌊ n p2 ⌋ + ...+ ⌊ n/pblogn/ log pc ⌋ ) log p vari en restterm kan urskiljas och uppskattas till ∑ p≤n (⌊ n p2 ⌋ + ...+ ⌊ n/pblogn/ log pc ⌋ ) log p ≤ ∑ p≤n   n p2 ∞∑ k=0 1 pk   log p = n ∑ p≤n 1 p2 · log p 1− 1/p  n. Den första observationen är alltså att log n! = n ∑ p≤n log p p +O(n). (31) Den andra observationen ser vi genom att utföra en partiell summation, log n! = log ( ∏ k≤n k ) = ∑ k≤n 1 · k = bnc log n− ∫ n 1 btc t dt och att btc = t+O(1) ger att detta är lika med (n+O(1)) log n− ∫ n 1 t tdt+O(1) ∫ n 1 1 t dt = n log n− n+O(log n). (32) Sätter vi samman observationerna, (31) och (32) får vi n ∑ p≤n log p p +O(n) = n log n− n+O(log n) n ∑ p≤n log p p = n log n+O(n) vilket efter division med n ger det önskade resultatet. När vi hanterar Eratosthenes generaliserade såll, sats 4.2, och Bruns såll, sats 5.1, resulterar det ofta i att vi vill uppskatta W (z)-funktionen. En användbar sats för detta är [4, Sats 1.4.4] som säger Sats B.3. ∑ p≤n 1 p = log n+O(1). 23 Bevis. Låt ck := { log p för k = p 0 annars då får vi att S(x) = ∑ k≤x ck är lika med summan i sats B.2. Om vi använder föregående sats efter en partiell summation så ser vi att ∑ p≤n 1 p = S(n) log n + ∫ n 2 S(t) t(log t)2 dt = log n+O(1) log n + ∫ n 2 log t t(log t)2 dt+ ∫ n 2 O(1) t(log t)2 dt = O(1) + [log log t]n2 +O(1) [ − 1log t ]n 2 = log log n+O(1). B.3 Asymptotiskt beteende för W(z), ett specialfall Följande sats beskriver det asymptotiska beteendet hos W (z) i specialfallet då ω(2) = 1 och ω(p) = 2 för primtal p > 2. Resultatet används i (5.2) samt (4.3) och idéerna till beviset är hämtade från beviset av Merten’s Theorem i [4, kap.5.2]. Sats B.4. Antag att ω(2) = 1 och ω(p) = 2 för alla primtal p > 2, och definiera W (z) := ∏ p 0 för i > 0. I den här uppsatsen berör vi endast särfallet då a0, a1, ..., an är heltal vilket då kallas för ett enkelt kedjebråk. En omedelbar utmaning är att, givet ett kedjebråk 〈a0, a1, ..., an〉, beräkna 〈a0, a1, ..., an+1〉 utan att räkna om hela kedjebråket från term an+1 till a0. Lösningen på det här problemet är så kallade konvergenter, [11, Definition 20.4], och definieras som ett par (pn, qn), där p−2 = 0, p−1 = 1, pn = anpn−1 + pn−2 då n ≥ 0 q−2 = 1, q−1 = 0, qn = anqn−1 + qn−2 då n ≥ 0, och deras kvot, cn := pn/qn, n ≥ 0. Observera att definitionen ger oss att q0 = 1 och (qn)Nn=1 är en strikt växande följd av heltal om motsvarande kedjebråk är enkelt. Anledningen till att vi introducerar konvergenter ges av följande sats, [11, Sats 20.5i) och ii)], Sats C.1. Låt (an)Nn=0 vara en följd av reella tal där ai > 0 för i > 0 och (pn, qn) är deras respektive konvergenter. Då gäller att 1. 〈a0, a1, ..., an〉 = cn för alla n ≥ 0, 2. pnqn−1 − pn−1qn = (−1)n−1 för alla n ≥ −1. Bevis. Vi följer här beviset från [11]. (i): För att visa det första påståendet använder vi ett induktionsargument. Vi ser att påståendet håller för n = 0 ty 〈a0〉 = a0 och c0 = p0/q0 = (a0 · 1 + 0)/1 = a0. Antag nu att påståendet gäller för kedjebråk, 〈a0, a1, ..., an〉, med n+ 1 stycken element. Vi ska visa att detta medför att 〈a0, a1, ..., an, an+1〉 = cn+1. Vi gör detta genom att skriva om det sista elementet i kedjebråket så att vi får samma kedjebråk fast med n+ 1 stycken element, 〈a0, a1, ..., an, an+1〉 = 〈a0, a1, ..., an + 1/an+1〉. (36) Låt a′n beteckna det nya kedjebråkets (n + 1):te element. Det nya kedjebråket har då samma konvergenter upp till index n. Vi skriver den sista konvergenten som c′n = p′n/q′n. Alltså, per 26 induktionsantagandet, har vi c′n = p′n q′n = ( an + 1/an+1 ) pn−1 + pn−2 ( an + 1/an+1 ) qn−1 + qn−2 = an+1 (anpn−1 + pn−2) + pn−1an+1 (anqn−1 + qn−2) + qn−1 = an+1pn + pn−1an+1qn + qn−1 vilket är definitionen av cn+1 = pn+1/qn+1. Därav ger (36) att 〈a0, a1, ..., an, an+1〉 = cn+1 Det följer nu av induktion att 〈a0, a1, ..., an〉 = cn för alla n ≥ 0. (ii): För det andra påståendet gör vi ett till induktionsbevis. Vi börjar den här gången med att kolla basfallet n = −1, p−1q−2 − p−2q−1 = 1 · 1− 0 · 0 = (−1)−2 vilket stämmer med påståendet vi vill visa. Härnäst antar vi att zn := pnqn−1 − pn−1qn = (−1)n−1 för något n och vill visa att zn+1 = (−1)n. Detta är lätt att se med hjälp av den rekursiva definitionen av konvergenterna: zn+1 = pn+1qn − pnqn+1 = (anpn + pn−1)qn − pn(anqn + qn−1) = pn−1qn − pnqn−1 = −zn. Således ger induktionsantagandet att zn+1 = (−1) · (−1)n−1 vilket skulle visas och påståendet följer av induktion. Sats C.1 säger oss något om hur konvergenter och kedjebråk är relaterade. Vi kan nu använda den kunskapen för att säga hur väl vi kan approximera kedjebråk genom trunkering [11, sats 20.9]. Sats C.2. Låt (an)Nn=0 vara en följd av heltal med positiva termer då n > 0 och med konvergenter pn/qn = cn. Kedjebråket ξ = 〈a0, a1, . . . , aN 〉 uppfyller då för alla n ≥ 0 1. c2n < ξ < c2n+1 för 2n+ 1 < N , 2. |ξ − cn| < 1qnqn+1 . Bevis. (i): Vi börjar med att se att (ii) i sats C.1 ger oss, för n ≥ 1, pnqn−1 − pn−1qn = (−1)n−1 pn qn − pn−1qn−1 = (−1) n−1 qn−1qn (37) där sista vänsterledet är lika med cn − cn−1. Då qn−1qn är en produkt av två positiva tal medför detta att c2n < c2n−1 för n ≥ 1. Vidare, för n ≥ 2, får vi (cn − cn−1) + (cn−1 − cn−2) = (−1)n−1 qn−1qn + (−1) n−2 qn−2qn−1 cn − cn−2 =(−1)n qn − qn−1 qn−2qn−1q = (−1)nAn där An är en positiv konstant eftersom (qn)Nn=0 är en strikt växande följd av positiva tal. Alltså har vi att delföljden (c2n)bN/2cn=0 är strikt växande och delföljden av udda index, (c2n+1) b(N−1)/2c n=0 , är strikt avtagande. Sammantaget ger detta oss att c0 < c2 < c4 < ... < cN = ξ < ... < c5 < c3 < c1 vilket bevisar (i). (ii): Från första delen har vi att ξ ∈ [cn+1, cn] så att |ξ − cn| ≤|cn+1 − cn| och högerledet är enligt (37) lika med 1/(qnqn+1). 27 D Python-kod tillhörande avsnitt 8 D.1 Vår förbättrade version av programmet Nedan följer väsentliga delar av den förbättrade versionen av programmet som omnämns i 8.2. Koden är skrivet i Python och är en tolkning av den pseudokod som Helfgott presenterar i [1]. Om läsaren vill testa programmet kan all nedanstående kod förslagsvis läggas i samma fil. För att programmet ska fungera behöver Python-bibliotek Bitarray vara installerat. Vi börjar med import av några externa funktioner, detta ska göras först i koden för att de senare funktionerna ska fungera. Biblioteket bitarray ger oss möjlighet att arbeta direkt med bitsträngar och funktionen zeros(N) konstruerar en sådan bitsträng bestående av N stycken nollor. Funktionerna sqrt och floor ger kvadratroten respektive golvfunktionen av ett tal och isqrt returnerar heltalsdelen av kvadratroten. 1 from bitarray import bitarray 2 from bitarray.util import zeros 3 from math import floor, sqrt, isqrt Härnäst följer algoritmerna vars funktion beskrivs i 8.1, på flera rader finns det extra kommen- tarer (på engelska) som förklarar radens syfte. Alla funktioner, med undantag för DiophAppr, returnerar en bitsträng. Strängen representerar något sållat heltalsintervall [a, b] där biten med index i är en nolla om talet i+ a har sållats bort och en etta annars. SimpleSiev Detta är det vanliga Eratosthenes såll. Funktionen tar in ett heltal N och returnerar en lista med alla primtal i intervallet [0, N ]. Exempelvis ger SimpleSiev(7) svaret 00110101 vilket representerar alla primtal från 0 till 7. 1 def SimpleSiev(N): # Traditional Sieve of Eratosthenes 2 P = zeros(N+1) # Create bitarray of N+1 '0's, representing numbers 0 to N 3 P[2] = True # Set 2 to '1' 4 P[3::2] = True # Set odd numbers >1 to '1' 5 for num in range(3, isqrt(N)+1, 2): 6 if P[num]: P[num*num::2*num] = False # Set odd mult's of num to '0' 7 return P SimpleSegSiev Denna funktion tar in tre argument; n, ∆ och M . Därefter returnerar den en lista vilken represen- terar alla tal i intervallet [n, n+ ∆] som antingen är prima eller saknar delare mindre än, eller lika med M . Använder vi notation från avsnitt 3, representerar denna lista mängden S(A,P, z) där A = [n, n+ ∆], z = M och P är mängden av alla primtal. För att utföra sållningen behövs alltså alla primtal i intervallet [0,M ]. Dessa genereras av SimpleSiev som åkallas på rad 5. 1 def SimpleSegSiev(n, Delta, M): 2 S = zeros(Delta+1) 3 S.setall(True) # Set all bits in S to '1' 4 if n <= 1: S[0:2-n] = False # Set 0 and 1 to '0' if present 5 Primes = SimpleSiev(M) # Get list of primes up to M 6 for p in Primes.itersearch(bitarray('1')): # Iterate through primes 7 S[max(-(n//-p), 2)*p - n::p] = False # Set multiples of p to '0' 8 return S SubSegSiev Denna funktion är exakt som SimpleSegSiev gällande indata och utdata. Skillnaden mot först- nämnda är att intervallet [0,M ] delas upp i mindre delintervall. Funktionen tar sedan ett delinter- vall i taget, skapar en lista med alla primtal i delintervallet för att sedan sålla med hjälp av dessa 28 primtal. På så sätt behöver inte alla primtal i intervallet [0,M ] ligga i arbetsminnet på samma gång. För att generera listorna används SimpleSegSiev. 1 def SubSegSiev(n, Delta, M): 2 S = zeros(Delta+1) 3 S.setall(True) 4 if n <= 1: S[0:2-n] = False 5 D_s = isqrt(M) # Size (-1) of each segment 6 for M_s in range(1, M+1, D_s+1): # Iterate through segments 7 Primes = SimpleSegSiev(M_s, min(M-M_s,D_s), isqrt(M_s+D_s)) # Get primes in segment 8 for p in Primes.itersearch(bitarray('1')): # Iterate through primes 9 p = p+M_s # shift p to get the actual prime number 10 S[max(-(n//-p),2)*p-n::p] = False 11 return S NewSegSiev Detta är algoritmens huvudfunktion. Den tar in tre argument; n, ∆ och K, och returnerar alla primtal i intervallet [n − ∆, n + ∆]. Det sista argumentet K ska vara ett flyttal större eller lika med 2.5 och påverkar hur funktionen går tillväga för att sålla. Funktionen sållningen sker i två delar. Först sållas intervallet för multiplar av primtal mindre än eller lika med K∆. Detta utförs av SubSegSiev och sker på rad 16. Därefter sållas intervallet för resterande tal, vilket är multiplar av tal mellan K∆ och √ n+ ∆. Detta görs med hjälp av DiophAppr i while-loopen som börjar på rad 17 och slutar på rad 31. 1 def NewSegSiev(n, Delta, K): # Main algorithm 2 # Argument parsing: 3 if n**(1/3)>=Delta or Delta>n: 4 raise Exception("Delta should be between n^(1/3) and n") 5 if K < 2.5: 6 raise Exception("K must be at least 2.5") 7 if n+Delta < 16: 8 raise Exception("n + Delta must be at least 16") 9 10 # Calculation of some repeatedly used values: 11 upper, lower = n+Delta, n-Delta 12 f = sqrt(Delta/(4*n)) 13 bound1 = isqrt(upper) 14 15 M = floor(K*Delta) + 1 16 S = SubSegSiev(lower, 2*Delta, M-1) # SubsegSiev sieves by primes < M 17 while M <= bound1: # Sieve by the larger primes not covered by SubSegSiev 18 R = floor(M*f) 19 m0 = M + R 20 alpha0 = n/m0 % 1 21 alpha1 = -n/(m0*m0) % 1 22 ainv, q = DiophAppr(alpha1, 2*R) 23 c = floor(alpha0*q + 0.5) 24 k = floor(5*Delta*q/(4*M)) # Need int-type. floor(x/y) is faster than int(x//y) 25 bound2 = M + 2*R + 1 26 for j in range(-k-1, k+2): 27 r0 = -ainv*(c+j) % q 28 for m in range(m0+r0-((m0+r0-M)//q)*q, bound2, q): # for m in the intersection 29 n_s = (upper//m)*m - lower 30 if n_s >= 0: S[n_s] = False # Checking n_s <= n+Delta and n_s > m is redundant 31 M = bound2 32 return S DiophAppr Denna funktion tar in två tal; α och Q, och beräknar en rationell approximation a/q av α med hjälp av kedjebråk. Heltalen a och q uppfyller (a, q) = 1 samt att q ≤ Q och ∣ ∣a/q − α ∣ ∣ ≤ 1/qQ. Funktionen returnerar talparet (q, a−1) där a−1 är den multiplikativa inversen till a modulo q. 29 1 def DiophAppr(alpha, Q): 2 b = p = floor(alpha) 3 q = p_m = s = 1 4 q_m = 0 5 while q <= Q: 6 if alpha == b: 7 return -s*q_m, q 8 alpha = 1/(alpha-b) 9 b = floor(alpha) 10 p, q, p_m, q_m, s = b*p+p_m, b*q+q_m, p, q, -s 11 return s*q, q_m D.2 Några extra funktioner RemoveNonTwins Här presenteras den funktion som använts i 8.3. Denna tar in en redan sållad lista med primtal och sållar bort alla primtal p där p + 2 inte är prima. De tal i listan som är kvar efter detta är primtalstvillingarna i intervallet. Om det sista eller näst sista talet i listan är prima så är det omöjligt för funktionen att avgöra om talet är ett tvillingprimtal eller ej, funktionen sållar inte bort talet men utfärdar en varning om att detta har inträffat. 1 def RemoveNonTwins(S): # Sieve for twin primes in prime list. 2 # If the last or second to last number in the given list is prime, 3 # then that prime won't get removed even though it might not be a twin prime. 4 from bitarray import bitarray 5 try: # Removes 2 if present 6 # Searches bits 0-3 for occurrence of '11' corresponing to primes 2,3 7 # then replaces '11' with '01' 8 two = S.search(bitarray('11'),3) 9 S[two[0]] = False 10 except: 11 pass 12 for i in S.itersearch(bitarray('100')): # Replaces strings of 100 to 000 in bitarray S 13 S[i:i+3] = False 14 if S[-1]|S[-2]: 15 print("Warning! The last prime in the list may not be a twin prime.") 16 return Till sist ger vi även en modifierad version av NewSegSiev och SubSegSiev som vi har valt att ge namnen NewSegSievTwins respektive SubSegSievTwins. Som namnet antyder kan New- SegSiev användas för att från grunden sålla fram alla primtalstvillingar i det angivna intervallet och funktionen brukas på samma sätt som NewSegSiev. Funktionen SubSegSievTwins är nöd- vändig för att NewSegSievTwins ska fungera. NewSegSievTwins 1 def NewSegSievTwins(n, Delta, K): # Sieve for twin primes, small mod of NewSegSiev 2 if n**(1/3)>=Delta or Delta>n: 3 raise Exception("Delta should be between n^(1/3) and n.") 4 if K < 2.5: 5 raise Exception("K must be at least 2.5") 6 if n+Delta < 16: 7 raise Exception("n + Delta must be at least 16") 8 upper = n+Delta 9 lower = n-Delta 10 f = sqrt(Delta/(4*n)) 11 bound1 = sqrt(upper) 12 M = floor(K*Delta) + 1 13 S = SubSegSievTwins(lower, 2*Delta, M-1) 14 while M <= bound1: 15 R = floor(M*f) 16 m0 = M + R 17 alpha0 = n/m0 % 1 30 18 alpha1 = -n/(m0*m0) % 1 19 ainv, q = DiophAppr(alpha1, 2*R) 20 c = floor(alpha0*q + 0.5) 21 k = floor(5*Delta*q/(4*M)) 22 bound2 = M + 2*R + 1 23 for j in range(-k-1, k+2): 24 r0 = -ainv*(c+j) % q 25 for m in range(m0+r0-((m0+r0-M)//q)*q, bound2, q): 26 n_s = (upper//m)*m 27 if n_s >= lower+2: # both n_s and its twin n_s-2 is in the interval 28 S[n_s - lower] = False 29 S[n_s-2 - lower] = False 30 elif n_s >= lower: # n_s is in the interval but not n_s-2 31 S[n_s - lower] = False 32 if n_s+m-2 <= upper: # the twin to the next multiple of m is in the interval 33 S[n_s+m-2 - lower] = False 34 M = bound2 35 return S NewSegSievTwins 1 def SubSegSievTwins(n, Delta, M): # Sieve for twin primes, small mod of SubSegSiev, needed in NewSegSievTwins 2 S = zeros(Delta+1) 3 S.setall(True) 4 S[0:2-n] = False 5 D_s = isqrt(M) 6 for M_s in range(1, M+1, D_s+1): 7 Primes = SimpleSegSiev(M_s, D_s, isqrt(M_s+D_s)) 8 for p in Primes.itersearch(bitarray('1')): 9 p = p+M_s 10 start = max(-(n//-p),2)*p-n 11 S[start::p] = False 12 if start-2<0: 13 start = start+p 14 S[start-2::p] = False 15 return S 31