Primes from powers of 2 strings.

[ATH]

3395 digit prime using 2^0 to 2^148. I didn't check with Primo, but it is a strong Baillie-PSW PRP (no known composite PRP found yet):

16225927682921336339157801028812873786976294838206464103845937170696552570609926584401921329227995784915872903807060280344576209715248357032784585166988247041099511627776120892581961462917470617692233720368547758086553626584559915698317458076141205606891522028240960365167042394725128601639614081257132168796771975168720575940379279361088903574147003083082798743781658276659214073748835532864903710731685345356631204115251216777216165242886189700196426901374495621121717986918411805916207174113034242787593149816327892691964784081045188247552557518629963265578538392956816209037649510494447329657392904273924355614296588012332331194975126633106636877371252455336267181195264147573952589676412928858993459243980465111045368709122230074519853062314153571827264836150598041681129638414606681695789005144064519229685853482762853049632922009613743895347238685626227668133590597632446014903970612462830714365452967230119608329671406556917033397649408633825300114114700748351602688212676506002282294014967032053761125899906842624900719925474099269689828745408197317299119602026129706188843568119231764899702645714923623737840956866561888946593147858085478419342813113834066795298816281474976710656368934881474191032324294967296158456325028528675187087900672792281625142643375935439503363402823669209384634633746074317682114563276841538374868278621028243970633760768151115727451828646838272590295810358705651712883886081310722882303761517117441014120480182583521197362564300810737418245629499534213121701411834604692317316873037158841057281342177284253529586511730793292182592897102643234844914372704098658649559801013064853094467108864104857640963602879701896396881925070602400912917605986812821504154742504910672534362390528316912650057057350374175801344664613997892457936451903530140172288332306998946228968225951765070086144139379657490816394634598239204052259412377675557863725914323419136680564733841876926926749214863536422912262144268435456111503725992653115707678591363241807529902082535301200456458802993406410752166153499473114484112975882535043072892029807941224925661428730905934460239216645123518437208883257646075230342348829514790517935282585632544451787073501541541399371890829138329624758800785707605497982484489903520314283042199192993792230584300921369395217592186044416198070406285660843983859875842048212676479325586539664609129644855132162076918743413931051412198531688038422517998136852481784059615882449851322857461811868920478433281298074214633706907132624082305024272225893536750770770699685945414569164883076749736557242056487941267521536184467440737095516162567036874417766445035996273704963355443241943048711228593176024664662389950253266213273660446290980731458735308810633823966279326983230456482242756608128236118324143482260684854975581388821474836484722366482869645213696136112946768375385385349842972707284582417422457186352049329324779900506532426547246116860184273879041237940039285380274899124224495176015714152109959649689610241152921504606846976144115188075855872324518553658426726783156020576256241785163922925834941235225961484292674138142652481646100488507059173023461586584365185794205286418014398509481984642748779069445316911983139663491615228241121378304879609302220830948500982134506872478105621990232555523435973836821778071482940061661655974875633165533184377789318629571617095681638468719476736302231454903657293676544405648192073033408478945025720321

162259276829213363391578010288128_73786976294838206464_10384593717069655257060992658440192_1329227995784915872903807060280344576_2097152_4835703278458516698824704_1099511627776_1208925819614629174706176_9223372036854775808_65536_2658455991569831745807614120560689152_20282409603651670423947251286016_39614081257132168796771975168_72057594037927936_10889035741470030830827987437816582766592_140737488355328_649037107316853453566312041152512_16777216_16_524288_618970019642690137449562112_17179869184_1180591620717411303424_2787593149816327892691964784081045188247552_5575186299632655785383929568162090376495104_9444732965739290427392_43556142965880123323311949751266331066368_77371252455336267181195264_147573952589676412928_8589934592_4398046511104_536870912_22300745198530623141535718272648361505980416_81129638414606681695789005144064_5192296858534827628530496329220096_137438953472_38685626227668133590597632_44601490397061246283071436545296723011960832_9671406556917033397649408_633825300114114700748351602688_2_1267650600228229401496703205376_1125899906842624_9007199254740992_696898287454081973172991196020261297061888_4_356811923176489970264571492362373784095686656_18889465931478580854784_19342813113834066795298816_281474976710656_36893488147419103232_4294967296_158456325028528675187087900672_79228162514264337593543950336_340282366920938463463374607431768211456_32768_41538374868278621028243970633760768_151115727451828646838272_590295810358705651712_8_8388608_131072_288230376151711744_10141204801825835211973625643008_1073741824_562949953421312_170141183460469231731687303715884105728_134217728_42535295865117307932921825928971026432_348449143727040986586495598010130648530944_67108864_1048576_4096_36028797018963968_8192_5070602400912917605986812821504_154742504910672534362390528_316912650057057350374175801344_664613997892457936451903530140172288_332306998946228968225951765070086144_1393796574908163946345982392040522594123776_75557863725914323419136_680564733841876926926749214863536422912_262144_268435456_11150372599265311570767859136324180752990208_2535301200456458802993406410752_166153499473114484112975882535043072_89202980794122492566142873090593446023921664_512_35184372088832_576460752303423488_295147905179352825856_32_5444517870735015415413993718908291383296_2475880078570760549798248448_9903520314283042199192993792_2305843009213693952_17592186044416_19807040628566084398385987584_2048_21267647932558653966460912964485513216_20769187434139310514121985316880384_2251799813685248_178405961588244985132285746181186892047843328_1298074214633706907132624082305024_2722258935367507707706996859454145691648_83076749736557242056487941267521536_18446744073709551616_256_70368744177664_4503599627370496_33554432_4194304_87112285931760246646623899502532662132736_604462909807314587353088_10633823966279326983230456482242756608_128_2361183241434822606848_549755813888_2147483648_4722366482869645213696_1361129467683753853853498429727072845824_174224571863520493293247799005065324265472_4611686018427387904_1237940039285380274899124224_4951760157141521099596496896_1024_1152921504606846976_144115188075855872_324518553658426726783156020576256_2417851639229258349412352_2596148429267413814265248164610048_85070591730234615865843651857942052864_18014398509481984_64_274877906944_5316911983139663491615228241121378304_8796093022208_309485009821345068724781056_2199023255552_34359738368_21778071482940061661655974875633165533184_37778931862957161709568_16384_68719476736_302231454903657293676544_40564819207303340847894502572032_1

[Flatlander]

I'm interested in how you guys are are approaching this problem. Are you randomly shuffling the strings and testing for a prime?

This is the sort of problem I would love to play with if I had the programming skills. Maybe I could learn from your programming and/or techniques.

[Flatlander]

As n grows 'suitably large' does the string of strings contain the amount of each of the digits, 0 to 9, as would be 'expected' for a random number of that size?

[ATH]

These primes are either not so rare or I'm lucky, just found 2 more for n=38 at 244 digits and n=72 at 829 digits:

4194304858993459213107253687091232768256163841342177281717986918412881922147483648268435456326710886451210243435973836820971524137438953472262144335544322048655361048576868719476736167772166427487790694424096838860810737418244294967296165242881
4194304_8589934592_131072_536870912_32768_256_16384_134217728_17179869184_128_8192_2147483648_268435456_32_67108864_512_1024_34359738368_2097152_4_137438953472_262144_33554432_2048_65536_1048576_8_68719476736_16777216_64_274877906944_2_4096_8388608_1073741824_4294967296_16_524288_1
9007199254740992838860825634359738368655361342177285497558138881374389534721073741824922337203685477580811258999068426242104857616384180143985094819845629499534213122748779069443602879701896396820971528858993459241943045368709122814749767106562684354564722366482869645213696324429496729670368744177664140737488355328590295810358705651712144115188075855872409617592186044416335544321310726710886417179869184184467440737095516162361183241434822606848109951162777646116860184273879041475739525896764129282147483648204816439804651110452428826214436893488147419103232512230584300921369395268719476736167772162251799813685248128102428823037615171174472057594037927936295147905179352825856327681180591620717411303424351843720888321152921504606846976645764607523034234888796093022208737869762948382064644503599627370496219902325555281921
9007199254740992_8388608_256_34359738368_65536_134217728_549755813888_137438953472_1073741824_9223372036854775808_1125899906842624_2_1048576_16384_18014398509481984_562949953421312_274877906944_36028797018963968_2097152_8_8589934592_4194304_536870912_281474976710656_268435456_4722366482869645213696_32_4_4294967296_70368744177664_140737488355328_590295810358705651712_144115188075855872_4096_17592186044416_33554432_131072_67108864_17179869184_18446744073709551616_2361183241434822606848_1099511627776_4611686018427387904_147573952589676412928_2147483648_2048_16_4398046511104_524288_262144_36893488147419103232_512_2305843009213693952_68719476736_16777216_2251799813685248_128_1024_288230376151711744_72057594037927936_295147905179352825856_32768_1180591620717411303424_35184372088832_1152921504606846976_64_576460752303423488_8796093022208_73786976294838206464_4503599627370496_2199023255552_8192_1

With GMP package and the mpz_set_str and mpz_get_str functions its actually very easy to look for them. I choose an n and then choose the numbers from 1 to n in random order while I add 2^x to the string. Then I add 2^0 = 1 to the end of the string and convert the string to a mpz_t variable, which I send through a BPSW PRP test function I got from: http://www.trnicely.net/misc/bpsw.html

At n=200 the number is 6152 digits using these digits: 0:528,1:641,2:663,3:617,4:646,5:592,6:650,7:591,8:634,9:590
At n=300 the number is 13743 digits using these digits: 0:1304,1:1420,2:1465,3:1374,4:1416,5:1343,6:1441,7:1305,8:1398,9:1277
So it seems lower than average 0's and 9's higher than average number of 1's and 2's and 6's.

[CRGreathouse]

Originally Posted by R.D. Silverman

Using your rules, I expect only finitely many; the numbers grow too fast.

I disagree.

The numbers are something like n²/2 + O(n) bits long and there are (n-1)! ways to order them with the 1 in the rightmost position. The 'chance' that one would be prime is about 2.5 log 2 / n², so the expected number of primes is very large -- superexponential.

[CRGreathouse]

Originally Posted by ATH

3395 digit prime using 2^0 to 2^148. I didn't check with Primo, but it is a strong Baillie-PSW PRP (no known composite PRP found yet)

I did check mine with Primo, but as the numbers get large that's going to become inconvenient.

Originally Posted by Flatlander

I'm interested in how you guys are are approaching this problem. Are you randomly shuffling the strings and testing for a prime?

I'm going through permutations in order (except that I put the 1 at the end) and testing each for BPSW-pseudoprimality.

[CRGreathouse]

Originally Posted by Flatlander

As n grows 'suitably large' does the string of strings contain the amount of each of the digits, 0 to 9, as would be 'expected' for a random number of that size?

It should, yes. The irregularities from the final digits aren't meaningless -- they're similar in magnitude to the fluctuations expected from chance -- but they're small compared to the total number of digits. Basically you'd expect n/10 + O(sqrt(n)) digits of each of 0..9 and using these numbers changes raises the constant in the big O, but sqrt(n) is still swamped by the main term n/10.

[R.D. Silverman]

Originally Posted by CRGreathouse

I disagree.

The numbers are something like n²/2 + O(n) bits long and there are (n-1)! ways to order them with the 1 in the rightmost position. The 'chance' that one would be prime is about 2.5 log 2 / n², so the expected number of primes is very large -- superexponential.

Yes. I was only considering the "canonical" order; catenating powers
of two in order of increasing magnitude without shuffling. e.g. -->

6432168421

was the only one allowed up to n=6.

[CRGreathouse]

Originally Posted by R.D. Silverman

Yes. I was only considering the "canonical" order; catenating powers
of two in order of increasing magnitude without shuffling. e.g. -->

6432168421

was the only one allowed up to n=6.

Ah. If you consider the canonical order only I agree with you -- zeta(2) is finite so there should be only finitely many of those.

[retina]

Originally Posted by axn

Also, for even n, the sum of digits of 2^0 .. 2^n is divisible by 3. So only odd 'n' has a chance of yielding primes.

swapsies, even <---> odd.

[Batalov]

Indeed random shuffle gets results pretty quick.
n=180, len=4995, PRP attached.
n=240, len=8828, PRP attached. / <== edit/