Questions tagged [polynomials]
For challenges involving polynomials, mathematical expressions that consist of variables and coefficients.
89
questions
38
votes
23
answers
3k
views
Pretty Print Polynomials
Introduction
Humans are a remarkable species, but we can be very awkward to understand sometimes—especially for computers.
In particular, we seem to like writing polynomials in a very ...
- 441
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
29
votes
26
answers
3k
views
Fundamental Solution of the Pell Equation
Given some positive integer \$n\$ that is not a square, find the fundamental solution \$(x,y)\$ of the associated Pell equation
$$x^2 - n\cdot y^2 = 1$$
Details
The fundamental \$(x,y)\$ is a pair of ...
- 43.7k
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,178
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
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(...
- 73.8k
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 \$...
- 2,049
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
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
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
23
votes
28
answers
3k
views
"Factorise" a quadratic [duplicate]
When learning to factorise quadratics in the form \$x^2 + ax + b\$, a common technique is to find two numbers, \$p, q\$ such that
$$pq = b \\
p + q = a$$
as, for such numbers, \$x^2 + ax + b = (x + p)(...
- 49.4k
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
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
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
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
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
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
21
votes
4
answers
511
views
Compute height of Bowl Pile
Bowl Pile Height
The goal of this puzzle is to compute the height of a stack of bowls.
A bowl is defined to be a radially symmetric device without thickness.
Its silhouette shape is an even ...
- 451
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
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
17
answers
2k
views
Find Integral Roots of A Polynomial
Challenge
The challenge is to write a program that takes the coefficients of any n-degree polynomial equation as input and returns the integral values of x for which the equation holds true. The ...
- 5,260
20
votes
8
answers
1k
views
Counting Distinct Real Roots of Low-Degree Polynomials
Challenge: I want to know about the real roots of polynomials. As a pure mathematician, I care about the existence of such roots, rather than their numeric values.
The challenge is to write the ...
- 559
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
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
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) = \...
- 46.5k
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\$ ...
- 46.5k
19
votes
3
answers
388
views
A multiple of n in every base!
In November 2019, Alon Ran published a particularly lovely sequence in the OEIS, A329126:
\$a(n)\$ is the lexicographically earliest string of digits which yields a multiple of \$n\$ when read in any ...
- 8,659
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
18
votes
19
answers
4k
views
Evaluate polynomial expression string
Create a function which takes a polynomial equation, a value for x and returns the result of the operation.
Example: given ...
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) ...
- 46.5k
18
votes
18
answers
2k
views
Determine the degree of a polynomial
Background:
For this challenge, a polynomial looks like this:
$$P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_2x^2+a_1x+a_0$$
The degree, \$n\$, is the highest power \$x\$ is raised to. An example of a degree 7 ...
- 18.6k
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
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 ...
- 46.5k
18
votes
1
answer
675
views
Golfing Expressions
We can write mathematical expressions using the standard math operators (,),+,...
- 281
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 ...
- 14k
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
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 \$...
- 10.5k
17
votes
5
answers
1k
views
Are you a probabilist or a physicist?
Hermite polynomials refer to two sequences of polynomials:
The "probabilist's Hermite polynomials", given by
$${He}_n(x) = (-1)^n e ^ \frac {x^2} 2 \frac {d^n} {dx^n} e ^ {-\frac {x^2} 2}$$
...
- 49.4k
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
15
votes
14
answers
1k
views
Generating generating expressions for sequences
(yes, "generating generating" in the title is correct :) )
Context
In middle (?) school we are taught about sequences and, in particular, we are taught about linear sequences where the ...
- 14k
15
votes
16
answers
898
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 ...
- 43.7k
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 ...
- 9,891
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 ...
- 5,677
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 ...
- 5,677
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
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 ...
- 46.5k
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
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 ...
- 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
...
- 5,260
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