7
$\begingroup$

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.

$\endgroup$
15
  • 1
    $\begingroup$ $f(12)=2.3.5.7.11<g(12)$, take $k=114$ or $k=115$. $\endgroup$
    – san
    Jul 18, 2015 at 19:06
  • 2
    $\begingroup$ We also have $k\in\{2,2184,9440\}\implies f(14) = f(15) = \ldots = f(20) = f(21) = g(12) = 30030$. $\endgroup$
    – will
    Jul 19, 2015 at 5:12
  • 1
    $\begingroup$ @will we have 2201=31.71 so 2184 works only till 17. $\endgroup$
    – san
    Jul 19, 2015 at 14:02
  • 1
    $\begingroup$ @san Why is 2 always a factor of $f(n)$? $\endgroup$
    – will
    Jul 19, 2015 at 21:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – san
    Jul 20, 2015 at 15:11

1 Answer 1

Reset to default
3
+50
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ With $n!!$ you mean $p_n\#$? $\endgroup$
    – san
    Jul 21, 2015 at 3:13
  • $\begingroup$ @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. $\endgroup$
    – will
    Jul 21, 2015 at 3:52
  • $\begingroup$ @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}$. $\endgroup$
    – Batominovski
    Jul 24, 2015 at 19:10
  • 2
    $\begingroup$ I just found the relevant paper in neumann.math.unideb.hu/~hajdul/jacobsrev.pdf $\endgroup$
    – san
    Jul 25, 2015 at 1:23
  • 1
    $\begingroup$ According to it, the first counterexample is at $p_{24}$, and $f(n)$ is a primorial for every smaller integer. $\endgroup$
    – san
    Jul 25, 2015 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.