49

Python 2, 43 bytes f=lambda n,k=1:k/n or n*f(n,k+1)+k*f(n-1,k) Try it online! A different approach Ever since I posted this challenge, I tried to come up with a recursive solution to this problem. While I failed using nothing more than pen and paper, I managed to turn the formula to golf into a practical problem – at least for certain definitions of ...


27

Jelly, 3 bytes ‘b@ Try it online! Returns the polynomial as a list of coefficients. Since we know the polynomial has non-negative integer coefficients, f(b) can be interpreted as "the coefficients of the polynomial, taken as base b digits," by the definition of a base. This is subject to the condition that none of the coefficients exceeds or is equal to ...


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


16

Mathematica, 15 bytes #~ChebyshevT~x& Of course, Mathematica has a builtin. If an alternative input form is allowed (10 bytes): ChebyshevT takes an integer n and a variable.


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


15

Retina, 53 43 42 41 40 35 bytes ^[^x]+ |(\^1)?\w(?=1*x.(1+)| |$) $2 For counting purposes each line goes in a separate file, but you can run the above as a single file by invoking Retina with the -s flag. This expects the numbers in the input string to be given in unary and will yield output in the same format. E.g. 1 + 11x + -111x^11 + 11x^111 + -1x^...


14

J, 10 8 bytes [:+//.*/ Usage: ppc =: [:+//.*/ NB. polynomial product coefficients 80085 1337 ppc _24319 406 _1947587115 7 542822 Description: The program takes takes two lists, makes a multiplication table, then adds the numbers on the positive diagonals.


14

Octave, 39 bytes @(n)round(2^n/2*poly(cos((.5:n)/n*pi))) Try it online! Explanation cos((.5:n)/n*pi) builds a vector with the roots of the polynomial, given by poly gives the monic polynomial with those roots. Multiplying by 2^n/2 scales the coefficients as required. round makes sure that results are integer in spite of numerical precision.


13

Jelly, 15 bytes 251©xX€⁵0¦ḅЀ%® Expects t, n, and s as command-line arguments. Try it online! How it works 251©xX€⁵0¦ḅЀ%® Main link. Left argument: t. Right argument: n Third argument: s 251© Yield 251 and copy it to the register. x Repeat [251] t times. X€ Random choice each; pseudo-randomly choose t integers ...


12

Mathematica, 10 Bytes Pure function which takes a function of x and substitutes in ix. #/.x->I*x& Alternative with only 7 bytes but not quite sure if it counts. Pure function which takes in a pure function and returns a function of x. #[I*x]&


12

Haskell, 120 bytes import Data.Complex p%a=zipWith(\x y->x-a*y)(p++[0])$0:p f n=foldl(%)[1][cis(2*pi/fromInteger n)^^k|k<-[1..n],gcd n k<2] Try it online! Gives a list of complex floats that has entries like 1.0000000000000078 :+ 3.314015728506092e-14 due to float inacurracy. A direct method of multiplying out to recover the polynomial from its ...


12

JavaScript (ES7), 48 bytes Based upon a suggestion from @RickHitchcock Expects X in uppercase. Takes input in currying syntax (p)(X). p=>X=>eval(p.replace(/[X^]/g,c=>c<{}?'*X':'**')) Try it online! JavaScript (ES7), 49 bytes Same approach as @DeadPossum. Takes input in currying syntax (p)(x). p=>x=>eval(p.split`x`.join`*x`.split`^`....


12

Wolfram Language (Mathematica), 20 bytes Root[xx^5+x+#,1]& Try it online! Still a built-in, but at least it isn't UltraRadical. (the character  is displayed like |-> in Mathematica, similar to => in JS)


12

Python 2, 53 bytes f=lambda n,x:n<1or((2*n-1-x)*f(n-1,x)-~-n*f(n-2,x))/n Try it online!


11

Pari/GP, 12 bytes Yes, a builtin. Shorter than Mathematica. polchebyshev Try it online! Without builtin: Pari/GP, 34 bytes f(n)=if(n<2,x^n,2*x*f(n-1)-f(n-2)) Try it online!


11

SageMath, 3 bytes 5 bytes saved thanks to @Mego fcp Try it online! Takes a Matrix as input. fcp stands for factorization of the characteristic polynomial, which is shorter than the normal builtin charpoly.


11

Wolfram Language (Mathematica), 9 bytes LaguerreL Try it online!


10

J, 8 bytes A series of verbs: |.p.1;~. Call it like this: |.p.1;~. 1 2 1 _3 2 J has a built-in verb p. (Roots). It converts between polynomials like 2 _3 1 (reverse order from the problem) and a multiplier/root pair like (1; 1 2). From right-to-left, ~. takes the unique elements, 1; pairs the list with 1, meaning we want the smallest integer polynomial, ...


10

Haskell, 86 72 bytes u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c o g=(0:)!((<$>g).(*))!pure Defines a function o such that o g f computes the composition f ∘ g. Polynomials are represented by a nonempty list of coefficients starting at the constant term. Demo *Main> o [1,1] [5,3,1] [9,5,1] *Main> o [0,-1,1] [1,0,1,0,0,0,1] [1,0,1,-2,1,0,1,-...


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

Haskell, 62 bytes t n|n<2=1:[0|n>0]|x<-(*2)<$>t(n-1)++[0]=zipWith(-)x$0:0:t(n-2) Try it online! flawr saved a byte.


10

Retina 0.8.2, 56 bytes (?=( \S+)+) x^$#1 \b0x.\d+ \b1x x x.1 x 0 - - + Try it online! Link includes test cases. Explanation: (?=( \S+)+) x^$#1 Insert all of the powers of x, including x^1 but not x^0. \b0x.\d+ Delete all powers of x with zero coefficients, but not a trailing 0 (yet). \b1x x Delete a multiplier of 1 (but not ...


10

Pari/GP, 40 bytes r->[x=27*r^3+1,9*r-x,z=9*r-27*r^2]/(3-z) Try it online! The same length, the same formula: r->d=9*r^2-3*r+1;[x=r+1/3,3*r/d-x,1/d-1] Try it online! This formula is given in: Richmond, H. (1930). On Rational Solutions of \$x^3+y^3+z^3=R\$. Proceedings of the Edinburgh Mathematical Society, 2(2), 92-100. $$r=\left(\frac{27r^3+1}{27r^...


10

Scala 3, 49 44 bytes a=>b=>(-b*b to b*b)map(p=>a-p->p)find(_*_==b) Try it onlne! Takes (a)(b) and returns an Option[(Int, Int)]. It's now a little more inefficient since it goes from \$-b^2\$ to \$b^2\$ instead of \$-|b|\$ to \$|b|\$, including values that \$p\$ and \$q\$ could never be, but it saves 4 bytes. a => b => (-b*b to b*b) ...


9

CJam, 43 41 bytes Qleu'^/';*'+/{~:E[*'x['^E(]]E<}/]1>" + "* Thanks to @jimmy23013 for pointing out one bug and golfing off two bytes! Try it online in the CJam interpreter. How it works Q e# Leave an empty array on the bottom of the stack. l e# Read a line from STDIN. eu'^/';* e# Convert to uppercase and replace carets with ...


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

Mathematica, 17 bytes Expand[#/.x->#2]& Example usage: In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x] 2 4 Out[17]= -96 x + 48 x


9

Mathematica, 33 32 bytes Saved one byte thanks to JungHwan Min. Binomial[#,r=0~Range~#].(r+1)^#&


9

Mathematica, 24 23 bytes Saved 1 byte thanks to Greg Martin D[1/#2,{x,#}]/#!/.x->0& Pure function with two arguments # and #2. Assumes the polynomial #2 satisfies PolynomialQ[#2,x]. Of course there's a built-in for this: SeriesCoefficient[1/#2,{x,0,#}]&


9

Octave, 16 4 bytes @BruteForce just told me that one of the functions I was using in my previous solution can actually do the whole work: poly Try it online! 16 Bytes: This solution computes the eigenvalues of the input matrix, and then proceeds building a polynomial from the given roots. @(x)poly(eig(x)) But of course there is also the boring ...


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