53

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)...


32

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 ...


20

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

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 ...


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] = (((-...


17

Proof of impossibility The only anti-distributive operator when \$S=\mathbb Z\$ is such that \$\forall a, \forall b, a*b=0\$. Indeed, suppose that \$*\$ is anti-distributive. Then \$*\$ has the following property, for all \$ a,b,c\in\mathbb Z\$: (D) \$a*(b+c) = - (a*b+a*c)\$ (In my notation, \$*\$ has precedence over \$+\$.) Take \$a,b \in \mathbb Z\$. By (...


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 ...


14

J, 23 bytes ~:/I.@,~4|[:-/1#;._1@,] Try it online! Takes a boolean vector where 0 represents r and 1 represents s, and returns the result in the same encoding. How it works Imagine evaluating the chunks of \$r^n s r^m s\$ from the start. If we evaluate \$sr\$ in the middle \$m\$ times, we get \$r^{n+3m}s^2 = r^{n+3m}\$. We can repeat the process to the end. ...


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

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

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

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

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 $$\text{A001692}(n) = \frac 1 n \sum_{d|n} \mu(d)5^\frac n d$$ from the OEIS page, where \$d | n\$ indicates that we sum over all divisors \$d\$ of \$n\$, and \$\mu\$ represents the Möbius function. Code ÆF>1’PḄ Monadic ...


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

Jelly, 5 bytes R²%³Q Try it online! Explanation R²%³Q Main link, argument: n R Range from 1 to n ² Square each %³ Mod each by n Q Deduplicate


9

Husk, 11 10 9 bytes VS≡`ȯU¡!1 1-based. Returns the index of a generator if one exists, 0 otherwise. Try it online! Explanation V Does any row r of the input satisfy this: ¡! If you iterate indexing into r ` 1 starting with 1 ȯU until a repetition is encountered, S≡ the result has the same length as r.


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 ...


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