Skip to content

Instantly share code, notes, and snippets.

@ubuntor

ubuntor/prime.thue

Last active May 22, 2016 16:30
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ubuntor/c10dad4e04a49bb5acd9125775ddb92f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ubuntor/c10dad4e04a49bb5acd9125775ddb92f to your computer and use it in GitHub Desktop.
Download ZIP
Thue Nth Prime
Raw
prime.thue
# 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