Questions tagged [polynomials]
For challenges involving polynomials, mathematical expressions that consist of variables and coefficients.
31
questions
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
12
votes
18
answers
1k
views
Polynomial Laplace transform
This is a repost of this challenge, intended to revamp it for looser I/O formats and updated rules
You are to write a program which takes an integer polynomial in \$t\$ as input and outputs the ...
- 49.4k
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
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
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
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
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 ...
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
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
12
votes
2
answers
418
views
Decompose Polynomials
Given an integral polynomial of degree strictly greater than one, completely decompose it into a composition of integral polynomials of degree strictly greater than one.
Details
An integral ...
- 43.7k
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
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
9
votes
5
answers
553
views
Computing a specific coefficient in a quotient of polynomials
Context
After "Computing a specific coefficient in a product of polynomials", asking you to compute a specific coefficient of polynomial multiplication, I wish to create a "mirror" challenge, asking ...
- 14k
8
votes
2
answers
775
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
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