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)

9
votes
2answers
244 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...
7
votes
3answers
2k 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
143 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 ...
7
votes
1answer
144 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 ...
6
votes
1answer
500 views

Count expressions with 1s and 2s

Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * ...
6
votes
5answers
303 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
1answer
751 views

Finding all roots of polynomial system (numerically)

I want to numerically find all the roots of a system of polynomials (n equations in n variables). Since I can compute the Jacobian for the system (analytically or otherwise), I can use the Newton ...
5
votes
3answers
14k views

Algorithms for Finding the Prime Factorization of an Integer

As practice, I am currently writing a program that takes a given integer $n$ as input, and then finds the (unique) prime factorization of $n$, provided $n$ is composite. My question is about ...
5
votes
1answer
230 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?
5
votes
3answers
405 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
3k views

how to diagonalize a large sparse symmetric matrix, to get the eigenvalues and eigenvectors

How does one diagonalize a large sparse symmetric matrix to get the eigenvalues and the eigenvectors? The problem is the matrix could be very large (though it is sparse), at most 2500*2500. Is there ...
5
votes
3answers
652 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 ...
4
votes
2answers
119 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
698 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
640 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 ...
3
votes
2answers
6k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
3
votes
1answer
293 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 ...
2
votes
0answers
117 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 ...
2
votes
2answers
90 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
0answers
313 views

Count swap permutations

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

Number of horse races to determine the top three out of 25 horses [duplicate]

This is a short mathematical puzzle from mindciphers.com which says : The London racetrack needs to submit its top three horses to the Kentucky Derby next month in order to compete for a prize. ...
2
votes
1answer
105 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
1answer
209 views

how to generate all possible equations with a set of number and operators?

i got a maths problem, for given that a set of character {1,2,3,4,5,6,7,8,9,+,-,*,/}. and then by using the set of characters to randomly generate 10(or let say N) characters in an array, i.e. ...
2
votes
1answer
158 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 ...
1
vote
2answers
115 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
2answers
290 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 ...
1
vote
2answers
449 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 ...
1
vote
2answers
93 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
4k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
1
vote
1answer
231 views

Finding the topological genus of a triangulated surface

Given is a surface represented through a triangle mesh (as commonly used in computer graphics, with vertices, edges and faces). The surface is known to be "watertight", i.e. no missing faces. Is ...
0
votes
0answers
46 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 ...
0
votes
2answers
2k views

Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$

I want to Arrange the following growth rates in increasing order This order are following : $O (n (\log n)^2), O ((35)^n), O(35n^2 + 11), O(1), O(n \log n)$ Please give me idea how to arrange growth ...
-9
votes
2answers
218 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 ...
10
votes
2answers
132 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 ...
9
votes
1answer
4k views

Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height

I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of ...
9
votes
1answer
3k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
9
votes
2answers
10k views

How to calculate the number of decimal digits for a binary number?

I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but... Given a number represented in binary, it's ...
8
votes
1answer
2k views

On problems of coins totaling to a given amount

I don't know the proper terms to type into Google, so please pardon me for asking here first. While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
7
votes
0answers
378 views

Problem with an algorithm to $3$-colour the edges of cubic graphs

I'm currently trying to implement an algorithm to $3$-colour the edges of cubic graphs. (I want to do this with Matlab's Symbolic toolbox). After restricting to planar graphs to ensure the existence ...
7
votes
1answer
10k views

How to compute the Pareto Frontier, intuitively speaking?

I'm working on a multi-objective optimization problem and we have 'alternatives' that are quantified on two dimensions - value and cost. Now the question is 'how does one compute a pareto frontier'? ...
7
votes
1answer
385 views

Algorithm for scrolling through different orbits in a permutation group

Given an $n\in\mathbb{N}$, and a permutation $\pi\in S_{n}$, denote the centralizer of $\pi$ by $C_{\pi}$. Now we can look on the conjugation action of $C_{\pi}$ on $S_{n}$ and then divide $S_{n}$ to ...
7
votes
1answer
1k views

Why are Hornsat, 3sat and 2sat not equivalent?

I have been reading a little bit about complexity theory recently, and I'm having a bit of a stumbling block. The horn satisfiability problem is solvable in linear time, but the boolean satisfiability ...
7
votes
1answer
239 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
6
votes
1answer
196 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
6
votes
3answers
788 views

$3 \times 3 $ Magic Square of Squares

On picture below is three-by-three magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the ...
6
votes
1answer
1k views

Why is sorting pancakes NP hard?

An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with ...
6
votes
2answers
1k views

How/why does this noise function work?

How/why does this noise function work? ...
6
votes
1answer
1k views

Algorithm for computing square root of a perfect square integer?

My question is the following: Is there a polytime non-numerical algorithm for computing square root of perfect square integers? The more elementary the algorithm is, the better! EDIT: ...
5
votes
1answer
2k views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
5
votes
1answer
239 views

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?

Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed? We define $f(n)=m$ where the digits of $m$ and $n$ are reverse. Such as ...