7
$\begingroup$

A certain number of the 5000 members of the World Arithmetical Society (each of which has a different membership number between 1 and 5000) got together to discuss a problem. Much to their surprise, when they were lining up for lunch they discovered that their membership numbers could be arranged to form a sequence of consecutive whole numbers and, moreover, that none of them was standing next to someone whose number was relatively prime to his own. (Remember that two numbers, such as 25 and 34, are relatively prime if they have no common divisor greater than 1.)

How many were the members of the Society who met and what were their membership numbers?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
7
$\begingroup$

Here is a solution. I'm afraid I used a computer to help find it. Some explanation is below.

2197 13 2184 2 3 7 13 2191 7 2198 2 7 2194 2 2186 2 2188 2 2192 2 2196 2 3 2187 3 2193 3 2199 3 2190 2 3 5 2185 5 2195 5 2200 2 5 11 2189 11

This uses

17 numbers, from 2184 to 2200. Each row shows which "small" prime numbers divide the number on that row, and you can see that each pair of consecutive rows has a prime number in common.

To find this without requiring too much human brute force or computer cleverness, I

defined a set of numbers to be "plausible" if each shares a common factor with at least one other, and no more than two share a common factor with only one other,

a condition it's easy to check by computer, and then

conducted an exhaustive search for the shortest plausible string of consecutive numbers below 5000.

This might have yielded a non-solution, in which case I'd have continued the search. That would have happened if, e.g.,

you could arrange the numbers into a "chain" and some "rings", but there was no way to connect these together into a single "chain".

Is this solution unique?

This set of numbers is unique. (An earlier version of this answer had a sketch of how to prove it, with a remark to the effect that the details are fiddly enough to put me off doing it properly. Peter Taylor, in comments below, correctly observes that the details are much less fiddly than I'd thought.) Suppose you have a "working" set of numbers, and it includes a prime number $p$. This must be adjacent to at least one other number, which must therefore be a multiple of $p$. Therefore your range must extend at least as far as $2p$. But in the range $(p,2p)$ there is at least one prime number, by Bertrand's postulate. So if you have a prime number then you have a larger prime number; hence, any solution must include no prime numbers. The longest gap between prime numbers below 5000 has length 33; so brute force up to size 33 suffices. I've run my program further than that and found no viable sets of numbers other than the one above.

But

the exact sequence is not unique; e.g., we could swap 2187 and 2193.

Improve this answer
$\endgroup$
3
  • $\begingroup$ There are no fiddly details. As you state, if the range includes a prime p then it must also include 2p to prevent that member from being isolated; by Bertrand's postulate there is another prime q in that range, which is isolated, and by induction the range must extend beyond 5000. Ergo it suffices to consider ranges which contain no prime; the longest such has 33 elements, so a brute force that far is sufficient. $\endgroup$
    – Peter Taylor
    Feb 22, 2017 at 15:52
  • $\begingroup$ (For what it's worth, by hand I had got up to eliminating ranges of 12 elements by proving that at least one odd number must be isolated, but then it got too fiddly. It's definitely worth using a computer). $\endgroup$
    – Peter Taylor
    Feb 22, 2017 at 15:56
  • $\begingroup$ D'oh, of course you're right about the fiddly details not actually being fiddly. For whatever reason I'd got it into my head that an "out-of-range" prime would have one neighbour, not zero. I got up to about 10 by hand before deciding I'd rather do it by computer. I wouldn't be astonished to find that there's a tolerable way of getting to the right answer by hand, though the fact that there's only one seems like good reason to suspect there isn't. $\endgroup$
    – Gareth McCaughan ♦
    Feb 22, 2017 at 16:10
3
$\begingroup$

I confirm that Gareth's answer is unique with a simpler computer approach.

As Gareth points out, the range of membership numbers cannot include any primes. So the first step is to split into prime-free ranges. But then each range which contains a number coprime to the other numbers in that range can be split around that number. When we perform this operation recursively with all prime-free ranges up to 5000, we are left with one candidate range: 2184 to 2200 (both inclusive). Gareth's answer provides an ordering of this range which meets the criterion.

A computer program which performs this test can be run online. It takes about a second.

Extending the search to 30030 yields one other candidate range: 27828 to 27846 (inclusive). But 27829 = 17 * 1637 and 27833 = 13 * 2141 must both be next to 27846 = 2 * 3 * 3 * 7 * 13 * 17. It turns out, however, that the range 27830 to 27846 works.

27833 =                                13* 2141
27846 = 2*          3*3*    7*         13* 17
27839 =                     7*             41*97
27832 = 2*2*2*              7*7*           71
27836 = 2*2*                               6959
27838 = 2*                                 31*449
27842 = 2*                                 13921
27844 = 2*2*                               6961
27834 = 2*          3*                     4639
27831 =             3*                     9277
27837 =             3*3*3*                 1031
27843 =             3*                     9281
27840 = 2*2*2*2*2*2*3*    5*               29
27835 =                   5*               19*293
27845 =                   5*               5569
27830 = 2*                5*     11*11*    23
27841 =                          11*       2531

Adding any multiple of 2*3*5*7*11*13 = 30030 to this or to the <5000 solution gives another solution, because adding a multiple of all those primes to each number guarantees that each derived number will be divisible by the same subset of those primes. And the search up to 30030 guarantees to find any solution which relies only on those primes, which means that any other solution must involve a prime at least 17, and hence must contain at least 18 members.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Having split at primes and then at coprime-to-other-things numbers, you still have the possibility that a proper subrange of one of the remaining ranges might be usable. Incidentally, I don't think what you describe is any simpler than what I did, though I don't propose to try to translate my Python code into CJam to compare :-). $\endgroup$
    – Gareth McCaughan ♦
    Feb 22, 2017 at 17:09
  • $\begingroup$ @GarethMcCaughan, I obviously haven't explained it well enough. Having split on coprime-to-other-things recursively there is only one remaining range, and since the whole range is usable I didn't bother with proper subranges. As it happens, 87890 to 87906 is a proper subrange of the surviving range 87890 to 87910, which isn't usable as a whole. $\endgroup$
    – Peter Taylor
    Feb 22, 2017 at 17:19
  • $\begingroup$ As to being simpler: your definition of "plausible" is "if each shares a common factor with at least one other, and no more than two share a common factor with only one other". Mine is "if each shares a common factor with at least one other". $\endgroup$
    – Peter Taylor
    Feb 22, 2017 at 17:22
  • $\begingroup$ I hadn't realised that you end up with only one range left on doing that. That's amusing. I agree that your plausibility criterion is simpler than mine, but I think your search technique is more complicated than mine (but more effective since it lets you eliminate almost all candidates in reasonable time). $\endgroup$
    – Gareth McCaughan ♦
    Feb 22, 2017 at 17:24
-1
$\begingroup$

As the question stands now... This answer could be acceptable I think

3 members, ID 1,2 and 3

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ But 1 and 2 are relatively prime, as are 2 and 3, no? $\endgroup$
    – Rubio ♦
    Feb 22, 2017 at 2:20
  • $\begingroup$ @Rubio I was starting to think about that to now after reading the question again, We could debate that 1 and 2 are not, but 2 and 3 are.... i think. That whole relatively prime thing is a new concept to me. Not sure I get it yet..... If no neighbor is relatively prime, it means that all of them share a common divisor? But isn't it impossible for 2 consecutive numbers to have a common divisor? $\endgroup$
    – stack reader
    Feb 22, 2017 at 2:23
  • $\begingroup$ I have clarified this issue. $\endgroup$
    – Bernardo Recamán Santos
    Feb 22, 2017 at 2:30
  • $\begingroup$ Well, I have an answer if there are 120,000 number theorists... $\endgroup$
    – greenturtle3141
    Feb 22, 2017 at 3:45
  • $\begingroup$ @greenturtle3141 used a program? I can't find a solution without a program. $\endgroup$
    – stack reader
    Feb 22, 2017 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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