Finding Programs in the Primes

Question

Let's assign the numbers 0 through 94 to the 95 printable ASCII characters:

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Space is 0, ! is 1, and so on until ~ is 94. We'll also assign 95 to tab (\t) and 96 to newline (\n).

Now consider the infinite string whose Nth character is the character above that the Nth prime number, modulo 97, has been assigned to. We'll call this string S.

For example, the first prime number is 2, and 2 mod 97 is 2, and 2 is assigned to ", so the first character of S is ". Similarly, the 30th prime number is 113, and 113 mod 97 is 16, and 16 is assigned to 0, so the 30th character of S is 0.

The first 1000 characters of S are as follows:

"#%'+-137=?EIKOU[]cgiosy $&*,0>BHJTV\bflrt~
#%1=ACGMOY_ekmswy"046:HNXZ^dlrx|!)-5?AKMSW]eiko{"&.28DFX^hntv|%+139?CEQ[]agmo{ ,6ドル>HPV\`hnrz~+5ACMOSU_mqsw$(*.BFNX`djp~!'-5;GKQS]_eoq{}"48:>DJRX^tv
'17=EQU[aciu 026<>DHJNZ\b#)/7ISaegkqy} 0ドル:<@BFLXdlx~!'/3;?MQWY]ceku(.24LPR\hjt|!'-?EIKWamu28ドル<>BDNZ`fxz)+AGOUY[_gmwy"0:@LNRT^jl|~#')3;Meiow&(,4DFJRX^bnp%+-37=KQUW]agsy ,06BJPTn
)15;=CYegw ".<FHLTZ`dfjpx|~#-/9AES]ikquw&48>FLPbjtz
'1=KOU[]y{,0ドル>BJV\hlr%/1A[_amsw"(04<RTXZf!#)/59?AMQ]_ik{},2FV^bdhj
'39CEIOQWacoy{28ドル<BJPVfrtx%+/7AIOUkqs}*.4FHR`dfp~!);?EGKQS_cw,8:>DJLRhjp
%139EUW[aosu&>HNPZ\fhrxz#%/5=[egqy (:@LXZlrv|!35?MSWY]uw"(8@FL^nptz|!'17COacim &>BDHNP\`n+5;GU[eqsw}$*46:HNTX^`jl|'/AEKWY_ek&,:>FPXdvz|
7CIK[agu ,0NTZ`hnrt
%)+1GMOSegkwy "<BHLT^~-/59;?AKY_cku{.24:X\dntz!'37=?EIOQ[]ms&*6D`fz~/7=AGU[akmw"*46@HT^vx|#)-5GQW]_eo{}&,28@FPVX^djt|39OQcgoy6>PTV`fhnr#+7IY_ams} (*0:HLdfvx!#-AEGKScioq},48>\^hjptz
'-1=CKW[iu 6<HNPfn
)/=ACIS[aek(6@BNXZjl~5GM]ouw(,24>FPV\dhnpz|'+179EIWims&*28<DHV\`nz~
=AY_eq}*046:LR^

Stack Exchange turns tabs into spaces, so here's a PasteBin with the tabs intact.

Challenge

Find a substring of S that is a valid program in your language of choice that outputs the first M prime numbers, one per line, in order, for some positive integer M.

For example, 2 is a substring of S (it occurs in multiple places but any will do), and 2 is a valid CJam program whose output is

2

which is the first M = 1 prime numbers, one per line, in order.

Similarly, the string 2N3N5 may be a substring of S somewhere, and 2N3N5 is a valid CJam program that outputs

2
3
5

which is the first M = 3 prime numbers, one per line, in order.

Scoring

The submission with the highest M wins. Tie breaker goes to the submission posted first.

Details

• There should be no additional output besides the single primes on each line, except for an optional trailing newline after the last line. There is no input.

• The substring may be any length as long as it's finite.

• The substring may occur anywhere within S. (And S may contain it in multiple places.)

• The program must be a full-fledged program. You may not assume it is run in a REPL environment.

• The program must run and terminate in a finite amount of time without errors.

• "Newline" may be interpreted as any common newline representation necessary for your system/interpreter/etc. Just treat it as one character.

You must give the index of S where your substring starts, as well as the length of the substring if not the substring itself. You may not only show that the substring must exist.

^{Related: Looking for programs in a huge Boggle board}

• Optimizer: Can you give the code to produce that big string upto any number of characters ? (I suppose you already have one)
• aditsu quit because SE is EVIL: If there are 95 printable ASCII characters then why are you doing modulo 97? Ah nevermind, you also use tab and newline.
• Sp3000: Considering that 0 mod 97 can only occur once, the lack of space really hurts...
• Calvin's Hobbies: @Sp3000 Shoot, that didn't occur to me. :/

Answer 1

Lenguage, M = ∞

All of the programs start at the beginning of the string. The following poorly written Python program calculates how many characters are needed for a given M.

def program_length(n):
 PLUS, MINUS, DOT = '000', '001', '100'
 i = 1
 s = ''
 while n > 0:
 i += 1
 if all(i%f for f in range(2,i)): 
 s += str(i) + '\n'
 n -= 1
 out = '110111'
 ch = 0
 for c in s:
 dif = ord(c) - ch
 if dif > 0: out += PLUS * dif
 else: out += MINUS * -dif
 out += DOT
 ch = ord(c)
 return int(out, 2)

For example, for M = 5, the program is the first 2458595061728800486379873255763299470031450306332287344758771914371767127738856987726323081746207100511846413417615836995266879023298634729597739072625027450872641123623948113460334798483696686473335593598924642330139401455349473945729379748942060643508071340354553446024108199659348217846094898762753583206697609445347611002385321978831186831089882700897165873209445730704069057276108988230177356 characters.

• ymbirtt: If in doubt, there's a BF variant that'll do it for you.
• Calvin's Hobbies: It's funny how Lenguage was inspired by another challenge of mine. It's like I'm bringing about my own downfall.

Answer 2

CJam, M = 2

Short and sweet:

2NZ

This sequence starts at position 54398, using 1-indexing of the string. You can test it online here.

I attempted to search for a few possible variations, but this was the first solution I found.

I am currently trying to find an M = 3 version, but I don't expect to find one within a reasonable period of time. If the sequence is uniformly random (an approximation), then the starting index for a length 5 sequence could be on the order of 10^9.

• aditsu quit because SE is EVIL: Verified: 1e6{mp},97f%' f+"2NZ"# link (takes a while :p)