## Многочлены Чебышёва (Chebyshev Polynomials)

26

0

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]

If I output a list, can I output 0 1 (i.e. 0*x+1) for T_0? – Luis Mendo – 2017-08-10T20:07:24.217

As long the order of the monomials is consistent that is ok! – flawr – 2017-08-10T20:08:51.690

@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? – Uriel – 2017-08-10T20:36:30.323

Ah I unfortunately did not specify that further, so I guess that is ok, as it represents a polynomial. – flawr – 2017-08-10T20:37:54.247

11Meta discussion on the topic of English titles – Mego – 2017-08-10T21:03:54.250

3Are floating-point inaccuracies acceptable? i.e. T_5(n) = [0, 5, 3.55271e-15, -20, 0, 16] – miles – 2017-08-10T21:24:42.553

@miles Yes that should be ok! – flawr – 2017-08-11T10:21:27.847

Is outputting a list of coefficients, but skipping the ones that are zero because the polynomial is odd/even okay? – proud haskeller – 2017-08-11T20:13:09.317

No I think that this should not be allowed, as that way you cannot determine the actual polynomial by the output alone without any additional information. – flawr – 2017-08-11T20:33:18.997

Maybe it’s good to add example outputs in “ascending coefficient list” format and “descending coefficient list” format for at least one of the polynomials – Lynn – 2017-08-11T23:41:55.260

@Lynn thanks, added! – flawr – 2017-08-12T08:12:54.530

15

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

3Couldn't have guessed, huh. :P – HyperNeutrino – 2017-08-10T20:44:49.940

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.

1Clever as always :) – flawr – 2017-08-11T10:21:45.813

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!

Does polchebyshev take only one input and return the polynomial? – JungHwan Min – 2017-08-12T19:35:20.400

@JungHwanMin Yes. x is the default indeterminate. – alephalpha – 2017-08-13T04:25:08.850

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.

This is very elegant! (I keep forgetting about zipWith for vector operations.) – flawr – 2017-08-11T10:30:10.143

1I 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 :) – flawr – 2017-08-11T10:42:22.127

I think you have to change 0: to 0:0: - OP just disallowed this kind of skipping the zeroes. – Ørjan Johansen – 2017-08-11T20:46:48.377

7

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

6

# 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!

[1,x][n] -> x**n – alephalpha – 2017-08-11T08:41:57.870

5

## SageMath, 25 bytes

lambda n:chebyshev_T(n,x)


Try it online

5

# MATL, 17 bytes

lFTi:"0yhEbFFh-]x


Coefficients are output in increasing order of degree.

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


4

# 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


14 bytes – Leaky Nun – 2017-08-13T23:05:07.443

2

# 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]}


2

# 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!

2

# 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!

2

# 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


1

# 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


1

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