Find a block of positive consecutive integers that can be placed around a circle in some order so that any two adjacent numbers always have a common divisor greater than 1.
$\begingroup$
$\endgroup$
17
asked Mar 1, 2019 at 11:37
-
2$\begingroup$ Is there a minimum amount of numbers you need (ie would just 3 do?) $\endgroup$– SmockMar 1, 2019 at 11:53
-
1$\begingroup$ you say consecutive integers but how ti will be consecutive after it reaches back to the first number? $\endgroup$– OrayMar 1, 2019 at 12:00
-
1$\begingroup$ @Flying_whale They have to be put in some other order before you take the gcd's. $\endgroup$– Jaap ScherphuisMar 1, 2019 at 12:24
-
3$\begingroup$ Note also that you can't have any prime numbers in your block. $\endgroup$– Michael SeifertMar 1, 2019 at 21:03
-
4$\begingroup$ I have now been able (thanks to Freddy Barrera of Colombia Aprendiendo) to trace the source: Problem 11019, AMM, June-July, 2003, with solution published in AMM, March 2005. Michael Reid (University of Central Florida) found a solution with just 47 consecutive numbers. Kevin Ford (University of Illinois) and Sergei Konyagin (Moscow State University) proved that such blocks of length N can be found if N is sufficiently large. (How large?) My own solution, involving more primes and a gap of around 80 (?), is lost in one of my notebooks. $\endgroup$– Bernardo Recamán SantosMar 3, 2019 at 14:23
|
Show 12 more comments
4 Answers
$\begingroup$
$\endgroup$
4
I have a solution using 448 consecutive integers.
The integers are centered on a number which I will call $c$, which is:
342807324437386669890245640930601418907623281362205720311372555412334319102271973072975564592463524267335118648596000454654370063914007920553665901460149824033735950242152959820
$c$ is approximately $3.4*10^{176}$.
The integers are the interval [c-224, c+223].
The order around the circle is the following, where I've only listed the offset from $c$:
[0, -169, -13, 13, 169, -221, -17, 17, -187, -121, -11, 11, 121, -209, -19, 19, -171, -81, -27, -9, -3, 3, 9, 27, 81, -219, -73, 73, -146, -64, -32, -16, -8, -4, -2, 2, 4, 8, 16, 32, 64, -218, -109, 109, 218, -216, -214, -107, 107, 214, -212, -53, 53, -159, -213, -71, 71, -142, -206, -103, 103, 206, -202, -101, 101, 202, -200, -125, -25, -5, 5, 25, 125, -215, -43, 43, -129, -207, -23, 23, -184, -194, -97, 97, 194, -192, -201, -67, 67, -134, -176, -166, -83, 83, 166, -164, -41, 41, -205, -185, -37, 37, -111, -189, -49, -7, 7, 49, -217, -31, 31, -155, -175, -203, -29, 29, -145, -160, -162, -183, -61, 61, 122, -152, -144, -177, -59, 59, -118, -136, -153, -147, -161, -133, -119, -112, -116, -106, -104, -143, -117, -141, -47, 47, -94, -100, -135, -123, -99, -96, -98, -92, -115, -95, -85, -80, -88, -86, -82, -76, -74, -72, -93, -87, -75, -69, -63, -91, -77, -56, -68, -62, -58, -54, -57, -51, -48, -52, -65, -55, -50, -46, -44, -40, -45, -39, -33, -24, -38, -34, -28, -35, -21, -15, -20, -26, -22, -14, -10, 6, 10, 12, 14, 20, 15, 21, 24, 22, 26, 28, 34, 36, 33, 39, 45, 35, 40, 38, 44, 46, 48, 50, 52, 54, 51, 57, 63, 56, 58, 62, 68, 72, 69, 75, 55, 65, 80, 74, 76, 82, 86, 88, 77, 91, 98, 92, 94, 96, 87, 93, 99, 108, 100, 85, 95, 115, 135, 111, 117, 104, 116, 118, 124, 128, 1, -126, 157, -124, 139, -139, 130, 112, 119, 133, 147, 123, 129, 141, 144, 134, 142, 146, 148, 152, 158, -79, 79, -158, 173, -173, 164, 160, 145, 155, 175, 161, 184, 162, 153, 159, 171, 177, 183, 189, 196, 172, 176, 143, 187, 209, -220, 178, -89, 89, -178, 181, -172, 188, 200, 185, 205, 215, -195, 201, 207, 213, 216, 219, -222, -224, -1, 222, -210, 223, -208, 221, -182, 203, 217, -196, 193, -193, 204, -198, -190, -188, 191, -191, 192, -181, 186, -186, -180, -174, -170, -165, -156, -154, -148, 163, -150, -140, -138, -132, -130, -122, 149, -128, -120, -108, 131, -110, -105, -102, -90, -84, -78, -70, -66, -60, -42, -36, 127, -199, 199, -223, -12, -30, -18, -149, 113, -113, 114, -6, -163, 151, -151, 211, 30, 18, -131, 167, -167, 150, -157, 136, 42, 60, 66, 70, 78, 84, 90, 105, 110, 106, -127, 102, 126, 132, 138, 140, 154, 156, 168, 165, 174, 180, 182, 190, 195, 198, 208, -211, 210, 212, -197, 197, -204, 220, -168, 179, -179, 170, -114, 137, -137, 120]
The GCDs of consecutive integers, starting from gcd(c, c-169) and continuing around the circle are:
[13, 13, 13, 13, 13, 17, 17, 17, 11, 11, 11, 11, 11, 19, 19, 19, 3, 3, 3, 3, 3, 3, 3, 3, 3, 73, 73, 73, 2, 4, 4, 4, 4, 2, 2, 2, 4, 4, 4, 4, 2, 109, 109, 109, 2, 2, 107, 107, 107, 2, 53, 53, 53, 3, 71, 71, 71, 2, 103, 103, 103, 2, 101, 101, 101, 2, 5, 5, 5, 5, 5, 5, 5, 43, 43, 43, 3, 23, 23, 23, 2, 97, 97, 97, 2, 9, 67, 67, 67, 2, 2, 83, 83, 83, 2, 41, 41, 41, 5, 37, 37, 37, 3, 7, 7, 7, 7, 7, 31, 31, 31, 5, 7, 29, 29, 29, 5, 2, 3, 61, 61, 61, 2, 4, 3, 59, 59, 59, 2, 17, 3, 7, 7, 7, 7, 4, 2, 2, 13, 13, 3, 47, 47, 47, 2, 5, 3, 3, 3, 2, 2, 23, 5, 5, 5, 4, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 7, 7, 7, 4, 2, 2, 2, 3, 3, 3, 4, 13, 5, 5, 2, 2, 4, 5, 3, 3, 3, 2, 2, 2, 7, 7, 3, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 3, 3, 2, 2, 2, 2, 2, 3, 3, 3, 5, 5, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 7, 2, 2, 2, 4, 3, 3, 5, 5, 5, 2, 2, 2, 2, 2, 11, 7, 7, 2, 2, 2, 9, 3, 3, 3, 8, 5, 5, 5, 5, 3, 3, 13, 4, 2, 2, 4, 127, 127, 283, 281, 263, 139, 269, 2, 7, 7, 7, 3, 3, 3, 3, 2, 2, 2, 2, 4, 2, 79, 79, 79, 331, 173, 337, 4, 5, 5, 5, 7, 23, 2, 3, 3, 3, 3, 3, 3, 7, 8, 4, 11, 11, 11, 11, 2, 89, 89, 89, 359, 353, 8, 4, 5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 2, 223, 223, 18, 433, 431, 13, 13, 7, 7, 7, 389, 193, 397, 6, 2, 2, 379, 191, 383, 373, 367, 186, 6, 6, 2, 5, 9, 2, 2, 311, 313, 10, 2, 6, 2, 2, 271, 277, 4, 12, 239, 241, 5, 3, 6, 6, 6, 2, 2, 6, 6, 6, 163, 163, 199, 211, 211, 18, 6, 131, 131, 113, 227, 6, 157, 157, 151, 181, 181, 6, 149, 149, 167, 317, 307, 293, 2, 18, 6, 2, 2, 6, 6, 15, 5, 2, 233, 229, 6, 6, 6, 2, 14, 2, 12, 3, 3, 6, 2, 2, 5, 3, 2, 419, 421, 2, 409, 197, 401, 8, 4, 347, 179, 349, 2, 251, 137, 257, 60]
I wrote the following Python program to verify my solution:
offsets = [0, -169, -13, 13, 169, -221, -17, 17, -187, -121, -11, 11, 121, -209, -19, 19, -171, -81, -27, -9, -3, 3, 9, 27, 81, -219, -73, 73, -146, -64, -32, -16, -8, -4, -2, 2, 4, 8, 16, 32, 64, -218, -109, 109, 218, -216, -214, -107, 107, 214, -212, -53, 53, -159, -213, -71, 71, -142, -206, -103, 103, 206, -202, -101, 101, 202, -200, -125, -25, -5, 5, 25, 125, -215, -43, 43, -129, -207, -23, 23, -184, -194, -97, 97, 194, -192, -201, -67, 67, -134, -176, -166, -83, 83, 166, -164, -41, 41, -205, -185, -37, 37, -111, -189, -49, -7, 7, 49, -217, -31, 31, -155, -175, -203, -29, 29, -145, -160, -162, -183, -61, 61, 122, -152, -144, -177, -59, 59, -118, -136, -153, -147, -161, -133, -119, -112, -116, -106, -104, -143, -117, -141, -47, 47, -94, -100, -135, -123, -99, -96, -98, -92, -115, -95, -85, -80, -88, -86, -82, -76, -74, -72, -93, -87, -75, -69, -63, -91, -77, -56, -68, -62, -58, -54, -57, -51, -48, -52, -65, -55, -50, -46, -44, -40, -45, -39, -33, -24, -38, -34, -28, -35, -21, -15, -20, -26, -22, -14, -10, 6, 10, 12, 14, 20, 15, 21, 24, 22, 26, 28, 34, 36, 33, 39, 45, 35, 40, 38, 44, 46, 48, 50, 52, 54, 51, 57, 63, 56, 58, 62, 68, 72, 69, 75, 55, 65, 80, 74, 76, 82, 86, 88, 77, 91, 98, 92, 94, 96, 87, 93, 99, 108, 100, 85, 95, 115, 135, 111, 117, 104, 116, 118, 124, 128, 1, -126, 157, -124, 139, -139, 130, 112, 119, 133, 147, 123, 129, 141, 144, 134, 142, 146, 148, 152, 158, -79, 79, -158, 173, -173, 164, 160, 145, 155, 175, 161, 184, 162, 153, 159, 171, 177, 183, 189, 196, 172, 176, 143, 187, 209, -220, 178, -89, 89, -178, 181, -172, 188, 200, 185, 205, 215, -195, 201, 207, 213, 216, 219, -222, -224, -1, 222, -210, 223, -208, 221, -182, 203, 217, -196, 193, -193, 204, -198, -190, -188, 191, -191, 192, -181, 186, -186, -180, -174, -170, -165, -156, -154, -148, 163, -150, -140, -138, -132, -130, -122, 149, -128, -120, -108, 131, -110, -105, -102, -90, -84, -78, -70, -66, -60, -42, -36, 127, -199, 199, -223, -12, -30, -18, -149, 113, -113, 114, -6, -163, 151, -151, 211, 30, 18, -131, 167, -167, 150, -157, 136, 42, 60, 66, 70, 78, 84, 90, 105, 110, 106, -127, 102, 126, 132, 138, 140, 154, 156, 168, 165, 174, 180, 182, 190, 195, 198, 208, -211, 210, 212, -197, 197, -204, 220, -168, 179, -179, 170, -114, 137, -137, 120]
center = 342807324437386669890245640930601418907623281362205720311372555412334319102271973072975564592463524267335118648596000454654370063914007920553665901460149824033735950242152959820
import math
out = []
for index in range(len(offsets)):
next_index = (index+1) % len(offsets)
offset, next_offset = offsets[index], offsets[next_index]
g = math.gcd(center + offset, center + next_offset)
assert(g > 1)
out.append(g)
assert(len(out) == len(offsets))
print(out)
My solution was constructed by carefully arranging prime residues to ensure good factor coverage, and then applying the Chinese remainder theorem to generate the numbers. Then, I used a combination of a computer program and a bit of manual fiddling to get the order.
The center number c is chosen to be a multiple of all of the primes up to 109, and most of the primes from 113 to 223. 223 is relevant because it is the largest prime below half the interval length.
c's (partial) prime factorization is more illuminating than its digits:
{2: 2, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1, 23: 1, 29: 1, 31: 1, 37: 1, 41: 1, 43: 1, 47: 1, 53: 1, 59: 1, 61: 1, 67: 1, 71: 1, 73: 1, 79: 1, 83: 1, 89: 1, 97: 1, 101: 1, 103: 1, 107: 1, 109: 1, 113: 1, 137: 1, 139: 1, 151: 1, 167: 1, 173: 1, 179: 1, 191: 1, 193: 1, 197: 1, 199: 1, 252323065033443749571921567431183458773610610273113777423299583649546181648515108993786165033911355322282053: 1}
223 was also chosen very carefully: There are 39 primes in the interval [224, 448] and only 19 primes in the interval [113, 223]. My construction relies on the former number being (approximately) twice the latter number. 223 is the smallest prime for which my construction works. I haven't tried to minimize c, but I think it's within a handful of digits of the smallest it can be with my method.
If people are interested in more details of the construction, please ask in the comments.
-
1
-
1$\begingroup$ @DrXorile The basic idea was to start by making the center the product of a bunch of small primes. That way, all I had left to do was to fill in the gaps in the positions according to the medium sized primes - the ones between 113 and 223. Unfortunately, there were slightly too few medium and large primes to fill things in directly. However, I found I could place some medium sized primes so that they would cover multiple gaps left by the small primes, while also having the third multiple in the sequence not be the center integer, which was getting overloaded. $\endgroup$– isaacgMar 3, 2019 at 6:22
-
1$\begingroup$ @DrXorile I did this with 181, 163, 149, 131, 157 and 211. That freed up enough prime factors that I could fill in all of the gaps and ensure that every number had two neighbors that weren't already committed. Actually, I had 2 extra factors: I never used 439 and 449, which would have made the sequence even loner. $\endgroup$– isaacgMar 3, 2019 at 6:24
-
$\begingroup$
$\endgroup$
18
This is the answer:
It cannot be done.
Here's a tweak to the approach, but I haven't been able to finish it. It might not be a valid approach at all, but I thought I'd put it out there for now.
Definition 1: $p_k$ is the $k$th prime, ie the $k$th element in $[2,3,5,7,11,\ldots]$, indexed from 1, so $p_1=2$
Definition 2: The degree of a number in a sequence is the sum of the number of other numbers in that sequence that share a common prime factor.
E.g.
\begin{array}{rccccccr} \mathrm{Sequence} & p_1 & p_2 & p_3 & p_4 & p_5 & p_6 & \mathrm{degree}\\ 2184 & 2 & 3 & & 7 & & 13 & 16\\ 2185 & & & 5 & & & & 3\\ 2186 & 2 & & & & & & 8\\ 2187 & & 3 & & & & & 5\\ 2188 & 2 & & & & & & 8\\ 2189 & & & & & 11 & & 1\\ 2190 & 2 & 3 & 5 & & & & 16\\ 2191 & & & & 7 & & & 2\\ 2192 & 2 & & & & & & 8\\ 2193 & & 3 & & & & & 5\\ 2194 & 2 & & & & & & 8\\ 2195 & & & 5 & & & & 3\\ 2196 & 2 & 3 & & & & & 13\\ 2197 & & & & & & 13 & 1\\ 2198 & 2 & & & 7 & & & 10\\ 2199 & & 3 & & & & & 5\\ 2200 & 2 & & 5 & & 11 & & 12\\ & & & & & & & \\ \mathrm{Neighbors} & 8 & 5 & 3 & 2 & 1 & 1 & \end{array}
Theorem: Any sequence of consecutive numbers has at least two numbers with degree of at most 1.
Proof: If a sequence has length $N$ we need only look at primes that are less than $N$, as larger primes will not contribute to the degree. We will prove this by induction on $k$ in $p_k$.
Step 1: For $k=1$, we will need $N\geq3$, and at least one of those numbers will have degree 0. If it's only 1 then $N=3$, and the remaining two numbers have degree 1.
For $k=2$, we will need $N\geq4$. Then any sequence will contain four consecutive numbers, one of which will not be divisible by either 2 or 3. That number would have degree 0. There will also be at least 1 number that is only divisible by 3. Either there are at least three 3s, but then there are at least 2 numbers with degree 0, or there are two 3s but then one of those threes will have degree 1.
Step 2: Assume that this is true for all $p_k$ where $k\leq n-1$.
Step 3: We now want to show this for $p_n$.
Consider a sequence of consecutive numbers with $N\geq p_n+1$ numbers in it. Suppose the degree of all the numbers is at least 2.
Case 1:
Only 1 number in the sequence is a multiple of $p_n$. Then $p_n$ does not contribute to the degree of any element and we are reduced to $p_{n-1}$ and so it is true by Step 2.
Case 2:
This is where is falls apart currently. But it feels close.
Alternate approach. Using the degrees seems helpful. You can easily search through all $N$ and calculate the degree contributions from all $p_k<N$. In the example above (from this related question), you would have $N=17$, and cycle through all possible shiftings of the various primes (in this case the offsets are 0,0,1,0,5,0).
Doing this and looking for all degrees greater than or equal to 1 very quickly finds $N=17$ and $(0,0,1,0,5,0)$. One could easily then use the Chinese Remainder Theorem to figure out that 2184 is where the sequence starts.
In this problem, we will need all the degrees to be greater than or equal to 2. The nice thing is that this an exhaustive search for $N$ (although it doesn't guarantee a solution). Using this approach I've established that there are definitely no solutions for $N\leq32$.
Here's the code if anyone wants to jump ahead and do some searches for higher $N$:
import numpy as np
i=2
while True:
primes=tempprimes[:i]
for n in range(primes[-1]+1,tempprimes[i]+1):
arrays=[]
for p in primes[-1::-1]:
arrays.append(range(min([p,n-p])))
print(n,primes[-1::-1])
cover=False
for cp in itertools.product(*arrays):
covered = np.zeros(n,dtype=np.int64)
for s,p in zip(cp,primes[-1::-1]):
covered[s::p]+=(n-1-s)//p
#print(cp,covered)
if np.all(covered>=2):
print(cp,covered)
cover=True
print("*"*10)
if cover: break
if cover: break
i+=1
answered Mar 1, 2019 at 22:16
-
1$\begingroup$ Unless my brute-force calculations are wrong, I can go further: I can replace >=62 with >=1300. [EDITED to add:] When I wrote this, the answer above said "any solution must be long -- at least N>=62". It doesn't say that any more. $\endgroup$– Gareth McCaughan ♦Mar 1, 2019 at 23:22
-
2$\begingroup$ The solution of the related puzzle puzzling.stackexchange.com/questions/49336/… provides an example of 17 consecutive numbers that are all factors of some prime (2, 3, 5, 7, 11, 13) less than or equal to 13. That solution only works for a line, not a circle. But does it contradict your more general statement? I must be missing something. $\endgroup$– ppgdevMar 2, 2019 at 4:36
-
1$\begingroup$ I think your statement "Then we need only consider $N=p_k+1$." is problematic. $\endgroup$– ppgdevMar 2, 2019 at 5:26
-
6$\begingroup$ There is a subtle assumption in the induction step that assumes that in order to cover the $N-2$ numbers between the two multiples of the largest shared prime $p_k$ you must use $p_{k-1}$ twice also. In the answer of the linked question, $N$ is slightly larger than $p_k+1$, and only one of the $p_{k-1}$-multiples lies between them, the other lies outside (the two multiples of $13$ straddle only one of the multiples of $11$). $\endgroup$ Mar 2, 2019 at 7:02
-
2$\begingroup$ @DrXorile It's definitely not impossible. See my answer. $\endgroup$– isaacgMar 3, 2019 at 4:41
$\begingroup$
$\endgroup$
Very very partial answer
First of all, note that no prime number can occur around the circle. Suppose we have a configuration in which there is a prime number, and consider the biggest one; call it $p$. It is adjacent to two other numbers, and therefore has a nontrivial common factor with each, which means they're both multiples of $p$. So our range of numbers includes $p$ and (at least) $2p$. But there's a famous theorem ("Bertrand's postulate") that for $n>2$ there is always a prime between $n$ and $2n$ -- and a prime between $p$ and $2p$ is a prime larger than $p$, contrary to our assumption that $p$ was the biggest.
Hence we only need to look "between primes" -- and most gaps between primes are pretty short. The shortest gaps can be excluded by a modest amount of brute-force search. Specifically, if we have a block of $n$ consecutive integers then the only "relevant" primes are those $<n$ (because if two integers $<n$ have a common factor, that factor also divides their difference, which is $<n$), so it suffices to check a range of starting points that forms a complete set of residues modulo the product of the primes $<n$. Even a stupidly written program in a slow language can do this as far as $n=18$, so we need only look at gaps larger than that. And now a bit of brute force shows that up to 6000000 (and counting...) there is no block of consecutive integers "between primes" in which each has common factors with at least two of the others.
So if there is a solution to this then all its numbers are bigger than 6,000,000.
[EDITED to add:] I've left my brute-force program running, and so far that bound has increased from 6M to 100M. (The program is pretty stupid. I'm sure it could be sped up a lot.)
I haven't looked very hard for a proof that there is no solution (especially as OP phrased the question in a way that implies there is a solution).
answered Mar 2, 2019 at 22:23
$\begingroup$
$\endgroup$
Here is a way to get larger and larger bounds on the size the circle has to be. Let $L$ denote the smallest length a solution can have. It is based on the Chinese Remainder Theorem (CRT) and the fact that
Numbers with a large lowest prime factor are our enemies, since their possible neighbours are sparse.
First note that
$L>3$, since two consecutive integers are always coprime.
Now
We know $L\geq 4$, and by the CRT applied to $2\times 3=6$, any sequence of $4$ or more consecutive integers contains an integer coprime to $6$, hence whose least prime factor is at least $5$. Now this integer needs two friends, and the shortest way to achieve two friends is by having factors $5$ and $7$, which gives $L\geq 8$: $$\stackrel{5, 7}{\bullet}\bullet\,\bullet\,\bullet\,\,\bullet\stackrel{5}{\bullet}\bullet\stackrel{7}{\bullet}$$
One step further
We know $L\geq 8$, and by the CRT applied to $2\times 3\times 5=30$, any sequence of $6$ or more consecutive integers contains an integer coprime to $30$, hence whose least prime factor is at least $7$. The shortest way to achieve two friends for that guy is by having factors $7$ and $11$, which gives $L\geq 12$: $$\stackrel{7, 11}{\bullet}\bullet\,\bullet\,\bullet\,\bullet\,\bullet\,\bullet\stackrel{7}{\bullet}\bullet\,\bullet\,\bullet\,\stackrel{11}{\bullet}$$
Again
We know $L\geq 12$, and by the CRT applied to $2\times 3\times 5\times 7=210$, any sequence of $10$ or more consecutive integers contains an integer whose least prime factor is at least $11$. The shortest way to achieve two friends for that guy is by having factors $11$ and $13$, which gives $L\geq 14$. Etc.
This method can be implemented but the result cannot be predicted by a clever argument, because if you could predict the behaviour of the CRT tables that would be a huge hint at the behaviour of the primes.
