5
votes
2answers
136 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 ...
1
vote
2answers
44 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
2
votes
1answer
44 views

Is there a general algorithm to solve computable integral equation?

Hilbert's tenth problem ask for the general algorithm(finite number of operation) to solve of all Diophantine problems.Today, it is known that no such algorithm exists in the general case. What ...
0
votes
0answers
16 views

algorithm for traversing a fractal in a “maximally ordered” way

consider a multidimensional fractal that can be "traversed" in an arbitrary order. is there an algorithm for traversing a fractal in a "maximally ordered" way? in other words the algorithm has ...
0
votes
0answers
60 views

Finding the mathematical formula base on this C++ code

The code below is the solution to a ACM regional programming contest problem: Using credit cards for your purchases is convenient, but they have high interest rates if you do not pay your balance in ...
8
votes
2answers
118 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
0
votes
0answers
39 views

Maximum independent set problem

I need to study about the maximum independent set problem in graph theory. I need to study the $P_t$ free graphs and many other such variants and look up their maximum independent set characteristics. ...
0
votes
1answer
25 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
0
votes
0answers
41 views

Decision Making Algorithms - Chaos Theory

I'm doing research on decision making algorithms on robotics. And recently I've read a lot of about Chaos Theory. I've searched all over the web, in IEEEXplore, ACM Digital Library, but can't find any ...
3
votes
0answers
58 views

Operational Research. (Ressource Management)

I am looking for a solution that i know exists already in the field of "Operational Research"... I Just can't put my finger on the name of the thing. An heuristic to solve a very common and simple ...
1
vote
0answers
15 views

software to decide whether a 2-generator subgroup of PSL(2,R) is discrete/free

Gilman developed an algorithm with polynomial complexity that, given two elements in PSL(2,R), decides whether the group they generate is free/discrete or not. I was wondering whether anybody ever ...
2
votes
1answer
100 views

Generalized Straight Skeleton

The straight skeleton of a polygon can be computed by having the edges of the polygon move inwards at a uniform constant speed. Is it useful to generalize this computation process by varying the ...
4
votes
0answers
164 views

Test for equivalence of algebraic expressions

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
5
votes
3answers
390 views

Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms? Thanks.
7
votes
1answer
415 views

efficient summation of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a ...
0
votes
1answer
46 views

Algorithm to generate single iterative formula from an arbitrary sequence of numbers.

The end goal is to be able to compress paragraphs of words into arbitrary formulae, where the formula is calculated by some software using algorithms. So, is it possible to generate arbitrary ...
2
votes
1answer
80 views

Is there an efficient way to compute 2-separations of matroids?

Edit: Pointers to helpful references would also be appreciated, of course. The topic of matroids is a relatively new one for me and I don't personally know any experts of this subject. Thus, if I do ...
16
votes
1answer
392 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 ...
3
votes
1answer
127 views

Graph clique problem

I'm not sure to what degree this is a graph problem, and algorithms question, or what, but I'll give the setup: I have a simple undirected graph given in the form (for example) ...
1
vote
0answers
62 views

Are there books on algorithms for architecture?

I need books on algorithms for organic/nonlinear and linear architect anyone recommend a book?
3
votes
0answers
140 views

Difference between two sets of data points

I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
2
votes
1answer
78 views

Details about “fingerprinting” algorithms for groups?

where can I find details about "Fingerprinting" algorithms (to test whether two groups are non-isomorphic) "‘Fingerprinting’: For every group $G_1,…, G_r$ evaluate various isomorphism-invariant ...
0
votes
1answer
94 views

What is a good reference for basic shape detection algorithms

I've been doing research for a presentation on computer vision, and right now I'm specifically researching shape detection. Since this is a math course and not a programming course, I'm only concerned ...
0
votes
3answers
190 views

Algorithm to find all vertices exactly $k$ steps away in an undirected graph

This question may be better served at cs.SE, but I am not very familiar with CS lingo, so I'm hoping the maths community would be able to answer it as well... I have an undirected graph, and I am ...
8
votes
1answer
3k views

Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
3
votes
3answers
316 views

For Maths Major, advice for perfect book to learn Algorithms and Date Structures

Purpose: Self-Learning, NOT for course or exam Prerequisite: Done a course in basic data structures and algorithms, but too basic, not many things. Major: Bachelor, Mathematics My Opinion: Prefer ...
2
votes
0answers
314 views

Mathematics in the “ The Art of Computer Programming”

I don't know of this the right place to ask this type of question and hence I apologize (in advance) for any inconvenience. Here is my question: I have studied Concrete Mathematics by Knuth, Graham ...
1
vote
0answers
61 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = \{ G_i \}_{i=1 \ldots n} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_i ...
1
vote
0answers
277 views

Augmenting Path Algorithm for Maximum Matching

I have a rather cryptic pseudo code version of the augmenting path algorithm for finding a maximum matching in a bipartite graph in my notes. I m not sure it s correct, and there are some parts that ...
2
votes
3answers
202 views

Games with human edge [closed]

Which are some two- or one-player games, where humans far outperforms the best computer programs? And how does the relative edge scale with time allowed to think? (In time frame 1 sec to 8 hours per ...
5
votes
1answer
91 views

How to find the sparsest vector in a given subspace of $\mathbb{F}_2^n$

A subspace $C$ of $\mathbb{F}_2^n$ is given for some $n \geq 1$. The space $C$ is given by its basis. Is there a polynomial time algorithm to find the (nonzero) vector in $C$ of lowest hamming ...
5
votes
1answer
153 views

A trivial but maybe nonetheless non-trivial method of inferring primality

The topologist J. H. C. Whitehead (not to be confused with his famous uncle) said it is naive to think a theorem is trivial merely because its proof is trivial. Hence I'm wondering if a certain ...
1
vote
0answers
66 views

What is the most efficient algorithm for constructing an irreducible polynomial?

Theorem: Assuming that the generalized Riemann hypothesis is true, there is a deterministic polynomial time algorithm to find an irreducible polynomial of degree $n$ over $\mathbb{F_p}$ The ...
3
votes
2answers
2k views

How to construct magic squares of even order

Could someone kindly point me to references on constructing magic squares of even order? Does a compact formula/algorithm exist?
5
votes
2answers
336 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 ...
2
votes
1answer
60 views

Specific solvable cases of TSP

Did a quick search on polynomial time solvable TSP and found some references such as this one for special cases for the bottleneck TSP. Was wondering if anyone was aware of any references that catalog ...
1
vote
1answer
565 views

Algorithm for finding limits of compositions of simple functions?

There are two questions: Define the set $S$. Compute the limit of functions $f/g$ for functions $f,g\in S$, where $S$ is defined in the following way. All constant function are in $S$, $f(n) = ...
6
votes
1answer
135 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 ...
1
vote
1answer
256 views

Number of operations in grade school algorithm for multiplying 577 and 423

Given 577 x 423 with grade school algorithm you calculate 577 x 3 = 1731 577 x 2 = 1154 577 x 4 = 2308 These are 3 multiplications of a number by a single digit. Then, you go on and add 1731 + ...
3
votes
5answers
294 views

good resources for getting started with algorithms

I am reasonably mathematically competent and use algorithms regularly in computing, however I have started reading through 'introduction to algorithms' but find I need to understand a few more basics ...
1
vote
3answers
298 views

Can you help me translate this programming algorithm into mathematical language? Has prior work been done on the “LFSR” problem already?

There is this programming/mathematical problem I have; it is the problem of generating a sequence of n unique random numbers, where the random number $n$ is element of of the set $S = \{0, 1, 2, ...
10
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
0
votes
2answers
347 views

References with explanations of how works CORDIC algorithm for division

Does anyone know any available reference to learn how works CORDIC algorithm to implement a division? Thank you!
3
votes
2answers
369 views

Voronoi decomposition implementation in four dimensions?

I'm a software engineer and have been asked to research a Voronoi implementation in four dimensions. I'm not asking for "teh codez" but am interested in approachable tutorials on Voronoi decomposition ...