5
votes
1answer
270 views

Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...
5
votes
1answer
285 views

Subsets of all Diophantine's sets

I have asked this question on math.stackexchange already: http://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable ...
8
votes
1answer
502 views

How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$? ...
20
votes
4answers
1k views

Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an information-greedy secret service which has backdoors to all internet nodes throughout the world which permit him to observe all exchanged data ...
2
votes
1answer
296 views

Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n $\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
2
votes
1answer
882 views

The Jones-Sato-Wada-Wiens polynomial for prime numbers and differential calculus?

After works of Davis, Matijasevic, Putman and Robinson between 1960 and 1970, we know that every recursively enumerable set of numbers can be represented by a polynomial. In particular, it's the case ...
3
votes
1answer
137 views

Question about the elementary divisors of a special matrix

I have the following question: Is there a closed formula for the elementary divisors of the Matrix $M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
1
vote
1answer
513 views

Collatz conjecture— finite state machine transducer construction, origination?

wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
3
votes
2answers
793 views

How to draw Archimedean-Galileo spiral?

It is known that some plane curves can be drawn with a tool. For instance, I heard at a web site that Archimedes created his spiral in the third century B.C. by fooling around with a compass and ...
1
vote
1answer
217 views

Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without “being able to know” one of the discrete logs involved (formal definition given in question)?

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
15
votes
2answers
573 views

Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem: Find a decision procedure for determining if an arbitrary semilinear set is ...
1
vote
4answers
1k views

What is the name of the function f(x,y) = ((x-1) mod y)+1 ?

Does the function $f(x,y) = ((x-1) \mod y)+1$ have an existing name? f(1,5) = 1 f(2,5) = 2 ...
2
votes
2answers
747 views

Why is every finite set Diophantine?

I understand that every finite set is recursively enumerable, as I see that one could just encode each element of some finite set on a Turing Machines tape, and then have the machine check each member ...
2
votes
1answer
1k views

Conditions that allow unique solutions for Linear Diophantine equations

(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for ...
2
votes
3answers
2k views

Counting lattice points on an n-simplex

Imagine an n-simplex, the solution set for the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where: $a_1$ through $a_n$ are positive bounded integers $x_1$ through $x_n$ are ...
1
vote
1answer
188 views

Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?

Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are ...