{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" 18 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Helvetica" 0 12 0 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 32 35 32 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "# SELFRIDG.MS\n" } {TEXT -1 723 "## Is 2^p-1 prime for infinitely many p? ##\n# I s 2^(2^n)+1 prime for some n > 4? #\n# \+ #\n# John B. Cosgrave, #\n # Department of Mathematics, #\n# St. Patric k's College, #\n# Drumcondra, \+ #\n# Dublin 9, #\n# IRE LAND. #\n# \+ #\n# Home e-mail: johnbcos@iol.ie #\n# Coll ege e-mail: John.Cosgrave@spd.ie #\n# \+ #\n# 2^sqrt(2) is transcendental. Pi(x)~x/ln(x). # \+ \n## .12345678910111213 ... is normal. Is Pi? ##\n\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 153 "This worksheet illustrates Selfridge's i mprovement of the Lucas-Kraitchik-Lehmer theorem in \nproving primalit y. [At the end there is a 216-digit prime.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "The first procedure looks for p rime numbers of the form:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 28 "2*3*3*5*5*5*7*7*7*7 ... + 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "test := proc(n)" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local k;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "for k to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "i f isprime(product(ithprime(r)^r, r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "then print(k, product(ithprime(r)^r, r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "fi od end:" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "test(16);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"\"\"\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"# \"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$\"%^A" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "2*3*3 + 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "2*3*3*5*5*5 + 1; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"%^A" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "In the following procedu re (where the powers to which the primes are raised go 1, 2, 1, 2, 1, \+ 2 ... ) - 'One_Two' - at ones like:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 38 "2*3*3*5*7*7*11*13*13*17*19*19 ... + 1:" }}{PARA 2 "" 0 "" {TEXT -1 1 "\n" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "One_Two := proc(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local k;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "for k to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "if isprime(product(ithprime(r)^(1 + irem(r + 1, 2)), \+ r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "then print(k, pro duct(ithprime(r)^(1 + irem(r + 1, 2)), r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "fi od end:" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 12 "One_Two(30);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\" \"\"\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"#\"#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"'\"(\">)>)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$ \"#5\"0\"HOZm!>t*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#8\"76P')z/X$y] Lp\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#<\"AJ]BS]0e:h$\\w._)QC" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 121 "And now at ones where th e powers go 2, 1, 2, 1, 2, 1 ... , so producing numbers like 2*2*3*5*5 *7*11*11*13*17*17* ... + 1:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Two_One := proc(n)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local k;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "for k t o n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "if isprime( product(ithpr ime(r)^(1 + irem(r, 2)), r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "then print(k, product(ithprime(r)^(1 + irem(r, 2)), r = 1..k) \+ + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "fi od end:" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Two_One(30);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"\"\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\" \"#\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"3,.B&42$4uE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#:\"=,.ku9" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Two_One(50);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"\"\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"#\"# 8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#6\"3,.B&42$4uE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#:\"=,.ku9" }}{PARA 11 " " 1 "" {XPPMATH 20 "6$\"#J\"eo,^2#z$\\Y*Gdo(\\+BZOz@Bx!eX=*[%\\mc6PI/2 :nT$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "I'm going to take the last of those:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 67 "Two_One[31]:=product(ithprime(r)^(1 + irem(r , 2)), r = 1..31) + 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%(Two_One G6#\"#J\"eo,^2#z$\\Y*Gdo(\\+BZOz@Bx!eX=*[%\\mc6PI/2:nT$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "length(Two_One[31]);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"#u" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "2&^(Two_One[31] - 1) mod Two_One[31];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "2& ^((Two_One[31] - 1)/2) mod Two_One[31];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"eo+^2#z$\\Y*Gdo(\\+BZOz@Bx!eX=*[%\\mc6PI/2:nT$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "2&^((Two_One[31] - 1)/3) mod Two_On e[31];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"eo\"QH5+#Rwdq[OH$\\G`i()fv kR7&Hl_pM>XoC*f2b_\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "seq (2&^((Two_One[31] - 1)/ithprime(m)) mod Two_One[31], m = 1..5);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6'\"eo+^2#z$\\Y*Gdo(\\+BZOz@Bx!eX=*[%\\m c6PI/2:nT$\"eo\"QH5+#Rwdq[OH$\\G`i()fvkR7&Hl_pM>XoC*f2b_\"\"eo[%)['H&> &GW#yd2`z\")4<,U$Goc[a0b!*eeCRiofq*>\"eoRe#>X.\\^`6%4^:&=GH!3x'Qt')HI2 +g$3>tL4n1p8\"eo4/L4\"))\\pVAch&[&f&3$*y]I'HoFIggz9g951C/b<#" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Mu ch better is to look out for possible 1's:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "for k to 31 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "if 2&^((Two_One[31] - 1)/ithprime(k)) mod Two_One[31] = 1" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "then print(k)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "fi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 42 "So there's ONLY o ne hickup, namely k = 11:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 52 "2&^((Two_One[31] - 1)/ithprime(11)) mod Two_ One[31];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "3&^((Two_One[31] - 1)/ithprime(11)) mod Two _One[31];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"eocIqIl=/Q^$>x.z_5\"4.( H(=L+3_*o-DM&3!e)*fb*=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 90 "And by Selfridge's improvement of the L_K _L theorem we now know that Two_One[31] is prime." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 "Let's alter Two_One to al low testing to start where we wish:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "new_Two_One := proc(start, n)" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "local k;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "for k from start to n do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "if isprime( product(ithprime(r)^(1 + irem(r, 2)), r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "then print(k, produc t(ithprime(r)^(1 + irem(r, 2)), r = 1..k) + 1)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "fi od end:" }}{PARA 2 "" 1 "" {TEXT -1 1 "\n" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "new_Two_One(51, 70);" }} {PARA 2 "" 1 "" {TEXT -1 1 "\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "new_Two_One(1, 20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"\" \"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"#\"#8" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$\"#6\"3,.B&42$4uE" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$ \"#:\"=, " 0 "" {MPLTEXT 1 0 20 "new_Two_One(71, 75);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6$\"#r\"cx,@T#) )zJKt5TXks(Hp<')>G!*pJNK@#37$)=R@JHH,#y*[(QA&3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "Two_One[71]:=product(ithprime(r)^(1 + irem(r, 2)), r=1..71) + 1;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>&%(Two_OneG6# \"#r\"cx,@T#))zJKt5TXks(Hp<')>G!*pJNK@#37$)=R@JHH,#y*[(QA&3;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "length(Two_One[71]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"$;#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "2&^(Two_One[71] - 1) mod Two_One[71];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "for k to 71 do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "if 2&^((Two_One[71] - 1)/ithprime(k )) mod Two_One[71] = 1" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "then prin t(k)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "fi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "So once again there's only one hickup, namely k = 2:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "2&^((Two_One[71] - \+ 1)/ithprime(2)) mod Two_One[71];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "3&^((Two_One[71] - \+ 1)/ithprime(2)) mod Two_One[71];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#\" bx8-F??!Q-7$H$)>kLP4*3&=^JE([hcOsTA+p!3v%fzc#=+.]Z=d9\"3`qirwY))ec(plc T,u3q:$o.$Q%H_Yb&yf*>u&>x+T\"**y!3HDk='>cyUzgaL]\\![tjg(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "And by Se lfridge's improvement of the L_K_L theorem we now know that Two_One[71 ] is prime." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "ifactor(Two_One[71] - 1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*js-%!G6#\"\"#F'-F%6#\"\"$\"\"\"-F%6#\"\"&F'-F%6#\"\"(F +-F%6#\"#6F'-F%6#\"#8F+-F%6#\"#F+-F%6#\"#BF'-F%6#\"#HF+-F% 6#\"#JF'-F%6#\"#PF+-F%6#\"#TF'-F%6#\"#VF+-F%6#\"#ZF'-F%6#\"#`F+-F%6#\" #fF'-F%6#\"#hF+-F%6#\"#nF'-F%6#\"#rF+-F%6#\"#tF'-F%6#\"#zF+-F%6#\"#$)F '-F%6#\"#*)F+-F%6#\"#(*F'-F%6#\"$,\"F+-F%6#\"$.\"F'-F%6#\"$2\"F+-F%6# \"$4\"F'-F%6#\"$8\"F+-F%6#\"$F\"F'-F%6#\"$J\"F+-F%6#\"$P\"F'-F%6#\"$R \"F+-F%6#\"$\\\"F'-F%6#\"$^\"F+-F%6#\"$d\"F'-F%6#\"$j\"F+-F%6#\"$n\"F' -F%6#\"$t\"F+-F%6#\"$z\"F'-F%6#\"$\"=F+-F%6#\"$\">F'-F%6#\"$$>F+-F%6# \"$(>F'-F%6#\"$*>F+-F%6#\"$6#F'-F%6#\"$B#F+-F%6#\"$F#F'-F%6#\"$H#F+-F% 6#\"$L#F'-F%6#\"$R#F+-F%6#\"$T#F'-F%6#\"$^#F+-F%6#\"$d#F'-F%6#\"$j#F+- F%6#\"$p#F'-F%6#\"$r#F+-F%6#\"$x#F'-F%6#\"$\"GF+-F%6#\"$$GF'-F%6#\"$$H F+-F%6#\"$2$F'-F%6#\"$6$F+-F%6#\"$8$F'-F%6#\"$<$F+-F%6#\"$J$F'-F%6#\"$ P$F+-F%6#\"$Z$F'-F%6#\"$\\$F+-F%6#\"$`$F'" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}{MARK "1 0 0" 101 }{VIEWOPTS 1 1 0 1 1 1803 }