# A weird question on measuring the randomness of a sequence of integers via expected behavior of gcd

Say there is a a sequence of integers, $a_k$, that keeps coming toward you, and you have an infinite memory of the sequence, and the only measure you can do on the sequence is the following :

($a_k$,$a_{k_1}$) = $d_{k_1}$, ($a_k$,$a_{k_2}$) = $d_{k_2}$, ($a_k$,$a_{k_3}$) = $d_{k_3}$, ($a_k$,$a_{k_4}$) = $d_{k_4}$, $...$ ($a_k$,$a_{k_n}$) = $d_{k_n}$

1. For each new number that comes in you can select up to $n$ previous numbers, $a_{k_i}$, and for each of these $n$ previous numbers, you can calculate the greatest common divisor of the new number and that previous number.

I conjecture that the gcd of randomly selected pairs of integers is 1 with high unknown probability and then :

2 with probability 0.25
3 with probability 0.11


and so on by terms in the Basel problem series.

My question is :

Using only this metric is it possible to distguish between the following sequences:

• A. A sequence of compressed bytes from a streaming youtube video
• B. The English text of a poem by Neruda, with characters mapped to ASCII codes
• C. Some 'random' noise generated by http://random.org
• D. A geometric progression.
• E. An arithmetic progression.
• F. The prime gaps sequence : 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, etc...

By, using only, I mean you are not even allowed to see the individual elements of the sequence, only to query about the GCD between elements i, and j at any index in the past.

-
Why would you want to do this? – Qiaochu Yuan Feb 28 '13 at 7:44
Such things interest me. I like randomness and all that jazz. How much information is in, or can be extracted from, or what form does the information take in some sequence are a few of my favorite things. – Cris Stringfellow Feb 28 '13 at 7:51
By random I mean as people would commonly consensus agree random to be... Ironically the consensus here is that it is IMPOSSIBLE to define such a thing as a uniformly distributed random integer--hence I am afraid you will have to explain what you mean by that. – Did Mar 22 '13 at 8:32
@Did haha. Good point. Okay, I was hoping that sentence would avoid having to explain what random is. You found me out. – Cris Stringfellow Mar 22 '13 at 11:04
The gcd of a randomly selected pair of integers is $1$ with probability $6/\pi^2$, given a plausible interpretation of "randomly selected pair of integers". – Gerry Myerson Mar 22 '13 at 12:13

A way to approach rigorously the nonexistent notion of an integer chosen uniformly randomly is to consider the probability measures $\mu_s$ on $\mathbb N$ defined for each $s\gt1$ by $\mu_s(n)=1/(n^s\zeta(s))$ for every $n$ in $\mathbb N$. The pointwise limit of $\mu_s$ when $s\to1$ has some nice features, for example, $\mu_s(k\mathbb N)=1/k^s$ hence $\mu_s(k\mathbb N)\to1/k$, for every $k\geqslant1$, a property one might view as desirable. Likewise, being divisible by $n$ and by $m$ are two independent events for every $\mu_s$ when $n\wedge m=1$ since then $(n\mathbb N)\cap(m\mathbb N)=(nm)\mathbb N$. Beware though that there is no limiting probability measure to the family $(\mu_s)$ when $s\to1$ since, for example, $\mu_s(n)\to0$ for every $n$ in $\mathbb N$.
In this setting, consider two random variables $N_s$ and $M_s$ i.i.d. with distribution $m_s$, that is, assume that, for every $n$ and $m$ in $\mathbb N$, $\mathbb P(N_s=n,M_s=m)=1/(n^sm^s\zeta(s)^2)$. Then the gcd $D_s$ of $N_s$ and $M_s$ is such that $[D_s\in k\mathbb N]=[N_s\in k\mathbb N]\cap[M_s\in k\mathbb N]$. This implies that $\mathbb P(D_s\in k\mathbb N)=1/k^{2s}$ for every $k\geqslant1$, in particular, $\mathbb P(D_s\in k\mathbb N)\to1/k^{2}$ when $s\to1$. Furthermore, $[D_s=1]$ is the complement of the union of the independent events $[D_s\in p\mathbb N]$ for every $p$ in the set $\mathfrak P$ of prime numbers. Thus, $$\mathbb P(D_s=1)=\prod_{p\in\mathfrak P}\left(1-\frac1{p^{2s}}\right)\to\prod_{p\in\mathfrak P}\left(1-\frac1{p^2}\right)=\left(\sum_{n\geqslant1}\frac1{n^2}\right)^{-1}=\frac1{\zeta(2)}=\frac6{\pi^2}.$$ (A shortcut to this formula is to note that $D_s$ converges in distribution to a random variable $D$ with distribution $\mu_2$, hence $\mathbb P(D_s=1)\to\mu_2(1)$.)
In this sense, one may ascribe the "probability" $1/k^2$ to the "event" that two random integers independent and "uniformly distributed" are both multiples of some $k\geqslant1$, the "probability" $1/(k^2\zeta(2))=6/(\pi^2k^2)$ to the "event" that the gcd of two random integers independent and "uniformly distributed" is exactly $k\geqslant1$, and, in particular, the "probability" $1/\zeta(2)=6/\pi^2$ to the "event" that two random integers independent and "uniformly distributed" are relatively prime. Likewise, for every $i\geqslant2$, the "probability" that $i$ random integers independent and "uniformly distributed" are relatively prime is $1/\zeta(i)$.
Okay so we have a possible measure for randomness by sampling the GCDs and seeing if the occurrence of co-primality reproduces the distribution $1/\zeta(i)$, for i samples. This is good. Geometric progression will always have a GCD with probability 1. Arithmetic I am unsure of. Prime gaps will have pairwise GCD = 2 with probability 1 in the limit, and then GCD = 4, 6, ... with some discoverable distribution. The compressed bytes will likely obey the above 'random' metric, and the text of Naruda is a case that would have to be closely examined in the ring mod 257. – Cris Stringfellow Mar 22 '13 at 19:14