# Tagged Questions

**5**

votes

**1**answer

260 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

**1**answer

282 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

**1**answer

457 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

**4**answers

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

**1**answer

290 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)$ ...

**1**

vote

**1**answer

811 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

**1**answer

126 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

**1**answer

485 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

**2**answers

705 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

**1**answer

214 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

**2**answers

550 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

**4**answers

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

**2**answers

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

**1**answer

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

**3**answers

1k 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

**1**answer

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 ...