26
\$\begingroup\$

Chebyshev Polynomials are a family of orthogonal polynomials that pop up in all kinds of places in math, and they have a lot of quite interesting properties. One characterization of them is that they are the unique polynomials that satisfy Tn(cos(x)) = cos(n*x).

Challenge

Given an nonnegative integer n, you should output the n-th Chebyshev Polynomial. Tn(x).

Definition

The n-th Chebyshev Polynomial is given by following three term recursion:

T0(x) = 1
T1(x) = x
Tn+1(x) = 2*x*Tn(x) - Tn-1(x)

Details

If your language has a native polynomial type, you can use that one as an output, otherwise you should output a list of coefficients in ascending- or descending order, or as a string representing a polynomial.

Examples

T0(x) = 1
T1(x) = x 
T2(x) = 2x^2 - 1
T3(x) = 4x^3 - 3 x
T4(x) = 8x^4 - 8x^2 + 1
T5(x) = 16x^5 - 20x^3 + 5x
T10(x) = 512x^10 - 1280x^8 + 1120x^6 - 400x^4 + 50x^2 - 1

In the descending degree list format we'd get T3(x) = [4,0,-3,0] and in the ascending degree format we'd get T3(x) = [0,-3,0,4]

\$\endgroup\$
  • \$\begingroup\$ If I output a list, can I output 0 1 (i.e. 0*x+1) for T_0? \$\endgroup\$ – Luis Mendo Aug 10 '17 at 20:07
  • \$\begingroup\$ As long the order of the monomials is consistent that is ok! \$\endgroup\$ – flawr Aug 10 '17 at 20:08
  • \$\begingroup\$ @flawr is 2*x*(2*x**2 - 1) - x ok as output for 3 for polynom supportive lang, or do we need the representation as desc coeffs? \$\endgroup\$ – Uriel Aug 10 '17 at 20:36
  • 11
    \$\begingroup\$ Meta discussion on the topic of English titles \$\endgroup\$ – Mego Aug 10 '17 at 21:03
  • 2
    \$\begingroup\$ Are floating-point inaccuracies acceptable? i.e. T_5(n) = [0, 5, 3.55271e-15, -20, 0, 16] \$\endgroup\$ – miles Aug 10 '17 at 21:24

15 Answers 15

15
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Couldn't have guessed, huh. :P \$\endgroup\$ – HyperNeutrino Aug 10 '17 at 20:44
14
\$\begingroup\$

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

enter image description here

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Clever as always :) \$\endgroup\$ – flawr Aug 11 '17 at 10:21
11
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Does polchebyshev take only one input and return the polynomial? \$\endgroup\$ – JungHwan Min Aug 12 '17 at 19:35
  • \$\begingroup\$ @JungHwanMin Yes. x is the default indeterminate. \$\endgroup\$ – alephalpha Aug 13 '17 at 4:25
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is very elegant! (I keep forgetting about zipWith for vector operations.) \$\endgroup\$ – flawr Aug 11 '17 at 10:30
  • 1
    \$\begingroup\$ I think you can even save one more byte by using guards: t n|n<2=1:[0|n>0]|x<-(*2)<$>t(n-1)++[0]=zipWith(-)x$0:t(n-2), that way you can remove the middle pair of parenthesis in the last line :) \$\endgroup\$ – flawr Aug 11 '17 at 10:42
  • \$\begingroup\$ I think you have to change 0: to 0:0: - OP just disallowed this kind of skipping the zeroes. \$\endgroup\$ – Ørjan Johansen Aug 11 '17 at 20:46
7
\$\begingroup\$

CJam (21 bytes)

1a2,qi{0X$+2f*@.-}*;`

This is a full program: the equivalent as an anonymous block is the same length:

{1a2,@{0X$+2f*@.-}*;}

Online demo

\$\endgroup\$
6
\$\begingroup\$

Python + SymPy, 66 bytes

from sympy.abc import*
T=lambda n:n<2and x**n or 2*x*T(n-1)-T(n-2)

Try it online!

With descending coefficients representation

from sympy import*
x=symbols('x')
T=lambda n:n<2and x**n or expand(2*x*T(n-1)-T(n-2))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ [1,x][n] -> x**n \$\endgroup\$ – alephalpha Aug 11 '17 at 8:41
5
\$\begingroup\$

SageMath, 25 bytes

lambda n:chebyshev_T(n,x)

Try it online

\$\endgroup\$
5
\$\begingroup\$

MATL, 17 bytes

lFTi:"0yhEbFFh-]x

Coefficients are output in increasing order of degree.

Try it online! Or verify all test cases.

Explanation

For input n, the code applies the recursive relation n times. The two most recent polynomials are always kept on the stack. When a new polynomial is computed, the oldest is removed.

At the end, the second-last polynomial is displayed (the last polynomial is deleted), as we have done one too many iterations.

l        % Push 1
FT       % Push [0 1]. These are the first two polynomials
i:"      % Input n. Do the following n times
  0      %   Push 0
  y      %   Duplicate most recent polynomial
  h      %   Concatenate: prepends 0 to that polynomial
  E      %   Multiply coefficients by 2
  b      %   Bubble up. This moves second-most recent polynomial to top
  FF     %   Push [0 0]
  h      %   Concatenate: appends [0 0] to that polynomial
  -      %   Subtract coefficients
]        % End
x        % Delete. Implicitly display
\$\endgroup\$
4
\$\begingroup\$

Jelly, 18 bytes

Cr1µ’ßḤ0;_’’$ß$µỊ?

Try it online!

Returns a list of coefficients in ascending order.

There is another solution for 17 bytes with floating-point inaccuracies.

RḤ’÷Ḥ-*ḞÆṛæ«’µ1Ṡ?

Try it online!

Explanation

Cr1µ’ßḤ0;_’’$ß$µỊ?  Input: integer n
                Ị   Insignificant - abs(n) <= 1
                    If true, n = 0 or n = 1
   µ                  Monadic chain
C                       Complement, 1-x
 r1                     Range to 1
                    Else
               µ      Monadic chain
    ’                   Decrement
     ß                  Call itself recursively
      Ḥ                 Double
       0;               Prepend 0
         _              Subtract with
            $             Monadic chain
          ’’                Decrement twice
              $           Monadic chain
             ß              Call itself recursively
\$\endgroup\$
2
\$\begingroup\$

Ruby + polynomial, 59 58+13 = 72 71 bytes

Uses the -rpolynomial flag.

f=->n{x=Polynomial.new 0,1;n<2?[1,x][n]:2*x*f[n-1]-f[n-2]}
\$\endgroup\$
2
\$\begingroup\$

J, 33 bytes

(0>.<:)2&*1:p.@;9:o._1^+:%~1+2*i.

Try it online!

Assumes that floating-point inaccuracies are acceptable and creates the emoji (0>.<:)

For 41 bytes, there is another solution that avoids floats.

(0&,1:)`(-&2((-,&0 0)~2*0&,)&$:<:)@.(>&1)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 79 bytes

f=lambda n:n>1and[2*a-b for a,b in zip([0]+f(n-1),f(n-2)+[0,0])]or range(1-n,2)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Axiom, 40 bytes

f(n,x)==(n<2=>x^n;2*x*f(n-1,x)-f(n-2,x))

results

(9) -> for i in [0,1,2,3,4,5,10] repeat output ["f(y)",i,"=", f(i,y)]
   ["f(y)",0,"=",1]
   ["f(y)",1,"=",y]
                   2
   ["f(y)",2,"=",2y  - 1]
                   3
   ["f(y)",3,"=",4y  - 3y]
                   4     2
   ["f(y)",4,"=",8y  - 8y  + 1]
                    5      3
   ["f(y)",5,"=",16y  - 20y  + 5y]
                      10        8        6       4      2
   ["f(y)",10,"=",512y   - 1280y  + 1120y  - 400y  + 50y  - 1]
                                                               Type: Void

it is possible define one substitution law for formula in Axiom use above f() function for expansion of cos(n*x) where n is one integer

(9) -> o:=rule cos(n*%y)==f(n,cos(%y))
   (9)  cos(%y n) == 'f(n,cos(%y))
                    Type: RewriteRule(Integer,Integer,Expression Integer)
                                                              Time: 0 sec
(10) -> b:=o cos(20*x)
   (10)
                 20                18                16                14
     524288cos(x)   - 2621440cos(x)   + 5570560cos(x)   - 6553600cos(x)
   +
                  12                10               8              6
     4659200cos(x)   - 2050048cos(x)   + 549120cos(x)  - 84480cos(x)
   +
               4            2
     6600cos(x)  - 200cos(x)  + 1
                                                 Type: Expression Integer
                       Time: 0.48 (EV) + 0.02 (OT) + 0.10 (GC) = 0.60 sec
\$\endgroup\$
1
\$\begingroup\$

C# (.NET Core), 126 bytes

f=n=>n==0?new[]{1}:n==1?new[]{0,1}:new[]{0}.Concat(f(n-1)).Select((a,i)=>2*a-(i<n-1?f(n-2)[i]:0)).ToArray();

Byte count also includes:

using System.Linq;

Try it online!

The function returns polynomial as an array of coefficients in ascending order (from x^0 to x^n)

Explanation:

f = n =>                          // Create a function taking one parameter (int)
    n == 0 ? new[] { 1 } :        // If it's 0, return collection [1]
    n == 1 ? new[] { 0, 1 } :     // If it's 1, return collection [0,1] (so x + 0)
    new[] { 0 }                   // Else create new collection, starting with 0
        .Concat(f(n - 1))         // Concatenate with f(n-1), effectively multiplying polynomial by x
        .Select((a, i) => 2 * a - (i < n - 1 ? f(n - 2)[i] : 0))
                                  // Multiply everything by 2 and if possible, subtract f(n-2)
        .ToArray();               // Change collection to array so we have a nice short [] operator
                                  // Actually omitting this and using .ElementAt(i) is the same length, but this is my personal preference
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 65 bytes

f=n=>n?n>1?[0,...f(n-1)].map((e,i)=>e+e-(f(n-2)[i]||0)):[0,1]:[1]

Inefficient for large n. Interesting but sadly also inefficient:

n=>[...Array(n+1)].map(g=(m=n,i)=>i<0|i>m?0:m<2?i^m^1:g(m-1,i-1)*2-g(m-2,i))

Very efficient for 68 bytes:

f=(n,a=[1],b=[0,1])=>n?f(n-1,b,[0,...b].map((e,i)=>e+e-(a[i]||0))):a

Returns an array of coefficients in ascending order.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.