8
$\begingroup$

I'm working on a project that uses strings of integers with the property that the numbers 1 though N are each used twice such that each pair of numbers X are X spaces apart.

For example, in the string:

3 1 1 3 5 7 4 8 6 5 4 2 7 2 6 8

The 1's are 1 space apart, the 2's are 2 spaces apart, the 3's are 3 spaces apart, etc.

I believe I've found the number of unique such strings for the following values of N

N : # of strings

2 : 0
3 : 0
4 : 6
5 : 10
6 : 0
7 : 0
8 : 504
9 : 2656
10 : 0
11 : 0
12 : 455936

I was hoping someone could tell me if someone else has studied these patterns? And if so, could point me in the right direction?

$\endgroup$
1
  • 2
    $\begingroup$ For such things the "The On-Line Encyclopedia of Integer Sequences" is really handy, it gives this result for your sequence: oeis.org/A004075 $\endgroup$ Aug 11, 2011 at 18:03

2 Answers 2

11
$\begingroup$

What you are describing are known as Langford sequences. An Internet search will give you http://legacy.lclark.edu/~miller/langford.html and other links.

(According to the Internet Archive that page has moved to http://dialectrix.com/langford.html).

Skolem or near Skolem sequences may also be of interest to you. I have a specialization of this I am studying: see Has anyone seen this version of ring toss (combinatorial object) before? .

Gerhard "Yes, Number Theory Is Involved" Paseman, 2011.07.23

$\endgroup$
2
  • $\begingroup$ Your first link fails to open. Do you happen to have an updated link or does that page not exist anymore? $\endgroup$
    – Martin R
    Feb 20, 2020 at 15:47
  • $\begingroup$ @Martin R, you might be able to recover the page from the internet archive. (Martin Sleziak might come by and provide the link for us.) If you search and find a better page, I invite you to add a new link as part of a new paragraph in between the first two paragraphs of this answer post. Gerhard "Collaborative Post Editing Is Encouraged" Paseman, 2020.02.20. $\endgroup$ Feb 20, 2020 at 18:16
1
$\begingroup$

One of the recent volumes of Knuth's "Art of Computer Programming" (maybe volume 4), has these sequences and some things like a generating function. As far as I know, the asymptotic behaviour is not known.

$\endgroup$
2
  • $\begingroup$ Welcome back to MathOverflow! Gerhard "Apologies For Missing You Before" Paseman, 2011.08.11 $\endgroup$ Aug 11, 2011 at 7:31
  • $\begingroup$ Indeed it's present in Knuth: the very first paragraph of Volume 4A mentions this ("Langford pairs") as an example of combinatorics, and already on page 2 he points out they exist only when when $n = 4m - 1$ or $n = 4m$, and that the number of essentially different pairings $L_n$ "might be roughly of order $(4n/e^3)^{n+1/2}$ when it is nonzero (see exercise 5); and in fact this prediction turns out to be basically correct in all known cases." (His $L_n$ numbers are smaller than the OPs, presumably because of differing definitions of "essentially different".) $\endgroup$
    – shreevatsa
    Oct 16, 2016 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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