# Tagged Questions

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$. ...
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 ...
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$? ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...