Questions tagged [polynomials]
For challenges involving polynomials, mathematical expressions that consist of variables and coefficients.
89
questions
10
votes
6
answers
360
views
Hermite interpolation
We already have a challenge for polynomial interpolation: given a list of points, output the coefficients of the polynomial that passes through them.
Hermite interpolation is a generalization of ...
- 18.9k
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, ...
- 4,755
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 ...
- 4,755
13
votes
8
answers
641
views
Multiply numerical polynomials
A numerical polynomial is a polynomial \$p\$ in one variable with rational coefficients such that for every integer \$i\$, \$p(i)\$ is also an integer. The numerical polynomials have a basis given by ...
- 46.5k
13
votes
7
answers
1k
views
Ryley's Theorem
S. Ryley proved following theorem in 1825:
Every rational number can be expressed as a sum of three rational cubes.
Challenge
Given some rational number \$r \in \mathbb Q \$ find three rational ...
- 46.5k
4
votes
3
answers
230
views
Order of an algebraic number
Consider some arbitrary polynomial with integer coefficients,
$$a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0 = 0$$
We'll assume that \$a_n \ne 0\$ and \$a_0 \ne 0\$. The solutions to this polynomial ...
- 4,755
12
votes
9
answers
825
views
Chromatic polynomial of a graph
Given a undirected graph \$G\$ and a integer \$k\$, how many \$k\$-coloring does the graph have?
Here by a \$k\$-coloring, we mean assigning one of the \$k\$ colors to each vertex of the graph, such ...
- 4,755
15
votes
16
answers
897
views
Euler-Poincaré-Characteristic of Polyhedra
Given a triangulation of the surface of a polyhedron p, calculate its Euler-Poincaré-Characteristic χ(p) = V-E+F, where ...
- 46.5k
14
votes
13
answers
1k
views
Resultant of two polynomials
The resultant of two polynomials is a polynomial in their coefficients that is zero if and only if \$p\$ and \$q\$ have a common root. It is a useful tool for eliminating variables from systems of ...
- 4,755
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 &...
- 4,755
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 ...
- 4,755
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. ...
- 4,755
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\...
- 4,755
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)} \\...
- 4,755
19
votes
10
answers
2k
views
Is this polynomial a square?
Given an integral polynomial \$p\$, determine if \$p\$ is a square of another integral polynomial.
An integral polynomial is a polynomial with only integers as coefficients.
For example, \$x^2+2x+1\$ ...
- 4,755
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 ...
- 4,755
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 ...
- 4,755
7
votes
2
answers
290
views
Find the Circle-Tangent Polynomials
Introduction
A circle-tangent polynomial is a polynomial of degree \$N\ge3\$ or above that is tangent to the unit circle from inside at all of its N-1 intersection points. The two tails that exits the ...
- 4,755
10
votes
10
answers
455
views
CGAC2022 Day 3: \$n\$-dimensional Chocolate Pyramid
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
I've got an infinite supply of \$n\$-dimensional chocolate for some positive integer \$n\$. The shape of the ...
- 4,755
14
votes
7
answers
984
views
Exponential transform of an integer sequence
The exponential generating function (e.g.f.) of a sequence \$a_n\$ is defined as the formal power series \$f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n\$.
When \$a_0 = 0\$, we can apply the ...
- 4,755
18
votes
16
answers
1k
views
Multiplicity of a root of a polynomial
Let \$p(x)\$ be a polynomial. We say \$a\$ is a root of multiplicity \$k\$ of \$p(x)\$, if there is another polynomial \$s(x)\$ such that \$p(x)=s(x)(x-a)^k\$ and \$s(a)\ne0\$.
For example, the ...
- 4,755
7
votes
5
answers
482
views
Multiply multivariate polynomials
We already have a challenge about multiplying multiply single-variable polynomials. This challenge is about multiply two polynomials with multiple variables
Your task is given two multi-variable ...
- 5,677
17
votes
18
answers
2k
views
Computing a specific coefficient in a product of polynomials
Generator functions
This gives the context for why this challenge came to life. Feel free to ignore.
Generator functions are a nice way of encoding the solution to a problem of combinatorics. You ...
- 1,360
19
votes
14
answers
2k
views
Rook Polynomials
In combinatorics, the rook polynomial \$R_{m,n}(x)\$ of a \$m \times n\$ chessboard is the generating function for the numbers of arrangements of non-attacking rooks. To be precise:
$$R_{m,n}(x) = \...
- 61
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.
...
- 46.5k
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 ...
- 4,755
14
votes
14
answers
2k
views
Print all Polynomials
The set of all polynomials with integer coefficients is countable.
This means that there is a sequence that contains each polynomial with integer coefficients exactly once.
Your goal is it to write a ...
- 20.4k
15
votes
7
answers
1k
views
Solve quadratic equations when 1+1=0
There already have been multiple challenges about carryless
multiplication, this challenge will work with the same calculation rules.
You task is given a quadratic polynomial ...
- 12.5k
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 <...
- 987
26
votes
19
answers
3k
views
Laguerre Polynomials
Laguerre polynomials are nontrivial solutions to Laguerre's equation, a second-order linear differential equation: \$xy''+(1-x)y'+ny=0\$. For a given value of \$n\$, the solution, \$y\$, is named \$...
29
votes
22
answers
3k
views
Calculate the Ultraradical
What is the Ultraradical?
The ultraradical, or the Bring radical, of a real number \$a\$ is defined as the only real root of the quintic equation \$x^5+x+a=0\$.
Here we use \$\text{UR}(\cdot)\$ to ...
- 6,265
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 ...
- 68.1k
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 ...
- 131
12
votes
6
answers
1k
views
Approximate a root of an odd degree polynomial
Every odd degree polynomial has at least one real root. However this root does not have to be a rational number so your task is to output a sequence of rational numbers that approximates it.
Rules
...
- 188k
18
votes
1
answer
675
views
Golfing Expressions
We can write mathematical expressions using the standard math operators (,),+,...
- 47.1k
6
votes
2
answers
376
views
Partial Fractions
Given an input of a string, output the partial fraction in string form.
The partial fraction decomposition of a rational fraction of the form \$\frac{f(x)}{g(x)}\$, where \$f\$ and \$g\$ are ...
- 4,964
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 ...
- 49.4k
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
18
votes
16
answers
2k
views
Fibonacci polynomials
The Fibonacci polynomials are a polynomial sequence defined as:
\$F_0(x) = 0\$
\$F_1(x) = 1\$
\$F_n(x) = x F_{n-1}(x) + F_{n-2}(x)\$
The first few Fibonacci polynomials are:
\$F_0(x) = 0\$
\$F_1(x) ...
- 12.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 ...
- 46.5k
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 ...
- 46.5k
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 ...
- 46.5k
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 ...
- 46.5k
15
votes
14
answers
2k
views
Multiply Two Integer Polynomials
Your task is to take two single-variable integer polynomial expressions and multiply them into their unsimplified first-term-major left-to-right expansion (A.K.A. FOIL in the case of binomials). Do ...
- 46.5k
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 ...
- 46.5k
9
votes
14
answers
1k
views
ASCII-Plot the equation
You are given a polynomial function, in the following format:
\$x = (c_0 * y^0) + (c_1 * y^1) + (c_2 * y^2) + ... + (c_n * y^n)\$
where \$c_n\$ stands for the coefficient of the \$n^{th}\$ power of \$...
- 46.5k
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 ...
- 96.5k
27
votes
7
answers
1k
views
Recover polynomial \$f(x)\$ from \$f^2(x)\$
Related: Calculate \$f^n(x)\$, Polynomialception
Challenge
Given a polynomial \$f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_k x^k\$ of order \$k\$, we can compute its composition with itself \$f\left(f(...
- 46.5k
14
votes
11
answers
4k
views
Find The Local Maxima And Minima
Definition
The maxima and minima of a given function are the largest and smallest values of the function either within a given range or otherwise within the entire domain of the function.
Challenge
...
- 32.5k
17
votes
7
answers
2k
views
Define the finite field GF(9)
\$GF(9)\$ or \$GF(3^2)\$ is the smallest finite field whose order isn't a prime or a power of two. Finite fields of prime order aren't particurlarly interesting and there are already challenges for \$...
- 49.4k