I looked at your
problem 1.a in several stages:
Make a ring keeping
consecutive numbers apart: minimum K=5, {1,3,5,2,4}
Make a ring keeping
even numbers apart, minimum K=7, {1,4,7,2,5,3,6}
Now 6 is in there, a
very fussy neighbor. The next number it's coprime to is 11, so:
1.a
Make a ring with
coprime non-consecutive neighbors, minimum K=11,
{1,6,11,7,4,9,2,5,8,3,10}
The section of this
ring [7,4,9,2] can be reversed so that the ring can be extended by
dropping 12 between 7 & 5: {1,6,11,2,9,4,7,12,5,8,3,10}
This gave me an idea
for 1.b, a systematic way to build larger rings.
Adding an odd number k: try next to the odd numbers starting with k-4
and descending.
Adding an even number k is more complicated:
cut the ring between
the two adjacent odds. If possible insert the even number there
If not possible reflect
a section of the ring to push the problem number(s) somewhere else.
Example: insert 14 into
{1,6,11,2,9,13,4,7,12,5,8,3,10}
9 & 13 are adjacent
odds but 13 is a problem so reflect 13 - 5 to give:
{1,6,11,2,9,5,12,7,4,13,8,3,10} then insert 14 between 9 & 5:
{1,6,11,2,9,14,5,12,7,4,13,8,3,10}
This is the
step-by-step approach, which could be programmed. It's a little tough
to do by hand, especially if the goal is 100. I went as far as 20:
{1,6,11,16,7,12,19,4,17,20,13,18,5,14,9,2,15,8,3,10}
I also tried a modular
approach: take the 12-ring and make copies of it adding 12k to each
member, adding a longer ring to reach a particular number (100). This
doesn't make a perfect ring - lots of neighbors sharing a factor of 5
or 7. I corrected each problem with section reversals. This was the
result:
1.b
{1,6,11,14,23,18,13,10,3,20,
17,24,19,30,7,12,5,8,15,22,
25,4,9,2,21,16,35,26,45,38,
47,42,37,34,27,32,29,36,31,28,
33,40,43,48,55,52,57,50,59,54,
49,46,39,44,41,60,77,80,53,78,
85,82,75,56,51,58,63,68,65,72,
67,64,69,62,95,66,61,70,73,84,
79,76,81,74,99,86,93,100,71,90,
83,98,89,96,91,88,97,92,87,94}
Your Q2 example is
broken, of course - you have 324 and 325 adjacent.
Obviously from my first steps on Q1 there are no solutions for
K=3,4,5,6. For K=7 there will be a multiple of 6, the nearest possible
neighbors are n+/- 5, n+/-7. No solutions for K=7 or 8: the shortest
span this can be achieved in is K=9, starting at 6k-1 up to 6k+7 .
Unfortunately 6k takes 6k+5 and 6k+7 as neighbors, 6k+6 takes 6k-1 and
6k+1 as neighbors, leaving 6k+2,3,4 as the rest of the ring, which
can't be done. So no solutions for K=9 either.
K=10 will still require
two multiples of 6 and adds another even number so this doesn't work
any better. No solutions for K=10.
K=11 we now have the
option of only one multiple of 6 bracketed by 6k-5 and 6k+5. From Q1
we know this can be done. Of course the first and last number must be
odd so we need a gap between primes of at least 14.
The first such feasible
gap is after 317, which gives:
{319,324,329,320,327,322,325,323,326,321,328} for K=11, and, luckily,
{319,324,329,320,327,322,325,318,323,326,321,328} for K=12
My expectation is that
the first large-enough gap will work for the higher-population rings
because there are more options for arrangement. The gap of 22 after
1129, even though tight, works for K=20:
{1147,1130,1143,1148,1135,1146,1141,1136,1131,1142,1149,1132,1137,1144,1139,1134,1145,1138,1133,1140}
Although I haven't
tried them, the gap after 19609 will probably work for 50 and the gap
after 370261 will probably work for 100.
2.
Summarizing:
No solutions for K=3,4,5,6,7,8,9,10
K=11, minimum [319,329]
K=12, minimum [318,329]
K=20, minimum [1130,1149]
Guesses:
K=50, minimum
[19610,19659]
K=100, minimum
[370262,370361]
