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)

80
votes
4answers
2k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
56
votes
2answers
3k views

Fastest way to check if $x^y > y^x$?

What is the fastest way to check if $x^y > y^x$ if I were writing a computer program to do that? The issue is that $x$ and $y$ can be very large.
46
votes
2answers
2k views

How do the Catalan numbers turn up here?

The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
45
votes
4answers
12k views

How to use the Extended Euclidean Algorithm manually?

I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
43
votes
1answer
2k views

Sums of prime powers

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum? For concreteness, you ...
39
votes
4answers
18k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
34
votes
1answer
2k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
32
votes
2answers
2k views

A natural number multiplied by some integer results in a number with only ones and zeros

I recently solved a problem, which says that, A positive integer can be multiplied with another integer resulting in a positive integer that is composed only of one and zero as digits. How can ...
32
votes
2answers
924 views

Can every number be written as a small sum of sums of squares?

In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, (k-1)\...
31
votes
5answers
3k views

Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
31
votes
6answers
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
30
votes
12answers
2k views

Computing irrational numbers

I am genuinely curious, how do people compute decimal digits of irrational numbers in general, and $\pi$ or nth roots of integers in particular? How do they reach arbitrary accuracy?
29
votes
2answers
3k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
29
votes
4answers
12k views

Calculator algorithms

Does there exist a good reference on the algorithms used by calculators, especially on the trigonometric and transcendental functions? I would still like to know how Casio generates its random ...
28
votes
5answers
13k views

How can I find the square root using pen and paper?

Okay, I know this is very basic question. I learned 2 methods in school. But now, I forget one. Here is a simple method that I know. Find the prime divisors of the number Omit the half of numbers ...
28
votes
1answer
2k views

How can we turn any number into a prime number by simply adding more digits?

How can we turn any number (where the number is > 2) into a prime number by simply appending more digits? I'm referring to the right side of the number. So 4 is not a prime number But If I append ...
26
votes
6answers
6k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
26
votes
5answers
4k views

Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...
26
votes
4answers
1k views

Is there a branch of Mathematics which connects Calculus and Discrete Math / Number Theory?

I am asking this question out of both curiosity and frustration. There are many problems in computer science which require you to perform operations on a finite set of numbers. It always bothers me ...
25
votes
5answers
4k views

Find taxicab numbers in $O(n)$ time

This is a final exam question in my algorithms class: $k$ is a taxicab number if $k = a^3+b^3=c^3+d^3$, and $a,b,c,d$ are distinct positive integers. Find all taxicab numbers $k$ such that $a,b,c,d &...
25
votes
3answers
767 views

Sudoku with special properties

Sudoku is a puzzle, with the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also "sudoku-blocks") contains all of ...
23
votes
5answers
8k views

How does one compute the sign of a permutation?

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula $${\rm sgn}(\sigma) =...
21
votes
3answers
664 views

Finding the Robot

There are five boxes in a row. There is robot in any one of these five boxes. Every morning I can open and check a box (one only). In the night, the robot moves to an adjacent box. It is compulsory ...
21
votes
4answers
12k views

Simple explanation and examples of the Miller-Rabin Primality Test

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...
21
votes
2answers
931 views

Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely, $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$ This is Theorem 4 ...
20
votes
2answers
18k views

Explanation on arg min

would someone be so kind to explain this to me: Especially the arg min part. (it's from the k-means algorithm)
20
votes
1answer
500 views

Extracting individual race results from Mario Kart final scores

In Mario Kart, one "cup" involves 4 races, and after every race each racer gets points awarded based on what place they came in (better rank means more points). After playing it enough I grew curious ...
19
votes
9answers
28k views

Efficient way to determine if a number is Perfect Square

Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for ...
19
votes
4answers
14k views

Non-power-of-2 FFT's?

If I have a program that can compute FFT's for sizes that are powers of 2, how can I use it to compute FFT's for other sizes? I have read that I can supposedly zero-pad the original points, but I'm ...
19
votes
6answers
1k views

Algorithm for calculating $A^n$ with as few multiplications as possible

Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $A^n$ in a structure where multiplication is associative? For example, suppose $A$ is a square matrix. ...
19
votes
0answers
1k views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
18
votes
2answers
996 views

Puzzle: Cracking the safe [duplicate]

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream $...
18
votes
2answers
652 views

Embedding as a subgroup

Suppose I am given two finite groups $G$ and $H$ (not too large: let's say their orders are around $10000$ and $100$ respectively, and the order of $H$ divides the order of $G$). These may be ...
17
votes
4answers
11k views

Do dynamic programming and greedy algorithms solve the same type of problems?

I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically, As far as I know, the type of problems that dynamic ...
17
votes
4answers
8k views

Determining whether a symmetric matrix is positive-definite (algorithm)

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition. The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky ...
17
votes
6answers
2k views

Detecting perfect squares faster than by extracting square root

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which ...
17
votes
3answers
2k views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
17
votes
0answers
319 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 ...
16
votes
6answers
23k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
16
votes
1answer
3k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
15
votes
3answers
2k views

Quickest way to determine a polynomial with positive integer coefficients

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. ...
15
votes
1answer
14k views

What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?

I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
15
votes
1answer
442 views

Books to understand the construction of all groups of a specific order

The algorithms introduced by Besche–Eick (1999) were used to construct (or count) the groups of order up to 2000 in Besche–Eick–O'Brien (2002), yet I find the algorithms somewhat inaccessible. How ...
15
votes
3answers
6k views

Finding the intersection point of many lines in 3D (point closest to all lines)

I have many lines (let's say 4) which are supposed to be intersected. (Please consider lines are represented as a pair of points). I want to find the point in space which minimizes the sum of the ...
15
votes
2answers
228 views

Decomposition of an algebraic number into a sum or product of algebraic numbers with smaller degree

An algebraic number can be identified by its minimal polynomial together with isolating intervals with rational bounds for its real and imaginary parts. The degree of an algebraic number is the degree ...
15
votes
1answer
108 views

Is there an algorithm for deciding big/little-O queries?

Consider the following question: Is $2^{o(\log n)} = o(n^c)$ for every constant $0 < c < 1$? I can try to answer this question using basic limits to get that the answer is "yes." I can ...
15
votes
2answers
1k views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
14
votes
3answers
13k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...
14
votes
4answers
259 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 or n]...
14
votes
0answers
178 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...