# Find the common factor given a series of numbers

Let $$r$$ be an integer that $$1. We are given a series of $$k$$ integers of the following form:

$$\left[s_1\frac{2^n}{r}\right], \left[s_2\frac{2^n}{r}\right], \ldots, \left[s_k\frac{2^n}{r}\right]$$,

where $$s_i$$ are integers uniformly sampled from $$\{0,1,\ldots, r-1\}$$, and $$\left[\cdot\right]$$ means rounding to the closest integer. Given these $$k$$ numbers and $$n$$, how to extract $$r$$ (as an algorithm)? What is the probability that we can successfully extract $$r$$ using the above algorithm? For the last problem, I guess we can work in the $$n\to\infty$$ limit to simplify things.

• As $n\to\infty$, the probability that $r$ can be extracted will go to $1$, because with high probability the set of distinct values found will be exactly $[0\cdot2^n/r]$, $[1\cdot2^n/r]$, ..., $[(r-1)\cdot2^n/r]$. Commented Oct 16, 2019 at 22:32

If $$r$$ is not much smaller than $$2^n$$ you will need a lot of samples because most numbers are accessible. I found the numbers missing for $$r=11,12,13,14,15$$ when $$2^n=16$$ The numbers unavailable are \begin {align}&11\quad 2,5,8,11,14\\ &12\quad 2,6,10,14\\ &13\quad 3,8,13\\ &14\quad 4,12\\ &15\quad 8\end {align} If $$r$$ is $$13$$ we could not rule out $$15$$ unless we have enough draws to believe we should have gotten $$3$$ or $$13$$. To have $$90\%$$ confidence we would need $$(\frac {13}{15})^k \lt 0.1, k=16$$ If $$r$$ is rather smaller the available values will form a comb and we should be able to get close by noting the spacing of the numbers. Sort the numbers, take the difference between neighboring ones, and look for the greatest close to common divisor. Again, if $$11 \le r \le 15$$ but $$n=10$$ the spacings are about $$93,85,79,73,68$$ Those should not be hard to tell apart with just four or five samples.