TOPICS
Search

Langford's Problem


Arrange copies of the n digits 1, ..., n such that there is one digit between the 1s, two digits between the 2s, etc. For example, the unique (modulo reversal) n=3 solution is 231213, and the unique (again modulo reversal) n=4 solution is 23421314.

Davies (1959) showed that solutions to Langford's problem exist iff n=0,3 (mod 4) (cf. Assarpour et al. 2017), so the next solutions occur for n=7. There are 26 of these, as exhibited by Lloyd (1971). In lexicographically smallest order (i.e., small digits come first), the first few Langford sequences are 231213, 23421314, 14156742352637, 14167345236275, 15146735423627, ... (OEIS A050998).

The number of solutions for n=3, 4, 5, ... (modulo reversal of the digits) are 1, 1, 0, 0, 26, 150, 0, 0, 17792, 108144, ... (OEIS A014552). No formula is known for the number of solutions of a given order n, but Assarpour et al. (2017) computed their counts up to n=28, making n=31 the smallest unknown case (since there are no Langford sequences of order 29 or 30).


Explore with Wolfram|Alpha

References

Assarpour, A.; Bar-Noy, A.; and Liu, O. "Counting Skolem Sequences." 10 Nov 2017. https://arxiv.org/abs/1507.00315.Davies, R. O. "On Langford's Problem. II." Math. Gaz. 43, 253-255, 1959.Gardner, M. Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 70 and 77-78, 1978.Langford, C. D. "Problem." Math. Gaz. 42, 228, 1958.Lloyd, P. R. Correspondence to the Editor. Math. Gaz. 55, 73, 1971.Lorimer, P. "A Method of Constructing Skolem and Langford Sequences." Southeast Asian Bull. Math. 6, 115-119, 1982.Miller, J. "Langford's Problem." http://www.lclark.edu/~miller/langford.html.Miller, J. "Langford's Problem Bibliography." http://www.lclark.edu/~miller/langford/langford-biblio.html.Simpson, J. E. "Langford Sequences: Perfect and Hooked." Disc> Math. 44, 97-104, 1983.Priday, C. J. "On Langford's Problem. I." Math. Gaz. 43, 250-253, 1959.Sloane, N. J. A. Sequences A014552 and A050998 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Langford's Problem

Cite this as:

Weisstein, Eric W. "Langford's Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LangfordsProblem.html

Subject classifications