# Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every $i=0,1,2,\ldots,n-1$. For example, $f(1)=2$, $f(2)=f(3)=6$, and $f(4)=f(5)=30$. What I know is that, if $g(n)$ is the product of all positive primes less than or equal to $n+1$, then $f(n)\leq g(n)$ (and $k=2$ does the job in getting $g(n)$).

Is it true that $f(2k)=f(2k+1)$ and $f(k)\mid f(k+1)$ for every $k\in\mathbb{N}$? For all integers $n\geq4$, does $f(n)>n^2$ hold? What is the asymptotic behavior of $f(n)$? If anybody proves the assertion that $f=g$, then other questions are trivial.

EDIT 1: According to san's comment below, $f \neq g$. What then is a formula for $f$? If $h(n)$ is the minimum positive integer $k$ such that $k+i$ is not relatively prime to $f(n)$ for every $i=0,1,2,\ldots,n-1$, then do we have a formula for $h$? Also, it seems like, for any $l\in\mathbb{N}$, there exists $n\in\mathbb{N}$ such that $f(n)=f(n+1)=f(n+2)=\ldots=f(n+l-1)$.

EDIT 2: Let $p_i$ be the $i$-th smallest positive prime integer for $i\in\mathbb{N}$. A conjecture by will is that $f\big(\mathsf{A058989}[n]\big)=p_1p_2\cdots p_n$ and $h\big(\mathsf{A058989}[n]\big)=\mathsf{A049300}[n]$ for every $n\in\mathbb{N}$, where the integer sequences $\mathsf{A058989}$ and $\mathsf{A049300}$ are found in http://oeis.org/A058989 and http://oeis.org/A049300, respectively.

• $f(12)=2.3.5.7.11<g(12)$, take $k=114$ or $k=115$.
– san
Jul 18, 2015 at 19:06
• We also have $k\in\{2,2184,9440\}\implies f(14) = f(15) = \ldots = f(20) = f(21) = g(12) = 30030$.
– will
Jul 19, 2015 at 5:12
• @will we have 2201=31.71 so 2184 works only till 17.
– san
Jul 19, 2015 at 14:02
• @san Why is 2 always a factor of $f(n)$?
– will
Jul 19, 2015 at 21:24
• In OEIS it is said that Phil Carmody proved the bound, however, I couldn't find it. You take a positive integer $N$ such that $N\equiv 0\mod p_i$ for $i=1,\dots,r-1$, and $N\equiv 1\mod p_r$ and $N\equiv -1 \mod p_{r+1}$ (which you can by the chinese reminder theorem). Then $N-p_r+1,N-p_r+2,\dots, N,N+1,\dots,N+p_r-2,N+p_r-1$ yields a sequence of $2p_r-1$ consecutive integers which contain some $p_j$ as a factor, for $j=1,\dots,r+1$. You can also take $N$ with $N\equiv -1\mod p_r$ and $N\equiv 1 \mod p_{r+1}$ if that gives you a smaller number.
– san
Jul 20, 2015 at 15:11

Using Batominovski's notation $g(n) :=$ product of all primes less than or equal to $n+1$, we can show that $f(n)|g(n)$:

There exists at least 1 candidate pair, $m$ and $k$, for which each $1 < \gcd(k+i,m),\ \ i=0,\ldots,n-1.$ (Batominovski provides $m = g(n)$ and $k=2$.)

If $p^2|m'$ and $m'$ covers $k,\ldots,k+n-1$, then $m'/p$ also covers $k,\ldots,k+n-1$, and so every $m', k$ reduces to square_free$(m'),k$.

There is a prime $\ p' \le n+1\$ for which candidate $m',k'$ satisfies $\ \gcd(m',p') = 1$, or the candidate reduces to the upper bound candidate, $m=g(n),k=2.$

Suppose we have reduced candidate $m'\not=g(n),k'$ with prime factor $p|m'$, $\ n+1 < p$. Because $n < p,\$ there is (1) $\ j\in\mathbb{Z}[0,n-1]\$ for which $\ 1 < \gcd(\frac{m'}{p},k'+i)\$ for all $i\in\mathbb{Z}[0,n-1]\setminus j.\$ Because $m'\not=g(n)$ there is prime $\ p',\ \ \gcd(p', m') = 1,\ \ p' \le n+1 < p.\$ Because $m'$ isreduced, we can also reduce $k = k'+d\frac{m'}{p}$ (for some positive integer $d$) $\to \gcd(p',k+j) = p'.\$ Then for further reduced $\ m= p'\frac{m'}{p}\$ we have $\ \gcd(m,k+j)=p\$ and $\ 1 < \gcd(m,k+i)\$ for all $i\in\mathbb{Z}[0,n-1].\$ So the factors of every candidate $m'$ reduce to $\le n+1.$

I originally hoped a similar argument would reduce $f(n)$ to a product of the first ? prime numbers, but as yet we only have weak experimental suggestion of such a conjecture.

# Numeric Exploration

Considering each $m|g(n)$ and each $k=2,\ldots,m+1-n$ is the brute force way to find $f(n).\$ My single-threaded, gcc, implementation ran sufficiently efficiently on my Intel(R) Celeron(R) CPU G1840 @ 2.80GHz, for the following test cases, which strongly concur with san's bound: $$\begin{array}{rrrrc} n & \frac{g(n)}{f(n)} & \frac{f(n)}{f(n-1)} & (k) & \frac{s(n)}{f(n)} \\ 1 & 1 & 2 & (2) & 1 \\ 2 & 1 & 3 & (2) & 1 \\ 3 & 1 & 1 & (2) & 1 \\ 4 & 1 & 5 & (2) & 1 \\ 5 & 1 & 1 & (2) & 1 \\ 6 & 1 & 7 & (2) & 1 \\ 7 & 1 & 1 & (2) & 1 \\ 8 & 1 & 1 & (2) & 1 \\ 9 & 1 & 1 & (2) & 1 \\ 10 & 1 & 11 & (2) & 1 \\ 11 & 1 & 1 & (2) & 1 \\ 12 & 13 & 1 & (114) & 1 \\ 13 & 13 & 1 & (114) & 1 \\ 14 & 1 & 13 & (2) & 1 \\ 15 & 1 & 1 & (2) & 1 \\ 16 & 17 & 1 & (2184) & 1 \\ 17 & 17 & 1 & (2184) & 1 \\ 18 & 323 & 1 & (9440) & 1 \\ 19 & 323 & 1 & (9440) & 1 \\ 20 & 323 & 1 & (9440) & 1 \\ 21 & 323 & 1 & (9440) & 1 \\ 22 & 437 & 17 & (39470) & 1 \\ 23 & 437 & 1 & (39470) & 1 \\ 24 & 437 & 1 & (217128) & 1 \\ 25 & 437 & 1 & (217128) & 1 \\ 26 & 23 & 19 & (60044) & 1 \\ 27 & 23 & 1 & (60044) & 1 \end{array}$$

Here we have taken san's bound, provided in an earlier comment, to be the function $\ s(1) = 2,\ \ s(2p_{k-1}) = s(2p_k-1) = g(p_{k+1}-1).\$ This bound is probably an equality until $f(2.19) = f(38) \le g(22) < g(29-1) = s(2.19),\$ (according to the computations below).

Exploring the effectiveness of the primorial, $g(n-1)$, to cover some sequence of consecutive integers, was provided by a much uglier gcc implementation. Upon reflection, iterating thru all plausible combination of bit strings:

101010101010101010...
100100100100100100...
100001000010000100001
1000000100000010000001
10000000000100000000001
...


was probably not an efficient idea, but it does test how fast my 22nm processing core can twiddle bits. $$\begin{array}{rrlc} product & = & \ldots & covers \\ 1!! = g(1) & f(1) = & f(1) & 1 \\ 2!! = g(2) & f(2) = & f(3) & 3 \\ 3!! = g(4) & f(4) = & f(5) & 5 \\ 4!! = g(6) & f(6) = & f(9) & 9 \\ 5!! = g(10) & f(10) = & f(13) & 13 \\ 6!! = g(12) & f(14) = & f(21) & 21 \\ 7!! = g(16) & f(22) = & f(25) & 25 \\ 8!! = g(18) & f(26) = & f(33) & 33 \\ 9!! = g(22) & ? & & 39 \\ 10!! = g(28) & ? & & 45 \\ 11!! = g(30) & ? & & 57 \\ 12!! = g(36) & ? & & 65 \end{array}$$ EDIT: much deeper computations are provided by the OEIS. Because f(n) is monotonically non-decreasing, we can extend $f(26) = f(33) = 2.3.5.7.11.13.17.19,\$ where $f(26)$ was found with brute force and listed our first table.

• With $n!!$ you mean $p_n\#$?
– san
Jul 21, 2015 at 3:13
• @san Yes, I'm referring to the primorial. Sorry for the abuse of notation. I appreciate the constructive proof you provided for your bound. I couldn't quite extend it for the special case of twin primes, which sometimes "fall below" your bound.
– will
Jul 21, 2015 at 3:52
• @will Despite not getting a complete answer, I decided to award you 50 reputations. This is a hard problem, and I think you have made a great progress by showing that $f(n)\mid g(n)$ for all $n\in\mathbb{N}$. Jul 24, 2015 at 19:10
• I just found the relevant paper in neumann.math.unideb.hu/~hajdul/jacobsrev.pdf
– san
Jul 25, 2015 at 1:23
• According to it, the first counterexample is at $p_{24}$, and $f(n)$ is a primorial for every smaller integer.
– san
Jul 25, 2015 at 1:25