# Questions tagged [algorithms]

Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

3,715 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
• 1,031
557 views

### Is there a numeral system that makes both addition and multiplication easy?

Decimal positional notation, the system for writing numbers we all use every single day, makes addition very easy by transforming it from a computation to a repeated operation on individual digits (...
460 views

### What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
269 views

### Recovering a binary function on a lattice by studying its sum along closed paths

I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following: Given an even ...
• 4,333
168 views

### Random domino tilings: Is this distribution well-defined, and how can it be sampled from?

I'd like to ask questions about a "random domino tiling of the plane". However, it's not quite obvious how to go about precisely specifying what this means. My first instinct was to do ...
• 17.6k
2k views

### Is there a Sokoban level with such conditions

First of all, let me explain what Sokoban is. It is a logic game created in Japan and it literally means "warehouse keeper". It is a type of transport puzzle, in which the player pushes boxes or ...
607 views

### Solving general (dis)entanglement puzzles

What is the state of the art in (modelling and) solving a general (dis)entanglement puzzle? The following picture shows a nice example: There is a project called "The Untangler", which seems to be ...
426 views

### Peaks in the circle chaos game

The chaos game is a random walk that steps halfway between your current position and a set of predefined points. If the points are on an equilateral triangle, the resulting set is Sierpinski's ...
• 6,687
257 views

### The practical usage of Arnold Matrix Trace Theorem

I would like to ask about the Arnold's Matrix Trace theorem: $$\textrm{tr}\big(A^{p^k}\big)\equiv\textrm{tr}\big(A^{p^{k-1}}\big)\ (\!\!\bmod {p^k}).$$ This theorem looks fantastic to me. But is ...
• 1,818
601 views

### Determining sign(det(A)) for nearly-singular matrix A

Motivation: determining whether a point $p$ is above or below a plane $\pi$, which is defined by $d$ points, in a $d$-dimensional space, is equivalent to computing the sign of a determinant of a ...
• 257
2k views

220 views

• 1,006
312 views

### Harmonic Numbers' Numerators Divisible by a Prime $p$

For a prime $p$, I am trying to determine the set of all $n$ for which the numerator of $H_n$ is divisible by $p$, with $H_n$ being the $n$'th harmonic number. After going through a lot of literature, ...
• 1,022
141 views

### Is this kind of "Gerrymandering" NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
• 6,639
710 views

### Packing problem - how to fit things nicely with just the aspect ratio of the objects

Suppose you have a rectangle that is w units wide and h units tall (bounding rectangle). You also have an even ...
213 views

• 101
1k views

### Implementing the Risch algorithm to integrate $\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}$

Following the work of Andreas Wurfl i am trying to implement the Risch algorithm on $\int{\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}dx}$ following his method for extensions that are purely logarithmic, we ...
• 453
2k views

### Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
• 161
1k views

### Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
• 171