# Tagged Questions

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).

566 views

### Algorithm for constructing primes

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$? There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking ...
345 views

### Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
2k views

### One number divisible by all prime factors of another?

Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
9k views

### Is there a simple method to do LU decomposition by hand?

Today my professor in numerical analysis pointed out that in the exam we will probably have to do LU decomposition by hand. I'm understand how the decomposition works theoretically, but when it comes ...
2k views

### Factoring large integers without a cluster

What is the best program to factor large arbitrary-form integers on a single computer, or on a few disjointed computers? "Best" is obviously subjective, but what do you recommend? I'm working on a ...
5k views

### Algorithm for generating integer partitions

I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
110 views

### Santa is secretly deranged! or, how to hand-generate assignments for a gift exchange?

Consider a standard Secret Santa/gift exchange game draw. We have a pool of $n$ people, each of whom is supposed to be assigned another member of the pool to find a gift for, without the recipient ...
10k views

### How to prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$?

Using the basic definition of theta notation prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$ I came across two answer to this question on this website but the answers weren't clear to me. Would ...
517 views

### Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none of ...
187 views

### Finding XOR of all even numbers from n to m

Problem : Given a range $[n,m]$, find the xor of all even numbers in this range. Constraints : $1 \le n \le m \le 10^{18}$ How do we solve this problem? P.S. I asked this question at stackoverflow ...
1k views

### Partition a binary tree by removing a single edge

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a ...
861 views

### What would be the shortest path between 2 points when there are objects obstructing the straight path?

How would an algorithm find the shortest distance between 2 points on a horizontal 2d plane , especially when a straight path is not possible? Could it be something on the lines of calculating least ...
471 views

### Understanding AKS

new user here. Where does a layman go to get a basic understanding of AKS primality testing. I am not talking about the optimal choice of "r" (which I am told is the hardcore number theoretic part of ...
462 views

### Is there a binary spigot algorithm for log(23) or log(89)?

The Bailey-Borwein-Plouffe formula yields a binary spigot algorithm for π, and related formulas give the bits of log(2) and those of the logarithms of some other integers. I got stuck (over a year ...
1k views

### Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
150 views

### Bounds on the gaps in a variant of polylog-smooth numbers.

Sorry for the long intro. I think the explanation motivates the question and puts it in context. But if you want to skip the story, then just move on to the grey boxes; they should contain enough ...