Questions tagged [algorithms]
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1,677 questions
12
votes
2
answers
694
views
Algorithm for selecting a fixed-point free permutation $\varphi:\{1,\ldots,n\}\to\{1,\ldots,n\}$
Motivation. In my younger son's class, everyone has to give a (small) Christmas present to one other student. Let $n\in\mathbb{N}$ be the number of students in the class. If you pick a permutation $\...
2
votes
0
answers
28
views
Fast calculation of the circum hyperspheres of n-simplices
first the trivial facts:
Non-degenerate n-dimensional simplices have $n+1$ corners and $\frac{(n+1)n}{2}$ edges.
The center of the circum-hypersphere from which all $n+1$ corners are equidistant can ...
- 14k
0
votes
0
answers
36
views
$O(1)$ algorithm for factoring integers of the form $n=X (X^D+O(X^{D-1}))$
Factorization of integers of special forms are of both theoretical
interest and cryptographic implications.
Experimentally we found a seemingly "large" set of integers for which a divisor ...
- 25.7k
3
votes
1
answer
309
views
Is there an algorithm which, given integer $k \ge 2 $, find all abc-tuple with $\mathrm{rad}(abc)=k$?
According to this lecture on abc
https://www.youtube.com/watch?v=zk4U5P61LbM&t=1960s around 18:00
there is a "subtle theorem" that for fixed $k \ge 2$, there are only finitely many ...
- 33
0
votes
1
answer
117
views
Closed form solutions of $x^D+y^D=n$ and $y^D-x^D=n$ assuming $y>x^{D/(D-1)}$
Let $x,y,X,Y,D>1$ be positive integers.
Let $X^D+Y^D=n$ and assume $Y>X^{D/(D-1)}$.
Conjecture 1 $Y=\lfloor n^{1/D}\rfloor$ and $X=(n-Y^D)^{1/D}$
Let $Y^D-X^D=n$ and assume $Y>X^{D/(D-1)}$.
...
- 25.7k
0
votes
0
answers
19
views
Sufficient condition for shortest path expansion by Minimum Mean Cost Cycle
Let $G=(V,A)$ be a directed graph, such that for any two vertices $v,w$, there exists a vertex $u$ such that $(v,u),(u,w)\in A$. Let $s,t\in V$, and let $c:A\rightarrow \mathbb{N}_{\geq 1}$ be arc ...
- 157
0
votes
0
answers
153
views
$O(1)$ algorithm for factoring integers of the form $p(p+O(\sqrt{p}))$?
Let $p,C$ be positive integers and assume $0 < C< \sqrt{p}$
Let $n=p (p+C) $ and assume $n$ is odd.
Conjecture 1 Given $n$ we can find $p,p+C$ with complexity computing two integer square roots ...
- 25.7k
0
votes
0
answers
158
views
On factoring integers of the form $n=(x^D+1)(y^D+1)$ and $n=(x^D+a_{D-2}x^{D-2}+\cdots+ a_0) (y^D+b_{D-2}y^{D-2}+... b_0)$ with $x,y$ of the same size
From our preprint On factoring integers of the form $n=(x^D+1)(y^D+1)$ and $n=(x^D+a_{D-2}x^{D-2}+\cdots+ a_0) (y^D+b_{D-2}y^{D-2}+ \cdots+b_0)$ with $x,y$ of the same size.
We got plausible ...
- 25.7k
11
votes
1
answer
461
views
Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?
Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]...
- 311
7
votes
0
answers
145
views
the complexity of transfinite comparison sorting
The story of finitary deterministic comparison sorting is well-known: we have the naive $O(n^2)$-time algorithms like selection and insertion sorts; once we try divide-and-conquer recursion we ...
- 301
0
votes
1
answer
117
views
Optimal probing problem
We are provided with a set of $n$ targets.
Each target is characterized by a utility value.
We know the distribution of the utility value for each target, but do not know its current value.
Therefore, ...
- 327
2
votes
0
answers
142
views
Rewriting a quaternary cubic as sums of $5$ cubes of linear forms
This question was first asked here but got no answer.
This paper by R. Garver talks about removing 4 terms from the 9th degree equation. Although everything is easy to understand, there was an ...
- 196
1
vote
2
answers
318
views
Algorithms to count restricted injections
Let the following data be given.
Two positive integers $m$ and $n$.
A family of sets $B_a \subseteq \{1, \dots, n\}$ (for $a \in \{1, \dots, m\}$).
The task is to count the number $N$ of injective ...
- 143
1
vote
0
answers
81
views
Similar algorithms for exponential transforms of some exponential generating functions
Let
$a_1(n)$ be A003713, i.e., an integer sequence whose exponential generating function $A_1(x)$ satisfies $$ A_1(x) = \log\left(\frac{1}{1+\log(1-x)}\right). $$
$a_2(n)$ be A141209, i.e., an ...
user231922
0
votes
0
answers
190
views
Practical partial fraction decomposition
I have tried to implement Ramanujan's algorithm for Solvability of a system of polynomial equations but got stuck in the final step of calculating the partial fraction decomposition from which the ...
- 14k