Last active
May 22, 2016 16:30
-
-
Save ubuntor/c10dad4e04a49bb5acd9125775ddb92f to your computer and use it in GitHub Desktop.
Thue Nth Prime
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# mark end | |
$1=1$; | |
$2=2$; | |
$3=3$; | |
$4=4$; | |
$5=5$; | |
$6=6$; | |
$7=7$; | |
$8=8$; | |
$9=9$; | |
$0=0$; | |
# optimization (can check just odd numbers after this) | |
# adjust for speed | |
q1$=2; | |
q2$=3; | |
q3$=5; | |
q4$=7; | |
q5$=11; | |
q6$=13; | |
q7$=17; | |
q8$=19; | |
q9$=23; | |
q10$=29; | |
q11$=31; | |
q12$=37; | |
q13$=41; | |
q14$=43; | |
q15$=47; | |
q16$=53; | |
q17$=59; | |
q18$=61; | |
q19$=67; | |
q20$=71; | |
q21$=73; | |
q22$=79; | |
q23$=83; | |
q24$=89; | |
q25$=97; | |
q26$=101; | |
q27$=103; | |
q28$=107; | |
q29$=109; | |
q30$=113; | |
q31$=127; | |
q32$=131; | |
q33$=137; | |
q34$=139; | |
q35$=149; | |
q36$=151; | |
q37$=157; | |
q38$=163; | |
q39$=167; | |
q40$=173; | |
q41$=179; | |
q42$=181; | |
q43$=191; | |
q44$=193; | |
q45$=197; | |
q46$=199; | |
q47$=211; | |
q48$=223; | |
q49$=227; | |
q50$=229; | |
q51$=233; | |
q52$=239; | |
q53$=241; | |
q54$=251; | |
q55$=257; | |
q56$=263; | |
q57$=269; | |
q58$=271; | |
q59$=277; | |
q60$=281; | |
q61$=283; | |
q62$=293; | |
q63$=307; | |
q64$=311; | |
q65$=313; | |
q66$=317; | |
q67$=331; | |
q68$=337; | |
q69$=347; | |
q70$=349; | |
q71$=353; | |
q72$=359; | |
q73$=367; | |
q74$=373; | |
q75$=379; | |
q76$=383; | |
q77$=389; | |
q78$=397; | |
q79$=401; | |
q80$=409; | |
q81$=419; | |
q82$=421; | |
q83$=431; | |
q84$=433; | |
q85$=439; | |
q86$=443; | |
q87$=449; | |
q88$=457; | |
q89$=461; | |
q90$=463; | |
q91$=467; | |
q92$=479; | |
q93$=487; | |
q94$=491; | |
q95$=499; | |
q96$=503; | |
q97$=509; | |
q98$=521; | |
q99$=523; | |
q100$=541; | |
q101$=547; | |
q102$=557; | |
q103$=563; | |
q104$=569; | |
q105$=571; | |
q106$=577; | |
q107$=587; | |
q108$=593; | |
q109$=599; | |
q110$=601; | |
q111$=607; | |
q112$=613; | |
q113$=617; | |
q114$=619; | |
q115$=631; | |
q116$=641; | |
q117$=643; | |
q118$=647; | |
q119$=653; | |
q120$=659; | |
q121$=661; | |
q122$=673; | |
''' | |
q123$=677; | |
q124$=683; | |
q125$=691; | |
q126$=701; | |
q127$=709; | |
q128$=719; | |
q129$=727; | |
q130$=733; | |
q131$=739; | |
q132$=743; | |
q133$=751; | |
q134$=757; | |
q135$=761; | |
q136$=769; | |
q137$=773; | |
q138$=787; | |
q139$=797; | |
q140$=809; | |
''' | |
q=P; | |
# mark end cont. | |
p1=q1$; | |
p2=q2$; | |
p3=q3$; | |
p4=q4$; | |
p5=q5$; | |
p6=q6$; | |
p7=q7$; | |
p8=q8$; | |
p9=q9$; | |
# converts P[N] to (N)P | |
P9=*********,P; | |
P8=********,P; | |
P7=*******,P; | |
P6=******,P; | |
P5=*****,P; | |
P4=****,P; | |
P3=***,P; | |
P2=**,P; | |
P1=*,P; | |
P0=,P; | |
# init, mark start | |
# adjust for speed | |
#P$=^------------------------------------------------------------------------------------------------P[*********,*******,*********,/|\%$; | |
M=------------; | |
P$=^MMMMMMMMMM--P[******,*******,*****,/|\%$; | |
*^=^*; | |
,^=^,; | |
# increment left | |
,**********,=*,,; | |
#P**********,=P*,,; | |
)**********,=)*,,; | |
\**********,=\*,,; | |
# skip multiples of 5 | |
\***,++C%=\*******,C%__; | |
,***,++)/=,*******,)/; | |
,+=*,; | |
# decrement left | |
^*,-=^; | |
/*,-=/; | |
#\*,-=\; | |
*,-=,; | |
,,-=,-*********,; | |
# decrement right | |
_,*$=$; | |
_,*]=]; | |
#_,*\=\; | |
_,*=,; | |
_,,=,*********_,; | |
# converts !(N) into [N] | |
!*********,=9!; | |
!********,=8!; | |
!*******,=7!; | |
!******,=6!; | |
!*****,=5!; | |
!****,=4!; | |
!***,=3!; | |
!**,=2!; | |
!*,=1!; | |
!,=0!; | |
# finalize | |
^P)[=!; | |
!/|\%$=; | |
# messages through *, | |
*********,{<<<<<<<<<={<<<<<<<<<*********,; | |
#*********,{<<<<<<<<={<<<<<<<<*********,; | |
*********,{<<<<<<<={<<<<<<<*********,; | |
#*********,{<<<<<<={<<<<<<*********,; | |
*********,{<<<<<={<<<<<*********,; | |
#*********,{<<<<={<<<<*********,; | |
*********,{<<<={<<<*********,; | |
#*********,{<<={<<*********,; | |
*********,{<={<*********,; | |
#*********,{={*********,; | |
********,{<<<<<<<<<={<<<<<<<<<********,; | |
#********,{<<<<<<<<={<<<<<<<<********,; | |
********,{<<<<<<<={<<<<<<<********,; | |
#********,{<<<<<<={<<<<<<********,; | |
********,{<<<<<={<<<<<********,; | |
#********,{<<<<={<<<<********,; | |
********,{<<<={<<<********,; | |
#********,{<<={<<********,; | |
********,{<={<********,; | |
#********,{={********,; | |
*******,{<<<<<<<<<={<<<<<<<<<*******,; | |
#*******,{<<<<<<<<={<<<<<<<<*******,; | |
*******,{<<<<<<<={<<<<<<<*******,; | |
#*******,{<<<<<<={<<<<<<*******,; | |
*******,{<<<<<={<<<<<*******,; | |
#*******,{<<<<={<<<<*******,; | |
*******,{<<<={<<<*******,; | |
#*******,{<<={<<*******,; | |
*******,{<={<*******,; | |
#*******,{={*******,; | |
******,{<<<<<<<<<={<<<<<<<<<******,; | |
#******,{<<<<<<<<={<<<<<<<<******,; | |
******,{<<<<<<<={<<<<<<<******,; | |
#******,{<<<<<<={<<<<<<******,; | |
******,{<<<<<={<<<<<******,; | |
#******,{<<<<={<<<<******,; | |
******,{<<<={<<<******,; | |
#******,{<<={<<******,; | |
******,{<={<******,; | |
#******,{={******,; | |
*****,{<<<<<<<<<={<<<<<<<<<*****,; | |
#*****,{<<<<<<<<={<<<<<<<<*****,; | |
*****,{<<<<<<<={<<<<<<<*****,; | |
#*****,{<<<<<<={<<<<<<*****,; | |
*****,{<<<<<={<<<<<*****,; | |
#*****,{<<<<={<<<<*****,; | |
*****,{<<<={<<<*****,; | |
#*****,{<<={<<*****,; | |
*****,{<={<*****,; | |
#*****,{={*****,; | |
****,{<<<<<<<<<={<<<<<<<<<****,; | |
#****,{<<<<<<<<={<<<<<<<<****,; | |
****,{<<<<<<<={<<<<<<<****,; | |
#****,{<<<<<<={<<<<<<****,; | |
****,{<<<<<={<<<<<****,; | |
#****,{<<<<={<<<<****,; | |
****,{<<<={<<<****,; | |
#****,{<<={<<****,; | |
****,{<={<****,; | |
#****,{={****,; | |
***,{<<<<<<<<<={<<<<<<<<<***,; | |
#***,{<<<<<<<<={<<<<<<<<***,; | |
***,{<<<<<<<={<<<<<<<***,; | |
#***,{<<<<<<={<<<<<<***,; | |
***,{<<<<<={<<<<<***,; | |
#***,{<<<<={<<<<***,; | |
***,{<<<={<<<***,; | |
#***,{<<={<<***,; | |
***,{<={<***,; | |
#***,{={***,; | |
**,{<<<<<<<<<={<<<<<<<<<**,; | |
#**,{<<<<<<<<={<<<<<<<<**,; | |
**,{<<<<<<<={<<<<<<<**,; | |
#**,{<<<<<<={<<<<<<**,; | |
**,{<<<<<={<<<<<**,; | |
#**,{<<<<={<<<<**,; | |
**,{<<<={<<<**,; | |
#**,{<<={<<**,; | |
**,{<={<**,; | |
#**,{={**,; | |
*,{<<<<<<<<<={<<<<<<<<<*,; | |
#*,{<<<<<<<<={<<<<<<<<*,; | |
*,{<<<<<<<={<<<<<<<*,; | |
#*,{<<<<<<={<<<<<<*,; | |
*,{<<<<<={<<<<<*,; | |
#*,{<<<<={<<<<*,; | |
*,{<<<={<<<*,; | |
#*,{<<={<<*,; | |
*,{<={<*,; | |
#*,{={*,; | |
''' | |
,{<<<<<<<<<={<<<<<<<<<,; | |
,{<<<<<<<<={<<<<<<<<,; | |
,{<<<<<<<={<<<<<<<,; | |
,{<<<<<<={<<<<<<,; | |
,{<<<<<={<<<<<,; | |
,{<<<<={<<<<,; | |
,{<<<={<<<,; | |
,{<<={<<,; | |
,{<={<,; | |
''' | |
''' | |
*{={*; | |
,{={,; | |
*<=<*; | |
,<=<,; | |
''' | |
''' | |
>>}****,=****,>>}; | |
>>}***,=***,>>}; | |
>>}**,=**,>>}; | |
>>}*,=*,>>}; | |
>>},=,>>}; | |
>>}*****=*****>>}; | |
>}****,=****,>}; | |
>}***,=***,>}; | |
>}**,=**,>}; | |
>}*,=*,>}; | |
>},=,>}; | |
>}*****=*****>}; | |
''' | |
}****,=****,}; | |
}***,=***,}; | |
}**,=**,}; | |
}*,=*,}; | |
},=,}; | |
}*****=*****}; | |
''' | |
>>>>>****,=****,>>>>>; | |
>>>>>***,=***,>>>>>; | |
>>>>>**,=**,>>>>>; | |
>>>>>*,=*,>>>>>; | |
>>>>>,=,>>>>>; | |
>>>>>*****=*****>>>>>; | |
>>****,=****,>>; | |
>>***,=***,>>; | |
>>**,=**,>>; | |
>>*,=*,>>; | |
>>,=,>>; | |
>>*****=*****>>; | |
''' | |
>****,=****,>; | |
>***,=***,>; | |
>**,=**,>; | |
>*,=*,>; | |
>,=,>; | |
>*****=*****>; | |
''' | |
>**=**>; | |
>*,=*,>; | |
>,*=,*>; | |
>,,=,,>; | |
''' | |
''' | |
>*=*>; | |
}*=*}; | |
''' | |
# copy x | |
>/(=/(*; | |
}/(=/(,; | |
>>>>>>>>>}/=/*********,; | |
>>>>>>>>}/=/********,; | |
>>>>>>>}/=/*******,; | |
>>>>>>}/=/******,; | |
>>>>>}/=/*****,; | |
>>>>}/=/****,; | |
>>>}/=/***,; | |
>>}/=/**,; | |
>}/=/*,; | |
}/=/,; | |
#>/=/*; | |
[*=*[; | |
[,=,[; | |
[/=++)/(; | |
*********,)=)*********,>>>>>>>>>}; | |
********,)=)********,>>>>>>>>}; | |
*******,)=)*******,>>>>>>>}; | |
******,)=)******,>>>>>>}; | |
*****,)=)*****,>>>>>}; | |
****,)=)****,>>>>}; | |
***,)=)***,>>>}; | |
**,)=)**,>>}; | |
*,)=)*,>}; | |
#*)=)*>; | |
,)=),}; | |
# init k | |
#>(|\%=(|\%; | |
#}(|\%=(|\%,; | |
>|\%=|\%; | |
}|\%=|\%,; | |
# rough sqrt | |
s,,=,*********s; | |
s$=$; | |
,*********s,$=,**,***$; | |
#s,$=,****$; | |
# ensure k is even | |
e,*********=,********; | |
#e,********=,********; | |
#e,*******=,******; | |
#e,******=,******; | |
#e,*****=,****; | |
#e,****=,****; | |
#e,***=,**; | |
e,**=,**; | |
#e,*=,; | |
#e,=,; | |
# destroy left | |
''' | |
*DL=DL; | |
,DL=DL; | |
''' | |
# destroy right | |
DR*=DR; | |
DR,=DR; | |
#DR]\=]\; | |
# destroy left (good) | |
''' | |
**GL=GL; | |
*,GL=GL; | |
,*GL=GL; | |
,,GL=GL; | |
''' | |
*GL=GL; | |
,GL=GL; | |
# destroy right (good) | |
GR,*********=GR; | |
GR,********=GR; | |
GR,*******=GR; | |
GR,******=GR; | |
GR,*****=GR; | |
GR,****=GR; | |
GR,***=GR; | |
GR,**=GR; | |
GR,*=GR; | |
GR,=GR; | |
# init j | |
|\?%=|,***\***,%; | |
# copy j | |
#]*=*]>; | |
#],=,]}; | |
#>\=\*; | |
#}\=\,; | |
(|\%=|]\%es; | |
(*=*(>; | |
(,=,(}; | |
#[\=\; | |
# good outer loop, decrement n | |
C%$=GL%$; | |
|\GL%$=GL|\%$; | |
/GL=:/; | |
*:=:*; | |
,:=:,; | |
P):=-P)[; | |
# clear leading zero | |
/,=/; | |
,\=\; | |
,|,]\=,|\?; | |
,,]\=]\; | |
,]\=]\; | |
# bad inner loop, destroy, increment x | |
/|]\%$=++)/(|\%$; | |
DR%=%DR; | |
DR$=$; | |
/|]\=/|]\DR; | |
# recopy | |
P))=P); | |
\{<<<<<<<<<=,*********\; | |
#\{<<<<<<<<=,********\; | |
\{<<<<<<<=,*******\; | |
#\{<<<<<<=,******\; | |
\{<<<<<=,*****\; | |
#\{<<<<=,****\; | |
\{<<<=,***\; | |
#\{<<=,**\; | |
\{<=,*\; | |
#\{=,\; | |
#\<=*\; | |
\*********,C=,*********]\*********,; | |
\********,C=,********]\********,; | |
\*******,C=,*******]\*******,; | |
\******,C=,******]\******,; | |
\*****,C=,*****]\*****,; | |
\****,C=,****]\****,; | |
\***,C=,***]\***,; | |
\**,C=,**]\**,; | |
\*,C=,*]\*,; | |
*********,C={<<<<<<<<<C*********,; | |
#********,C={<<<<<<<<C********,; | |
*******,C={<<<<<<<C*******,; | |
#******,C={<<<<<<C******,; | |
*****,C={<<<<<C*****,; | |
#****,C={<<<<C****,; | |
***,C={<<<C***,; | |
#**,C={<<C**,; | |
*,C={<C*,; | |
#,C={C,; | |
#\C=]\; | |
# good inner loop, decrement, recopy | |
d**=**d; | |
d*,=*,d; | |
d,*=,*d; | |
#d,,=,,d; | |
#d*=*d; | |
d,=,d; | |
d%=++C%__; | |
/|GR]\=)/|\d; | |
/|=/|GR; | |
# modulo loop | |
''' | |
?*********,%=*********,C%; | |
?********,%=********,C%; | |
?*******,%=*******,C%; | |
?******,%=******,C%; | |
?*****,%=*****,C%; | |
''' | |
?****,%=****,C%; | |
?***,%=***,C%; | |
?**,%=**,C%; | |
?*,%=*,C%; | |
?,%=,C%; | |
?****,=****,?; | |
?***,=***,?; | |
?**,=**,?; | |
?*,=*,?; | |
?,=,?; | |
?*****=*****?; | |
#?*=*?; | |
#?%=C%; | |
|]\=|\?; | |
|\=|\?; | |
***,,|,,***=,,|,,; | |
**,,|,,**=,,|,,; | |
*,,|,,*=,,|,,; | |
#*********,|,*********=,|,; | |
#********,|,********=,|,; | |
*******,|,*******=,|,; | |
******,|,******=,|,; | |
*****,|,*****=,|,; | |
****,|,****=,|,; | |
***,|,***=,|,; | |
**,|,**=,|,; | |
*,|,*=,|,; | |
#*,,,|,,*=,*********,,|,,; | |
#*,,|,,,*=,,|,,*********,; | |
*,,,|,*=,*********,*********,|,; | |
#*,|,,,*=,|,*********,*********,; | |
#*,,|,***]=,*******,|]; | |
#*,,|,**]=,********,|]; | |
''' | |
*,*********,|,,*=,*********,|,,; | |
*,********,|,,*=,********,|,,; | |
*,*******,|,,*=,*******,|,,; | |
*,******,|,,*=,******,|,,; | |
*,*****,|,,*=,*****,|,,; | |
*,****,|,,*=,****,|,,; | |
*,***,|,,*=,***,|,,; | |
*,**,|,,*=,**,|,,; | |
*,*,|,,*=,*,|,,; | |
*,,|,,*=,,|,,; | |
''' | |
*,,|,*]=,*********,|]; | |
#*,,|,*********=,*,|,; | |
#*,,|,********=,**,|,; | |
*,,|,*******=,***,|,; | |
*,,|,******=,****,|,; | |
*,,|,*****=,*****,|,; | |
*,,|,****=,******,|,; | |
*,,|,***=,*******,|,; | |
*,,|,**=,********,|,; | |
*,,|,*=,*********,|,; | |
**,|,,*]=,|,********]; | |
*,|,,*]=,|,*********]; | |
*********,|,,*=,|,*,; | |
********,|,,*=,|,**,; | |
*******,|,,*=,|,***,; | |
******,|,,*=,|,****,; | |
*****,|,,*=,|,*****,; | |
****,|,,*=,|,******,; | |
***,|,,*=,|,*******,; | |
**,|,,*=,|,********,; | |
*,|,,*=,|,*********,; | |
|=-|_; | |
''' | |
structure: | |
(n>P(x>/(xcopy>|<j)\(jcopy>%<k) | |
(variable> means lsb is at the right | |
<variable) means lsb is at the left | |
pseudocode: | |
x = 5 | |
while n > 0: | |
x += 2 | |
# check(x) | |
k = even(sqrt(n)) | |
j = 1 | |
while k > 0: | |
j += 2 | |
k -= 2 | |
if x%j == 0: | |
x += 1 | |
break # clear everything | |
else: | |
# prime | |
n -= 1 | |
''' |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment