# Find an integer coprime to sequence sum

Given two positive integers $$a, can we always find an integer $$c\in [a, b]$$ that is coprime to $$\sum_{a\le i\le b} i$$?

• Clearly OP is not good at English, but I find the question to be valid. Note that the question is not asking gcd of consecutive integers. – Yuzhou Gu Oct 15 '18 at 21:03
• Almost all of the time, one of the two largest primes primes works. If there are no primes, try b or b-1 or b-2. Gerhard "The Product Is Too Big" Paseman, 2018.10.15. – Gerhard Paseman Oct 15 '18 at 23:39
• I agree; I don't see that the solution is obvious. – Todd Trimble Oct 15 '18 at 23:48

I believe a large counterexample exists

Actually, no, there is no counterexample. Let's consider several cases:

Case 1: $$b-a$$ is even. Then the progression has odd number $$2X+1$$ of terms from $$A-X$$ to $$A+X$$ and the sum is $$A(2X+1)$$. Now let $$p_1 be all (automatically odd) primes that divide $$2X+1$$ but not $$A$$ (at least one such prime exists because otherwise we can just take $$c=A+1$$). Consider the numbers $$A\pm p_1\dots p_{n-1}$$. Note that they are in the range $$[A-X,A+X]$$ and the only common prime factor they may have with $$A(2X+1)$$ is $$p_n$$. But they cannot be divisible by $$p_n$$ simultaneously, so one of them can be taken as $$c$$.

Case 2: $$b-a$$ is odd, $$b=A+X,a=A-X+1$$, $$X$$ is odd. Then the sum is $$(2A+1)X$$. Again, let $$p_1 be all (automatically odd) primes that divide $$X$$ but not $$2A+1$$. This time just consider the number $$\frac{(2A+1)+ p_1\dots p_{n}}{2}$$.

Case 3: $$b-a$$ is odd, $$b=A+X,a=A-X+1$$, $$X$$ is even. Then the sum is still $$(2A+1)X$$. Again, let $$p_1 be all odd primes that divide $$X$$ but not $$2A+1$$. Consider the numbers $$\frac{(2A+1)\pm p_1\dots p_{n}}{2}$$. One of them is now even and the other one is odd. Also they are both in the range $$[A-X+1,A+X]$$. So, the odd one can be taken as $$c$$.

• Hmm. Is b-a really odd in cases two and three? Gerhard "Gerhard Finds Combination At Odds" Paseman, 2018.10.22. – Gerhard Paseman Oct 22 '18 at 14:33
• @GerhardPaseman $b-a=(A+X)-(A-X+1)=2X-1$, which looks odd to me. – fedja Oct 22 '18 at 17:42
• OK. I wonder why in all three cases, you start with "b-a is even". Otherwise, you found the bit I missed. Gerhard "Likes The Idea A Lot" Paseman, 2018.10.22. – Gerhard Paseman Oct 22 '18 at 18:29
• @GerhardPaseman Because I'm too slow to retype and too stupid to correct or even notice everything that should be corrected in copy-paste pieces :-) Changed now. Thank you! – fedja Oct 22 '18 at 22:16

Edit 2018.10.22 It looks like fedja has it. Briefly, if c is not next to the median, try a larger factor of k away from the median, where the factor is coprime to (twice) the median. If the one less than the median is not c, the larger one can be. Fedja's post has the details. End Edit 2018.10.22.

Let's suppose there is a prime (or two) in the interval $$[a,a+k-1]$$. if $$k$$ is even, we hope the prime does not divide $$(k/2)(2a+k-1)$$. This will be the case if the prime is greater than $$k/2$$ and greater than $$a$$. Invoking Chebyshev on the existence of more than one prime in long intervals, we find such a prime in this case

If k is odd, then the prime needs to be larger than k and not divide $$(a +(k-1)/2)$$, meaning it should not be in the middle. So if k is odd and contains a non central prime, again we have a winner.

So we reduce to the cases of no primes in the interval or one central prime when k is odd. Now we turn to results on Jacobsthal's function to show that for k not too small with respect to the sum (like bigger than log a) there must be a number coprime to the sum in the interval. For k very small, there is unlikely to be a failure (I believe one can find such a number), but I do not have a proof.

I will return with more precise estimates on k, which I believe work for any k larger than (log a )^(loglog a).

Update 2018.10.16

It works for short sequences (one can find a coprime number in the interval), and for sequences where k is large enough with respect to a to contain "enough" primes. However, there is still a middle ground which admits a possibility that every number in the interval shares a prime factor with the sum.

The sum $$S$$ can be written in terms of the first number in the interval, $$a$$, and the length of the interval $$k$$. We have $$S = k(a + (k-1)/2)$$, or $$k$$ times the median of the sequence. For many $$a$$, one can pick a number c next to and different from the median, and c will be coprime to the integer which is either the median or twice the median (in case $$k$$ is even), and if c is also coprime to $$k$$, then we are done.

Before we look at two examples, let us note that for $$a+i$$ in the interval, $$(S,a+i) \gt 1$$ iff $$(k((k-1 - 2i)/2),a+i ) \gt 1$$. Thus we need to check that every number in the interval has (or avoids) a prime factor less than $$k$$. It will now be helpful to look at numbers near the median, and write $$j$$ for $$k$$ when $$k$$ is odd, and $$j$$ for $$k/2$$ when $$k$$ is even.

Example for odd $$k$$: $$3j$$ $$2j$$ $$j$$ $$0$$ $$j$$ $$2j$$ $$3j$$

Example for $$k$$ even: $$5j$$ $$3j$$ $$j$$ $$j$$ $$3j$$ $$5j$$

Let's take $$k=j=9$$. The median of an interval with nine integers will always divide the sum, so let's look next to the median. By the observation above and the handy picture, if a number next to the median is coprime to $$j=9$$, then we have found our coprime integer. Well, the number just below the median might be coprime to 9. If it is not (and must be a multiple of three then), the number just above will be because it is less than three away from the lower candidate. So when $$k=9$$, regardless of $$a$$, we know where to look for a candidate.

Let us pick $$k=18$$, so $$j=9$$. Now the picture looks different. The median is not an integer, but the integers next to the median must both have a factor dividing $$j=9$$ to not be coprime to the sum. Since they are adjacent, they both cannot be multiples of three, and thus we know where to look for $$k=18$$.

One sees immediately the generalization to $$k$$ a prime power (even or odd), or twice an odd prime power, which covers all $$k \lt 12$$: for these small $$k$$ and many others, there is a number coprime and it is one of two numbers next to the median.

What about $$k=12$$? We do not have to look far from the median. If there is a sequence of numbers which are sequentially not coprime to 18 6 6 18, we have some potential for a counterexample. But this involves finding two even numbers and two multiples of three to cover the consecutive interval of integers, and it cannot be done. So no counterexample for $$k=12$$.

What about 15? Look at 45 30 15 0 15 30 45. We can use even numbers to cover 30, a multiple of three to cover one 15, and a multiple of five to cover the other 15 (which we can find with the aid of the Chinese Remainder Theorem). However, one finds that neither 45 can be covered by either a multiple of three or by five if we do this. So with $$k=15$$, we may have to stray far from the median to find a coprime, but again the coprime can be found.

A general proof for $$k$$ having two distinct prime factors can be made, but it gets slightly messy. It may be possible to make an even messier proof for $$k$$ with three distinct prime factors. However, I would instead spend the effort finding a counterexample with $$k$$ having at most twenty distinct prime factors. This leads to admissible sequences in prime number theory and the study of prime gaps. Based on my work (start at MathOverflow question 37679), I believe a large counterexample exists with $$k$$ at most $$e^{100}$$ and $$a$$ at most $$e^{e^{4k}}$$.

End Update 2018.10.16

Gerhard "Needs To Look Up ArXiv" Paseman, 2018.10.15.