Problem of the Week 989

Neighbors With Something in Common

Find a set of consecutive positive integers that can be rearranged into a row so that each two adjacent numbers have a common factor greater than 1. For example, it cannot be done with x, x + 1, and x + 2 because x + 1 has no factor in common with x or x + 2.

The problem becomes a little easier if you know how many consecutive positive integers there will be. If you would like that hint, you will have to ask me. A much harder variation of this problem (to which I do not know the solution), appeared as Problem 11019 in the June-July 2003 American Mathematical Monthly, and that was to do it in a circle: find consecutive positive integers that can be arranged in a circle so that each has a common divisor with both of its neighbors.

Both problems are due to Bernardo Recamán Santos (Bogotá, Colombia)

© Copyright 2003 Stan Wagon. Reproduced with permission.

18 September 2003