Questions tagged [polynomials]
For challenges involving polynomials, mathematical expressions that consist of variables and coefficients.
89
questions
8
votes
3
answers
389
views
Rational Polynomial Interpolation
Explanation
In this task you'll be given a set of N points (x1,y1),…,(xN,yN) with distinct xi values and your task is to interpolate a polynomial through these points. If you know what Lagrange ...
- 16.7k
14
votes
13
answers
2k
views
Characteristic polynomial
The characteristic polynomial of a square matrix \$A\$ is defined as the polynomial \$p_A(x) = \det(Ix-A)\$ where \$I\$ is the identity matrix and \$\det\$ the determinant. Note that this definition ...
- 16.7k
18
votes
13
answers
2k
views
Cyclotomic polynomial
Background (skip to definitions)
Euler proved a beautiful theorem about the complex numbers: \$e^{ix} = \cos(x) + i \sin(x)\$.
This makes de Moivre's theorem easy to prove:
$$
(e^{ix})^n = e^{i(nx)} \\...
- 49.6k
28
votes
16
answers
3k
views
Многочлены Чебышёва (Chebyshev Polynomials)
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 ...
- 43.7k
21
votes
25
answers
1k
views
Calculate the n-th iterate of a polynomial for a specific value; fⁿ(x)
Given a polynomial function f (e.g. as a list p of real coefficients in ascending or descending order), a non-negative integer n, and a real value x, return:
f n(x)
i.e. the value of f (f (f (…f (x)...
- 29.9k
12
votes
6
answers
442
views
Find the coefficients of a rational generating function
If we write a sequence of numbers as the coefficients of a power series, then that power series is called the (ordinary) generating function (or G.f.) of that sequence. That is, if for some function <...
- 39k
7
votes
4
answers
531
views
Add up two algebraic numbers
Definitions
An algebraic number is a number that is a zero of a non-zero polynomial with integer coefficients. For example, the square root of 2 is algebraic, ...
- 49.6k
11
votes
10
answers
977
views
Rotate the Roots
Given a nonzero polynomial with integer coefficients and roots that are on the imaginary and on the real line such that if a is a root then so is ...
- 43.7k
24
votes
7
answers
1k
views
Find the binarray!
We define a binarray as an array satisfying the following properties:
it's non-empty
the first value is a 1
the last value is a ...
- 188k
22
votes
8
answers
1k
views
Find the polynomial
We know that f is a polynomial with non-negative integer coefficients.
Given f(1) and f(1+f(1)) return f. You may output f as a list of coefficients, an ASCII formatted polynomial, or similar.
...
- 39k
8
votes
3
answers
352
views
Detect a Symmetric polynomial [closed]
A symmetric polynomial is a polynomial which is unchanged under permutation of its variables.
In other words, a polynomial f(x,y) is symmetric if and only if ...
- 5,353
24
votes
10
answers
1k
views
Calculate Power Series Coefficients
Given a polynomial \$p(x)\$ with integral coefficients and a constant term of \$p(0) = \pm 1\$, and a non-negative integer \$N\$, return the \$N\$-th coefficient of the power series (sometimes called &...
- 43.7k
30
votes
13
answers
4k
views
Absolute Sums of Sidi Polynomial Coefficients
Background
The Sidi polynomial of degree \$n\$ – or the \$(n + 1)\$th Sidi polynomial – is defined as follows.
$$S_n(x) = \sum^n_{k=0}s_{n;k}x^n \text{ where } s_{n;k} = (-1)^k\binom n k (k+1)^n$$
The ...
- 210k
20
votes
4
answers
529
views
Locally invert a Polynomial
Challenge
Given a polynomial \$p\$ with real coefficients of order \$1\$ and degree \$n\$, find another polynomial \$q\$ of degree at most \$n\$ such that \$(p∘q)(X) = p(q(X)) \equiv X \mod X^{n+1}\$, ...
- 43.7k
3
votes
3
answers
114
views
One out of Infinity: Interpolating polynomials [duplicate]
For this challenge, when given a list of (x,y) points your submission needs to output a polynomial function that goes through all of them.
For example, if your points were ...
- 14.4k
14
votes
5
answers
941
views
Algebraic curve plotter
An algebraic curve is a certain "1D subset" of the "2D-plane" that can be described as set of zeros {(x,y) in R^2 : f(x,y)=0 }of a polynomial <...
- 43.7k
17
votes
14
answers
3k
views
Shamir's Secret Sharing
Given n (the number of players), t (the threshold value), and s (the secret), output the <...
user45941
19
votes
4
answers
377
views
Self Referential Polynomials
For every given degree \$n\$ it is possible to construct (at least one) an integral polynomial \$p \in \mathbb Z[X]\$ such that \$p(k)\$ (\$p\$ evaluated in \$k\$) is the coefficient of the term \$x^k\...
- 43.7k
21
votes
16
answers
2k
views
Discrete Convolution or Polynomial Multiplication
Given two non empty lists of integers, your submission should calculate and return the discrete convolution of the two. Interestingly, if you consider the list elements as coefficients of polynomials, ...
- 43.7k
22
votes
13
answers
2k
views
Polynomialception
Given two polynomials f,g of arbitrary degree over the integers, your program/function should evaluate the first polynomial in the second polynomial. ...
- 43.7k
9
votes
8
answers
515
views
Expand roots into a polynomial
Challenge
Given the roots of a polynomial separated by spaces as input, output the expanded form of the polynomial.
For example, the input
1 2
represents this ...
- 263
13
votes
5
answers
1k
views
Irreducible polynomials over GF(5)
A polynomial with coefficients in some field F is called irreducible over F if it cannot be decomposed into the product of lower degree polynomials with coefficients in F.
Consider polynomials over ...
- 24.6k
23
votes
21
answers
2k
views
Diamond Puzzles!
Explanation:
Last year in math class, on homework we would occasionally get these extremely simple, although equally annoying questions called diamond puzzles. These were basically questions where we ...
- 481
21
votes
2
answers
878
views
Symbolic Integration of Polynomials
Apply an indefinite integral to a given string. The only rules you will be using are defined as such:
∫cx^(n)dx = (c/(n+1))x^(n+1) + C, n ≠ -1
c, C, and n are all constants.
Specifications:
You ...
- 11.2k
12
votes
6
answers
526
views
Is it a factor of a polynomial?
A polynomial is divisible by a factor (x-n) if f(n)=0 for a function f. Your job: to ...
- 463
14
votes
12
answers
1k
views
Construct a companion matrix
You have a number of polynomials who are lonely, so make them some companions (who won’t threaten to stab)!
For a polynomial of degree n, there is an ...
- 1,035
9
votes
11
answers
2k
views
Construct a polynomial with given roots
The challenge is to write the shortest function/program to find a polynomial given the roots. The function or program should take valid input; that is, a list of integers representing the roots of the ...
- 888
8
votes
2
answers
774
views
Laplace transform of a polynomial [duplicate]
Your goal is to write a program that will print out the Laplace transform of a polynomial function with integer coefficients \$f(x)\$. The Laplace transform of \$f(x)\$ is defined as \$\int_0^\infty f(...
- 192
21
votes
12
answers
2k
views
Symbolic Differentiation of Polynomials
Symbolic Differentiation 1: Gone Coefishin'
Task
Write a program that takes in a polynomial in x from stdin (1 < deg(p) < 128) and differentiates it. The input polynomial will be a string of ...
- 733
3
votes
1
answer
2k
views
Minimum of a Polynomial in Python
What is the shortest amount of code that can find the minimum of an inputted polynomial? I realize that you can import packages like Numpy and others, but using only user defined functions, what is ...
- 39
21
votes
2
answers
1k
views
Prime polynomials
Given a polynomial, determine whether it's prime.
A polynomial is ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, where each term is a constant number (the ...
- 10.8k
20
votes
1
answer
953
views
Factor a polynomial over a finite field or the integers
Without using any built-in factoring/polynomial functions, factor a polynomial completely into irreducibles over the integers or a finite field.
Input
Your program/function will receive some prime (or ...
- 21.2k
5
votes
1
answer
600
views
Find number of polynomials with a root which is a root of unity
Write a program which takes an integer argument and outputs the number of degree n monic polynomials with coefficients that are -1,1 or 0 which have a root which is a root of unity. To make it a ...
user9206
12
votes
7
answers
4k
views
Shortest Program to Solve a Quartic Equation
Write the shortest program to solve a quartic equation.
A quartic equation is a polynomial equation of the form:
\$ax^4 + bx^3 + cx^2 + dx + e=0\$
A solution for \$x\$ is a number such that the above ...
- 279
26
votes
1
answer
1k
views
Find real roots of a polynomial
Write a self-contained program which when given a polynomial and a bound will find all real roots of that polynomial to an absolute error not exceeding the bound.
Constraints
I know that Mathematica ...
- 43.1k
6
votes
3
answers
701
views
Pretty-printing polynomials
A polynomial over a variable x is a function of the form
p(x) = anxn + an-1xn-1 + ... + a1x + a0
where a0 ... an are the coefficients. In the simplest
case, the coefficients are integers, e.g.
...
- 4,162
13
votes
3
answers
1k
views
Polynomial Interpolation
Write a program that performs Polynomial Interpolation using true arbitrary precision rational numbers. The input looks like this:
f(1) = 2/3
f(2) = 4/5
f(3) = 6/7
...
You may assume that there's ...
- 10.1k
11
votes
7
answers
4k
views
Implement Shamir's Secret Sharing reconstruction
Shamir's secret sharing scheme is a simple way of protecting a secret by splitting it into several parts needed to reconstruct it.
Your task is to implement Shamir's Secret Sharing reconstruction ...
- 3,138
16
votes
5
answers
2k
views
Polynomial Long Division
Implement polynomial long division, an algorithm that divides two polynomials and gets the quotient and remainder:
(12x^3 - 5x^2 + 3x - 1) / (x^2 - 5) = 12x - 5 R 63x - 26
In your programs, you will ...
- 5,949