51

18 Steps (-a)*(-a) = ((-a)*(-a))+0 Axiom 2 = ((-a)*(-a))+(((a*a)+(a*(-a)))+(-((a*a)+(a*(-a))))) Axiom 3 = (((-a)*(-a))+((a*a)+(a*(-a))))+(-((a*a)+(a*(-a)))) Axiom 1 = (((a*a)+(a*(-a)))+((-a)*(-a)))+(-((a*a)+(a*(-a)))) Axiom 4 = ((a*a)+((a*(-a))+((-a)*(-a)...


31

18 steps Different from the already posted 18-step solution. a*a = a*a + 0 A2 = a*a + ((a*(-a) + a*(-a)) + (-(a*(-a) + a*(-a)))) A3 = (a*a + (a*(-a) + a*(-a))) + (-(a*(-a) + a*(-a))) A1 = (a*a + a*((-a) + (-a))) + (-(a*(-a) + a*(-a))) A8 = a*(a + ((-a) + (-a))) + (-(a*(-...


28

29 26 Steps No lemmas! Comment if you see anything wrong. (It's very easy to make a mistake) (-a) × (-a) = ((-a) + 0) × (-a) Ax. 2 = ((-a) + (a + (-a))) × (-a) Ax. 3 = ((a + (-a)) + (-a)) × (-a) Ax. 4 ...


19

Google Sheets, 52 51 47 bytes =ArrayFormula(Join(",",Unique(Mod(Row(A:A)^2,A1 Saved 4 bytes thanks to Taylor Scott Sheets will automatically add 4 closing parentheses to the end of the formula. It doesn't return the results in ascending order but it does return the correct results.


18

GolfScript (222 bytes) ~.@:q@.0\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/ Online demo Notes The input format is n followed by a GolfScript array of coefficients from most to ...


17

18 steps Not the first 18-step proof, but it’s simpler than the others. (-a)*(-a) = (-a)*(-a) + 0 [Axiom 2] = (-a)*(-a) + ((-a)*a + -((-a)*a)) [Axiom 3] = ((-a)*(-a) + (-a)*a) + -((-a)*a) [Axiom 1] = ((-a)*(-a) + ((-a) + 0)*a) + -((-a)*a) [Axiom 2] = ((-a)*(-a) + ((-a)*a + 0*a)) + -((-a)*a) [Axiom 9] = (((-...


16

CJam, 189 187 bytes This one's gonna be tough to explain... Time complexity is guaranteed to be O(scary). qi:N_3>{,aN*]N({{:L;N,X)-e!{X)_@+L@@t}%{X2+<z{_fe=:(:+}%:+!},}%:+}fX{:G;N3m*{_~{G@==}:F~F\1m>~F\F=}%:*},:L,({LX=LX)>1$f{\_@a\a+Ne!\f{\:M;~{M\f=z}2*\Mff==}:|{;}|}\a+}fX]:~$e`{0=1=},,}{!!}? If you're brave enough, try it online. On my crappy ...


16

Pyth, 66 63 bytes l.uum.rW}Hdd@_sm_B.iFP.>c3Zk3xZHG_r_Xz\'\39Nf!s}RTcZ2y=Z"UDLRFB Try it online: Demonstration or Test Suite. Notice that the program is kinda slow and the online compiler is not able to compute the answer for RU2D'BD'. But be assured, that it can compute it on my laptop in about 12 seconds. The program (accidentally) also accepts 2 ...


16

Pyth, 24 bytes L-b*/bJ+3^T11Jy*uy^GT11Q Test suite This uses the fact that a^(p-2) mod p = a^-1 mod p. First, I manually reimplement modulus, for the specific case of mod 100000000003. I use the formula a mod b = a - (a/b)*b, where / is floored division. I generate the modulus with 10^11 + 3, using the code +3^T11, then save it in J, then use this and ...


16

Piet, 612 codels Takes n from standard input. Outputs y then x, space-separated. Codel size 1: Codel size 4, for easier viewing: Explanation Check out this NPiet trace, which shows the program calculating the solution for an input value of 99. I'm not sure whether I'd ever heard of Pell's equation before this challenge, so I got all of the following from ...


13

GAP, 792 783 782 749 650 Bytes This seems to be working. If it messes up with something let me know. Thanks to @Lynn for suggesting that I decompose some of the primitive moves. Thanks to @Neil for suggesting that instead of Inverse(X) I use X^3. Usage example: f("R"); R:=(3,39,21,48)(6,42,24,51)(9,45,27,54)(10,12,18,16)(13,11,15,17);L:=(1,46,19,37)...


12

Python 2, 11 + 45 = 56 bytes Addition (11 bytes): int.__xor__ Multiplication (45 bytes): m=lambda x,y:y and m(x*2^x/128*283,y/2)^y%2*x Takes input numbers in the range [0 ... 255]. Addition is just bitwise XOR, multiplication is multiplication of polynomials with coefficients in GF2 with Russian peasant. And for checking: a=int.__xor__ m=lambda x,y:y ...


11

Retina, 21 bytes +`(.)(?!\1)(?i)\1 ^$ Try it online! Like flawr's solution, this just repeatedly deletes adjacent uppercase/lowercase pairs and then checks whether the result is empty or not. As for how one matches an uppercase/lowercase pair: (.) # Match and capture a letter. (?!\1) # Ensure that the next character is not the same, to avoid ...


11

Python 2, 166 bytes def Q(x,n,a=0): e=n/2 while pow(a*a-x,e,n)<2:a+=1 w=a*a-x;b=r=a;c=s=1 while e: if e%2:r,s=(r*b+s*c*w)%n,r*c+s*b b,c=(b*b+c*c*w)%n,2*b*c;e/=2 return min(r,-r%n)


11

Haskell, 190 bytes i!j|j<0=reverse$map(0-)$i!(-j)|i==j=[i,i+1,-i]|i+1==j=[i]|i+j==0=[j+1]|i+j==1=[-j,-i,j] _!j=[j] j%(k:a)|j+k==0=a j%a=j:a i&a=foldr(%)[]$foldr((=<<).(!))[i]a a?n=map(&a)[1..n] (a#b)n=a?n==b?n Try it online! How it works Let Fn be the free group on n generators x1, …, xn. One of the first results in braid theory (Emil ...


11

Mathematica, 14 bytes Obligatory Mathematica builtin: ModularInverse It's a function that takes two arguments (a and b), and returns the inverse of a mod b if it exists. If not, it returns the error ModularInverse: a is not invertible modulo b..


10

APL (10) (Assuming ⎕IO=0. It works on ngn/apl by default, other APLs tend to need an ⎕IO←0 first.) {⍵|∘.+⍨⍳⍵} Explanation: ⍳⍵: the numbers [0..⍵) ∘.+⍨: create a sum table ⍵|: numbers in the table mod ⍵


10

Mathematica, 413 401 bytes Evaluate[f/@Characters@"RFLBUD"]=LetterNumber@"ABFEJNRMDAEHIMQPCDHGLPTOBCGFKOSNADCBILKJEFGHQRST"~ArrayReshape~{6,2,4}; r[c_,l_]:=(b=Permute[c,Cycles@f@l];MapThread[(b[[#,2]]=Mod[b[[#,2]]+{"F","B","L","R"}~Count~l{-1,1,-1,1},#2])&,{f@l,{3,2}}];b); p@s_:=Length[c={#,0}&~Array~20;NestWhileList[Fold[r,#,Join@@StringCases[s,x_~~...


10

Haskell, 283 275 bytes The function g should be called with the matrix and the two ranges as arguments. The matrix is just a list of lists, the ranges each a two element list. import Data.List t=transpose u=tail z=zipWith l%x=sum$z(*)l$iterate(*x)1 --generate powers and multiply with coefficients e m y x=[l%x|l<-m]%y ...


10

23 steps (-a) * (-a) = ((-a) * (-a)) + 0 ✔ axiom 2 = ((-a) * (-a)) + (((-a) * a) + -((-a) * a)) ✔ axiom 3 = (((-a) * (-a)) + (-a) * a) + -((-a) * a) ✔ axiom 1 = (-a) * (-a + a) + -((-a) * a) ✔ axiom 8 = (-a) * (a + (-a)) + -((-a) * a) ...


10

Ruby, 18 bytes ->a,b{a+b*~0**a&7} Ungolfed ->a,b{ (a+b*(-1)**a) % 8} # for operator precedence reasons, #-1 is represented as ~0 in the golfed version Try it online! Uses the following coding numbers 0 to 7 In order native to the code: Native Effect Codes per Code Question 0 ...


9

Python 2, 108 89 87 86 bytes x=y=0 for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m print"--i"[~x%4::2]+`y` (Thanks to @grc and @xnor for the help) Explanation Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. 13 is -i2, so we put 2): 0123 0 0123 1 1032 2 2301 3 ...


9

Jelly, 30 23 22 20 bytes ÆF>1’PḄ ÆDµU5*×Ç€S:Ṫ Try it online! or verify all test cases at once. Algorithm This uses the formula from the OEIS page, where d | n indicates that we sum over all divisors d of n, and μ represents the Möbius function. Code ÆF>1’PḄ Monadic helper link. Argument: d This link computes the Möbius ...


9

Haskell, 118 113 105 101 bytes Inspired from this solution. -12 from Ørjan Johansen p=10^11+3 k b=((p-2)?b)b 1 r x=x-div x p*p (e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e] Try it online! Haskell, 48 bytes A rewrite of this solution. While fast enough for the test vector, this solution is too slow for other inputs. s x=until(\t->t-t`...


9

A2: (-a) x (-a) = ((-a) + 0) x (-a) A3: = ((-a) + (a + (-a))) x (-a) A9: = ((-a) x (-a)) + ((a + (-a)) x (-a)) A4: = ((-a) x (-a)) + (((-a) + a) x (-a)) A9: = ((-a) x (-a)) + (((-a) x (-a)) + (a x (-a))) A1: = (((-a) x (-a)) + ((-a) x (-a))) + (a x (-a)) A2: = (((-a) x (-a)) + ((-a) x (-...


9

Piet, 184 codels This is the brute-force alternative I said (in my other answer) that I didn't want to write. It takes over 2 minutes to compute the solution for n = 13. I really don't want to try it on n = 29... but it checks out for every n up to 20, so I'm confident that it's correct. Like that other answer, this takes n from standard input and outputs y ...


8

CJam, 43 40 37 34 bytes Thanks to Dennis for helping me save 6 bytes. lW%3/$1f=q{i8%"ÉĔɠƂ!"=i\m!=}/c Test it here. Explanation lW% e# Read the first line and reverse it. S/ e# Split it around spaces. $ e# Sort it. This puts the faces in order [B E N S T W]. 1f= e# Select the second character from each face, which is the number. q e# ...


8

Mathematica, 43 bytes Last@SymmetricReduction[#,Variables@#]===0& Unnamed function taking as input a polynomial in the given format (except that juxtaposed variables must be separated by a space) and returning True or False. Variables@# detects the variables appearing in the input (and thus the input can contain all kinds of weird variable names, not ...


8

Mathematica, 62 48 bytes Count[Subsets@First@#,x_/;Union@@#[[x,x]]==x]-1& Pure function expecting a 1-indexed 2D array. Counts the number of Subsets of the First row of the input array that are closed under the group operation. Since this will include the empty set, we subtract 1. Note that a nonempty subset of a finite group that is closed under the ...


8

Retina, 15 bytes (^.+?|\1)+$ $#1 Try it online! Matches the entire string by repeating a substring (shorter substrings are prioritised due to the ungreedy .+?) and replaces the entire string with the number of repetitions we used.


Only top voted, non community-wiki answers of a minimum length are eligible