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

learn more… | top users | synonyms (1)

6
votes
4answers
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 ...
5
votes
2answers
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 ...
5
votes
3answers
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$?.
4
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
4answers
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 ...
3
votes
2answers
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
3answers
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 ...
12
votes
2answers
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 ...
10
votes
2answers
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 ...
9
votes
3answers
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 ...
9
votes
1answer
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 ...
9
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
3answers
156 views

Knight move variant: Can it move from $A$ to $B$

Given a $N\times N$ "chess" board (Let $N = 10^{100}$) and a knight at $(0,0)$. Can the knight go to the position $(x, y)$ with jump $[a, b]$ moves ? jump $[a, b]$ mean: the knight on $(x,...
7
votes
3answers
4k views

Finding prime factors by taking the square root

I'm trying to solve the third Project Euler problem and I'd like a little help understanding a mathematical concept underlying my tentative solution. The question reads: The prime factors of ...
7
votes
3answers
916 views

Counting primes

Let $\pi(x)$ be the number of primes not greater than $x$. Wikipedia article says that $\pi(10^{23}) = 1,925,320,391,606,803,968,923$. The question is how to calculate $\pi(x)$ for large $x$ in a ...
6
votes
3answers
3k views

“Closest pair of points” algorithm

I'm having a problem understanding why I just have to consider the next 7 points in the Closest pair of points - algorithm. Can someone explain it in greater detail?
6
votes
5answers
337 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
6
votes
0answers
73 views

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
6
votes
4answers
440 views

First Course in Linear algebra books that start with basic algebra?

I'm 30 years old, and the only math I can remember from college is basic algebra and some probabilities. Next month, I have a machine learning project I'd like to work on, but I'll need a solid ...
5
votes
1answer
764 views

Efficiently calculating the logarithmic integral with complex argument

My number theory library of choice doesn't implement the logarithmic integral for complex values. I thought that I might take a crack at coding it, but I thought I'd ask here first for algorithmic ...
5
votes
1answer
234 views

How to find the value of positive integers $a$-through-$h$

If the equation $(x-a)(x-b)(x-c)(x-d)(x-e)(x-f)(x-g) = hx$ has seven positive integer roots, and $a,b,c,d,e,f,g,h$ are positive integers too, how can we find them?
4
votes
2answers
144 views

What is the algorithm hiding beneath the complexity in this paper?

So, I am a computer scientist (at least, I'm working to become one..) and I asked a question on here concerning some mathematics behind the Mandelbrot set. A reply I recieved pointed me to this paper. ...
4
votes
2answers
783 views

Upper bound for the partial sum $\sum k \lg k$ via summation?

In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound: $$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} ...
4
votes
1answer
366 views

Reasoning the calculation of the Hilbert's distance

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data ...
4
votes
0answers
190 views

Alice and Bob make all numbers to zero game

Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn. In a turn : A player selects one of the integers, divides it ...
3
votes
1answer
453 views

Generating a random derangement

I'm having a problem about derangements that I'm trying to solve. Given a set $S = \{1,\ldots,n\}$, I want to generate a random derangement. I've considered generating a permutation and checking ...
3
votes
1answer
683 views

Knuth's algorithm for Mastermind question

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm). I ...
3
votes
2answers
354 views

When do repeated intervals of time overlap?

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time. So each ...
3
votes
0answers
486 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
2
votes
1answer
79 views

An easy reference for genetic algorithm

My field is Coding Theory and my background is Algebraic, there are many applications of Genetic Algorithm in Coding Theory, I would to know the easiest and the most elementary and introductory note ...
2
votes
4answers
4k views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
2
votes
1answer
54 views

Math Analysis Designing Algorithms

I am trying to help prepare a friend for a midterm coming up and this is one of the question on a practice midterm of 5 years ago. To be honest I have trouble recalling some of the topics of Numerical ...
2
votes
0answers
87 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
2
votes
2answers
646 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
2
votes
1answer
167 views

Are there any sets other than the usual in which we can apply Sturm's axioms?

As we all know, Sturm's axioms have completely solved the problem for finding the number of roots in an arbitrary interval $[a,b]$, using the derivative and forms a Sturm set. Now my question ...
2
votes
1answer
140 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
2
votes
0answers
128 views

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in ...
1
vote
2answers
123 views

Does anyone know of any open source software for drawing/calculating the area of intersection of different shapes?

I would like to be able to draw any number of different shapes and determine the area of their intersections. I'm looking for free, open source software. I thought about trying to code something up ...
1
vote
2answers
119 views

Is there an algorithm for writing an integer as a difference of squares?

For example, if we have $36$, is there an algorithm to determine that it may equal $10^2-8^2$? What if we blow up the number to something like $492709612098$? Can it be written as the difference of ...
1
vote
1answer
703 views

Master Theorem. How is $n\log n$ polynomially larger than $n^{\log_4 3}$

I was reading Master theorem from CLRS, and it said that $n\log n$ is polynomially larger than $n^{\log_4 3}$ while $n\log n$ is not polynomially larger than $n$. What does it mean to be ...
1
vote
2answers
920 views

Most Efficient Method to Find Roots of Polynomial [duplicate]

I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
0
votes
0answers
48 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor \frac{n}{...
-7
votes
2answers
294 views

Prove that this recurrence relation algorithm generates all positive rational numbers, and does so without repetition and in reduced form [closed]

For $n\ge 1$, generate a sequence $\{a_n\}$ such that for any even $n = 2k$: $$ a_n = a_k$$ And for any odd $n=2k+1$: $$ a_n = a_k + a_{k+1}$$ With initial conditions $a_1 = a_2 = 1$ Now, generate a ...
11
votes
1answer
567 views

Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's easy: ...
11
votes
4answers
590 views

Is there a closed-form equation for $n!$? If not, why not?

I know that the Fibonacci sequence can be described via the Binet's formula. However, I was wondering if there was a similar formula for $n!$. Is this possible? If not, why not?
10
votes
2answers
133 views

Non-revealing maximum

How can a group of people find out their maximum age without revealing any other information to each other? (Is there a book or web site about such non-revealing algorithms?) Preferably I'm looking ...