Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

770 Views Asked by At

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.

1

There are 1 best solutions below

9
On

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.