Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

5
votes
2answers
405 views

Generate all binary numbers, a single bit flip a time

Is it possible to sequentially generate all $n$-bit configurations (say, the binary representation of a an $n$-digit number), a single bit flip a time, in such a way that no configuration is generated ...
5
votes
6answers
2k views

Calculate $\pi$ to an accuracy of 5 decimal places?

In this message at point 18 I saw following programming question: Given that $\pi$ can be estimated using the function $4(1 – 1/3 + 1/5 – 1/7 + \ldots)$ with more terms giving greater accuracy, ...
5
votes
3answers
863 views

programming brain teaser

Given a programming language where you could make as many variables up as possible and you could only perform these three operators find b-1. ...
5
votes
5answers
267 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 ...
5
votes
2answers
93 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
5
votes
3answers
2k views

How to accurately calculate the error function erf(x) with a computer?

I am looking for an accurate algorithm to calculate the error function I have tried using [this formula] (http://stackoverflow.com/a/457805) (Handbook of Mathematical Functions, formula ...
5
votes
1answer
260 views

Do irrational number contain infinite/every patterns of sequences?

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
5
votes
2answers
332 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
5
votes
1answer
237 views

Is there an efficient algorithm to determine the parity of the longest path in a graph?

Finding the longest path in a graph is intractable problem. Th decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in ...
5
votes
2answers
135 views

Choosing between $n$ things using dice?

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die? For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
5
votes
2answers
210 views

An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have. Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm ...
5
votes
2answers
376 views

Lights Out Variant: Flipping the whole row and column.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so: 1 0 0 00 0 0 00 1 0 0 0 0 1 0 When you selected a ...
5
votes
2answers
396 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
5
votes
2answers
3k views

Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?

This definition is extracted from "Introduction to Algorithm, 2nd Edition". The iterated logarithm function We use the notation $\lg^* n$ (read "log star of $n$") to denote the iterated ...
5
votes
2answers
117 views

How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

The Wikipedia article for the Collatz conjecture states that: The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$. It gives ...
5
votes
7answers
3k views

Prime number generator, how to make

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes... The objective is: given a first prime, ...
5
votes
2answers
772 views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
5
votes
3answers
219 views

FFT for power of 3

Classic FFT works fine, when n is power of 2. How to generalize FFT procedure when n is power of 3? Is it possible to easily ...
5
votes
1answer
34 views

Under what circumstances does this procedure terminate?

This earlier question (essentially) asked why the following loop will terminate. (This is Java code, so assume you're working with signed, 32-bit integers:) ...
5
votes
2answers
123 views

Algorithmic approach to enumerating ideals in $\Bbb Z[x]/(m, f(x))$

I'm studying for my algebra quals this fall and keep encountering problems like the following: List all the ideals of $\mathbb{Z}[x]/(16, x^3)$. or List all the primes of ...
5
votes
1answer
1k views

XOR properties in set of numbers

Say I have n positive numbers A1,A2...An and Ak is minimum among them. And d is a number ...
5
votes
1answer
961 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 ...
5
votes
3answers
179 views

Test whether an interval contains integer points

I want to make a non-complex (for algorithmic implementation) logical condition to test whether some real interval contains any integer points. Let $x$ be an interval with bounds $l, r$; Let ...
5
votes
4answers
683 views

How can I change the Conway's Game of Life so that, eventually, all cells die?

Darwinia features an intro which represents a modified version of Conway's Game of Life. You can see it in action here. The game developers added one more rule about the game: no cell may live ...
5
votes
2answers
512 views

What is the best way to factor arbitrary polynomials

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but ...
5
votes
1answer
375 views

Why does the method to find out log and cube roots work?

To find cube roots of any number with a simple calculator, the following method was given to us by our teacher, which is accurate to atleast one-tenths. 1)Take the number $X$, whose cube root needs ...
5
votes
1answer
211 views

Rabin and Shallit Algorithm

I want to implement Rabin and Shallit algorithm for representing a positive integer as a sum of three squares. Can anyone give me a rough sketch of the method? I searched through the internet but ...
5
votes
4answers
205 views

Looking for a significant example that highlights the suboptimality of the greedy algorithms

A week from now, I'll have to present my work to a bunch of coworkers who aren't used to the optimisation world and terminology. One of the main algorithms I implemented uses a greedy type algorithm ...
5
votes
2answers
335 views

Is there a branch of math studying music algorithms?

I have found 2-3 search engines for scientific studies, things like algorithms, thesis, piece of researches and stuff like that; I'm really surprised to see a lot of applications for the math ...
5
votes
1answer
193 views

Algorithm creating subsets with certain properties

I'm trying so solve following problem: Let's say, we have a set $A=\{1,2,3,...,49\}$. Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= ...
5
votes
3answers
696 views

Inverse of symmetric matrix $M = A A^\top$

I have a matrix, generated by the product of a non-square matrix with its own transpose: $$M = A A^\top.$$ I need the inverse of $M$, assuming $\det(M) \neq 0$. Given the nature of the matrix $M$, ...
5
votes
1answer
168 views

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the ...
5
votes
3answers
121 views

Understanding this summation identity

I'm currently reading a book in which part of the solution to the problem involve this identity: $$\sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j-\sum_{j=1}^{i}j$$ Which I cannot derive myself. The only thing ...
5
votes
1answer
6k 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'? ...
5
votes
2answers
401 views

Clustering algorithm to cluster objects based on their relation weight

I have $n$ words and their relatedness weight that gives me an $n\times n$ matrix. I'm going to use this for a search algorithm but the problem is I need to cluster the entered keywords based on their ...
5
votes
3answers
539 views

A balanced latin rectangle (more rows than columns)

In psychology we sometimes use balanced latin squares for the order of our tests to counterbalance first-order carry-over effects (fatigue, learning, etc.) . For our current study we want to pretest ...
5
votes
1answer
198 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
5
votes
1answer
190 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 ...
5
votes
1answer
256 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 ...
5
votes
2answers
327 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
5
votes
1answer
1k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
5
votes
4answers
169 views

Algorithm for randomly choosing learning cards

I'm programming a learning software. It works with question-/answercards. I´m searching for a algorithm that gives me a higher probability for cards that the user has answered wrong. My actual idea ...
5
votes
1answer
201 views

solve $\ln(n!) = \Theta(n\ln(n))$ without stirling approximation

My homework was proving this equation which is simple using Stirling approximation. I was wondering if there is any other method to prove it - whithout Stirling - I can prove $\ln(n!) = O(n\ln(n))$ ...
5
votes
2answers
213 views

Generating seating plans- maximal number of orderings with different adjacencies

Background: So the school I work at has a policy that we try and sit the kids next to as many different other kids as possible throughout the academic year. This means rejigging the seating plan as ...
5
votes
2answers
295 views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is ...
5
votes
1answer
337 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
1answer
880 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
5answers
687 views

Least wasteful use of stamps to achieve a given postage

You have sheets of 42-cent stamps and 29-cent stamps, but you need at least $3.20 to mail a package. What is the least amount you can make with the 42- and 29-cent stamps that is ...
5
votes
2answers
173 views

Understanding Intel's white paper algorithm for multiplication in $\text{GF}(2^n)$?

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials ...
5
votes
2answers
95 views

Puzzle about voting

I came across about this puzzle which I'm not sure how to go about. Suppose there are $L$ leaders and $F$ followers, with $1 < L<<F$. A leader makes a binary decision, $0$ or $1$ with same ...