In this document, the "yield" of a sequence of numbers will be defined as the maximum least common multiple of a pair of consecutive numbers in the sequence.

Sequence A064764 in the On-Line Encyclopedia of Integer Sequences is defined so that a(n) is the minimum yield of a permutation of {1, ..., n}. The purpose of this document is to prove the values of a(11) through a(70).

First, we exhibit permutations that yield the minimums:

a(11) = 18: 11 1 10 5 3 9 6 4 8 2 7
a(12) = 18: 11 1 10 5 3 9 6 12 4 8 2 7
a(13) = 24: 13 1 11 2 7 3 5 10 4 8 12 6 9
a(14) = 24: 13 1 11 2 14 7 3 5 10 4 8 12 6 9
a(15) = 24: 13 1 11 2 14 7 3 15 5 10 4 8 12 6 9
a(16) = 24: 13 1 11 2 14 7 3 15 5 10 4 16 8 12 6 9
a(17) = 35: 17 1 13 2 11 3 9 6 12 8 16 4 14 7 5 10 15
a(18) = 35: 17 1 13 2 11 3 9 18 6 12 8 16 4 14 7 5 10 15
a(19) = 44: 19 1 17 2 13 3 11 4 16 8 10 15 5 7 14 6 9 12 18
a(20) = 44: 19 1 17 2 13 3 11 4 16 8 20 10 15 5 7 14 6 9 12 18
a(21) = 44: 19 1 17 2 13 3 11 4 16 8 20 10 15 5 7 21 14 6 9 12 18
a(22) = 44: 19 1 17 2 13 3 11 22 4 16 8 20 10 15 5 7 21 14 6 9 12 18
a(23) = 55: 23 1 19 2 17 3 13 4 22 11 5 10 20 8 16 12 18 9 15 6 14 21 7
a(24) = 55: 23 1 19 2 17 3 13 4 22 11 5 10 20 8 24 16 12 18 9 15 6 14 21 7
a(25) = 55: 23 1 19 2 17 3 13 4 22 11 5 25 10 20 8 24 16 12 18 9 15 6 14 21 7
a(26) = 55: 23 1 19 2 17 3 13 26 4 22 11 5 25 10 20 8 24 16 12 18 9 15 6 14 21 7
a(27) = 55: 23 1 19 2 17 3 13 26 4 22 11 5 25 10 20 8 24 16 12 18 27 9 15 6 14 21 7
a(28) = 55: 23 1 19 2 17 3 13 26 4 22 11 5 25 10 20 8 24 16 12 18 27 9 15 6 14 21 7 28
a(29) = 68: 29 1 23 2 19 3 17 4 26 13 5 11 22 6 27 18 9 21 14 28 7 8 24 16 12 15 20 10 25
a(30) = 68: 29 1 23 2 19 3 17 4 26 13 5 11 22 6 27 18 9 21 14 28 7 8 24 16 12 15 20 30 10 25
a(31) = 85: 31 1 29 2 23 3 19 4 17 5 13 26 6 22 11 7 28 21 14 10 25 15 30 12 20 8 16 24 18 27 9
a(32) = 85: 31 1 29 2 23 3 19 4 17 5 13 26 6 22 11 7 28 21 14 10 25 15 30 12 20 8 32 16 24 18 27 9
a(33) = 85: 31 1 29 2 23 3 19 4 17 5 13 26 6 22 33 11 7 28 21 14 10 25 15 30 12 20 8 32 16 24 18 27 9
a(34) = 85: 31 1 29 2 23 3 19 4 34 17 5 13 26 6 22 33 11 7 28 21 14 10 25 15 30 12 20 8 32 16 24 18 27 9
a(35) = 85: 31 1 29 2 23 3 19 4 34 17 5 13 26 6 22 33 11 7 28 21 14 35 10 25 15 30 12 20 8 32 16 24 18 27 9
a(36) = 85: 31 1 29 2 23 3 19 4 34 17 5 13 26 6 22 33 11 7 28 21 14 35 10 25 15 30 12 20 8 32 16 24 18 27 9 36
a(37) = 102: 37 1 31 2 29 3 23 4 19 5 17 34 6 26 13 7 35 14 21 28 12 32 24 36 18 27 9 11 33 22 8 16 20 30 15 25 10
a(38) = 102: 37 1 31 2 29 3 23 4 38 19 5 17 34 6 26 13 7 35 14 21 28 12 32 24 36 18 27 9 11 33 22 8 16 20 30 15 25 10
a(39) = 102: 37 1 31 2 29 3 23 4 38 19 5 17 34 6 26 39 13 7 35 14 21 28 12 32 24 36 18 27 9 11 33 22 8 16 20 30 15 25 10
a(40) = 102: 37 1 31 2 29 3 23 4 38 19 5 17 34 6 26 39 13 7 35 14 21 28 12 32 24 36 18 27 9 11 33 22 8 16 40 20 30 15 25 10
a(41) = 119: 41 1 37 2 31 3 29 4 23 5 19 38 6 34 17 7 13 39 26 8 11 33 22 10 25 15 30 9 36 27 18 24 32 12 28 21 35 14 16 40 20
a(42) = 119: 41 1 37 2 31 3 29 4 23 5 19 38 6 34 17 7 13 39 26 8 11 33 22 10 25 15 30 9 36 27 18 24 32 12 28 42 21 35 14 16 40 20
a(43) = 145: 43 1 41 2 37 3 31 4 29 5 23 6 38 19 7 17 34 8 13 26 39 9 11 33 22 10 25 15 30 40 20 12 36 27 18 24 32 16 28 42 21 35 14
a(44) = 145: 43 1 41 2 37 3 31 4 29 5 23 6 38 19 7 17 34 8 13 26 39 9 11 44 33 22 10 25 15 30 40 20 12 36 27 18 24 32 16 28 42 21 35 14
a(45) = 145: 43 1 41 2 37 3 31 4 29 5 23 6 38 19 7 17 34 8 13 26 39 9 11 44 33 22 10 25 15 45 30 40 20 12 36 27 18 24 32 16 28 42 21 35 14
a(46) = 145: 43 1 41 2 37 3 31 4 29 5 23 46 6 38 19 7 17 34 8 13 26 39 9 11 44 33 22 10 25 15 45 30 40 20 12 36 27 18 24 32 16 28 42 21 35 14
a(47) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 9 39 26 13 11 33 44 22 10 25 15 45 30 40 20 12 36 27 18 24 32 16 28 42 21 35 14
a(48) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 9 39 26 13 11 33 44 22 10 25 15 45 30 40 20 12 36 27 18 24 48 32 16 28 42 21 35 14
a(49) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 9 39 26 13 11 33 44 22 10 25 15 45 30 40 20 12 36 27 18 24 48 32 16 28 42 21 35 14 49
a(50) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 9 39 26 13 11 33 44 22 10 50 25 15 45 30 40 20 12 36 27 18 24 48 32 16 28 42 21 35 14 49
a(51) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 51 9 39 26 13 11 33 44 22 10 50 25 15 45 30 40 20 12 36 27 18 24 48 32 16 28 42 21 35 14 49
a(52) = 174: 47 1 43 2 41 3 37 4 31 5 29 6 46 23 7 19 38 8 34 17 51 9 39 26 52 13 11 33 44 22 10 50 25 15 45 30 40 20 12 36 27 18 24 48 32 16 28 42 21 35 14 49
a(53) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 29 7 23 46 8 38 19 9 51 34 17 11 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 18 24 48 32 16 28 42 21 35 14 49
a(54) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 29 7 23 46 8 38 19 9 51 34 17 11 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 42 21 35 14 49
a(55) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 29 7 23 46 8 38 19 9 51 34 17 11 55 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 42 21 35 14 49
a(56) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 29 7 23 46 8 38 19 9 51 34 17 11 55 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 56 42 21 35 14 49
a(57) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 29 7 23 46 8 38 19 57 9 51 34 17 11 55 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 56 42 21 35 14 49
a(58) = 203: 53 1 47 2 43 3 41 4 37 5 31 6 58 29 7 23 46 8 38 19 57 9 51 34 17 11 55 33 44 22 12 26 39 52 13 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 56 42 21 35 14 49
a(59) = 232: 59 1 53 2 47 3 43 4 41 5 37 6 31 7 29 58 8 46 23 9 57 38 19 11 55 33 44 22 12 51 34 17 13 52 39 26 10 50 25 15 45 30 40 20 36 27 54 18 24 48 32 16 28 56 42 21 35 14 49
a(60) = 232: 59 1 53 2 47 3 43 4 41 5 37 6 31 7 29 58 8 46 23 9 57 38 19 11 55 33 44 22 12 51 34 17 13 52 39 26 10 50 25 15 45 30 60 40 20 36 27 54 18 24 48 32 16 28 56 42 21 35 14 49
a(61) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 8 58 29 9 23 46 10 38 57 19 13 52 39 26 12 51 34 17 11 55 44 33 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 16 28 56 42 21 35 49
a(62) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 62 8 58 29 9 23 46 10 38 57 19 13 52 39 26 12 51 34 17 11 55 44 33 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 16 28 56 42 21 35 49
a(63) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 62 8 58 29 9 23 46 10 38 57 19 13 52 39 26 12 51 34 17 11 55 44 33 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 16 28 56 42 63 21 35 49
a(64) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 62 8 58 29 9 23 46 10 38 57 19 13 52 39 26 12 51 34 17 11 55 44 33 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49
a(65) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 62 8 58 29 9 23 46 10 38 57 19 13 52 39 65 26 12 51 34 17 11 55 44 33 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49
a(66) = 261: 61 1 59 2 53 3 47 4 43 5 41 6 37 7 31 62 8 58 29 9 23 46 10 38 57 19 13 52 39 65 26 12 51 34 17 11 55 44 33 66 22 14 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49
a(67) = 296: 67 1 61 2 59 3 53 4 47 5 43 6 41 7 37 8 62 31 9 29 58 10 46 23 11 19 57 38 12 34 51 17 13 52 39 65 26 22 66 33 44 55 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49 14
a(68) = 296: 67 1 61 2 59 3 53 4 47 5 43 6 41 7 37 8 62 31 9 29 58 10 46 23 11 19 57 38 12 68 34 51 17 13 52 39 65 26 22 66 33 44 55 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49 14
a(69) = 296: 67 1 61 2 59 3 53 4 47 5 43 6 41 7 37 8 62 31 9 29 58 10 46 69 23 11 19 57 38 12 68 34 51 17 13 52 39 65 26 22 66 33 44 55 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 35 49 14
a(70) = 296: 67 1 61 2 59 3 53 4 47 5 43 6 41 7 37 8 62 31 9 29 58 10 46 69 23 11 19 57 38 12 68 34 51 17 13 52 39 65 26 22 66 33 44 55 15 45 30 60 40 50 25 20 36 27 54 18 24 48 32 64 16 28 56 42 63 21 70 35 49 14

Now we have to prove that these minimums can't be beaten. We will need to refer to some other sequences from the database:

%I A073818
%S A073818 2,4,6,10,15,22,33,44,55,68,85,102,119,145,174,203,232,261,296,333,370,
%T A073818 410,451,492,533,590,649,708,767,826,885,944,1005,1072,1139,1207,1278,
%U A073818 1358,1455,1552,1649,1746,1843,1940,2037,2134,2231,2328,2425,2540,2667
%N A073818 a(n) = max(prime(i)*(n+1-i) | 1 <= i <= n).
%e A073818 For n = 5, we take the first 5 primes in ascending order, and multiply them by the numbers from 5 to 1 in descending order: 2*5 = 10 3*4 = 12 5*3 = 15 7*2 = 14 11*1 = 11 The largest product is 15, so a(5) = 15.
%Y A073818 Cf. A073819, A073820.
%K A073818 easy,nonn,new
%O A073818 1,1
%A A073818 David Wasserman (wasserma@spawar.navy.mil), Aug 13 2002

%I A073819
%S A073819 2,2,2,5,5,11,11,11,11,17,17,17,17,29,29,29,29,29,37,37,37,41,41,41,41,
%T A073819 59,59,59,59,59,59,59,67,67,67,71,71,97,97,97,97,97,97,97,97,97,97,97,
%U A073819 97,127,127,127,127,127,127,127,127,149,149,149,149,149,149,149,149
%N A073819 a(n) = prime(i) such that prime(i)*(n+1-i) is maximized (1 <= i <= n).
%C A073819 3 is the only n for which the maximum is not unique; a(3) could also be given as 3.
%F A073819 a(n) = A073818(n)/A073820(n).
%e A073819 For n = 5, we take the first 5 primes in ascending order, and multiply them by the numbers from 5 to 1 in descending order: 2*5 = 10 3*4 = 12 5*3 = 15 7*2 = 14 11*1 = 11 The largest product is 15, so a(5) = 5.
%Y A073819 Cf. A073818, A073820.
%K A073819 easy,nonn,new
%O A073819 1,1
%A A073819 David Wasserman (wasserma@spawar.navy.mil), Aug 13 2002

%I A073820
%S A073820 1,2,3,2,3,2,3,4,5,4,5,6,7,5,6,7,8,9,8,9,10,10,11,12,13,10,11,12,13,14,
%T A073820 15,16,15,16,17,17,18,14,15,16,17,18,19,20,21,22,23,24,25,20,21,22,23,
%U A073820 24,25,26,27,24,25,26,27,28,29,30,31,32,33,34,32,33,31,30,31,32,33,34
%N A073820 a(n) = n+1-i such that prime(i)*(n+1-i) is maximized (1 <= i <= n).
%C A073820 3 is the only n for which the maximum is not unique; a(3) could also be given as 2.
%F A073820 a(n) = A073818(n)/A073819(n).
%e A073820 For n = 5, we take the first 5 primes in ascending order, and multiply them by the numbers from 5 to 1 in descending order: 2*5 = 10 3*4 = 12 5*3 = 15 7*2 = 14 11*1 = 11 The largest product is 15, so a(5) = 3.
%Y A073820 Cf. A073818, A073819.
%K A073820 easy,nonn,new
%O A073820 1,2
%A A073820 David Wasserman (wasserma@spawar.navy.mil), Aug 13 2002

Also, let pi(n) be the number of primes <= n (this is A000720(n)). a(n) will continue to mean A064764(n).

Theorem: For any n >= 4, a(n) >= A073818(pi(n)).

Observe that this bound was achieved above for 19 <= n <= 70.

To prove this theorem, we will use a lemma:

Lemma 1: For n > 3, A073819(n) > A073820(n).

Proof: Let p = A073819(n), and j = A073820(n). Suppose p = 2. Then j = n. By definition of the sequences, 2n >= 3(n - 1), so n <= 3, contrary to hypothesis. So p > 2. Let q be the next prime after p. Then by definition of the sequences, pj >= q(j - 1) >= (p + 2)(j - 1) = pj + 2j - p - 2. So p >= 2j - 2. This immediately implies p > j unless j <= 2. But we already showed p > 2. This completes the proof of Lemma 1.

Proof of Theorem: For n = 4, 5, or 6, the result is shown by direct computation, so assume n >= 7. Let r = A073820(pi(n)). Let p_1, p_2, ..., p_r be the r largest primes <= n, in descending order. Then p_r = A073819(pi(n)), so r*p_r = A073818(pi(n)). Since n >= 7, pi(n) >= 4, so by Lemma 1 p_r > r.

We define r + 1 disjoint nonempty subsets of {1, ..., n} as follows: for 1 <= i <= r, let S_i be the set of all multiples of p_i that are <= n (including p_i). Let S_0 be the set of all j with r <= j <= n such that j is not divisible by any p_i. Now we claim that if x is in S_i, y is in S_j, and 0 <= i < j <= r, then lcm(x, y) >= r*p_r. This is true because p_j divides y but not x, so lcm(x, y) >= x*p_j >= r*p_r since x >= r.

This claim tells us that in forming a permutation with yield less than r*p_r, no element of one of these r + 1 sets may be placed next to an element of another of these sets. So we must have at least r other elements to separate these sets from each other. But there are only r - 1 other elements of {1, ..., n}, a contradiction. This completes the proof of the theorem.

Now it remains to show that we can't beat the values given above for a(11) through a(18). This lemma will be useful:

Lemma 2: For any integer n > 1, if a(n) <= 2(n + 1), then a(n) <= a(n + 1).

Proof: Suppose instead that a(n + 1) < a(n). Pick some permutation of the numbers 1 through n + 1 that yields a(n + 1). If n + 1 is at the beginning or end of this permutation, than by removing n + 1, we get a permutation the numbers from 1 to n, which has a yield no higher that a(n + 1), contradicting the assumption that a(n + 1) < a(n). Thus n + 1 is not at the end of the permutation, so say that it is between x and y. Note that

lcm(x, n + 1) <= a(n + 1) < a(n) <= 2(n + 1).

But lcm(x, n + 1) is a multiple of n + 1, so lcm(x, n + 1) = n + 1, i.e. x divides n + 1. Similarly, y divides n + 1. So lcm(x, y) <= n + 1. But if we remove n + 1 from the permutation, we get a permutation of {1, ..., n}, and (x, y) is the only adjacent pair of this permutation that doesn't occur in the permutation of {1, ..., n + 1}. So this permutation of {1, ..., n} yields no more than a(n + 1). This contradicts the assumption that a(n + 1) < a(n).

More generally, this argument shows that a(n) <= a(n + 1) if there is no integer x less than n + 1 such that n + 1 < gcd(x, n + 1) < a(n).

Proposition: a(11) >= 18.

Proof: If we try to arrange the numbers 1 through 11 so that the lcm's of all adjacent pairs are < 18, we find that some of these numbers are very limited in which numbers they may be placed next to. We list these in a Table of Allowable Neighbors (TAN):

11: 1
10: 1 2 5
9: 1 3
8: 1 2 4
7: 1 2

First notice that 11 can have only one neighbor, so it must be at the end, with 1 next to it. So our permutation must be

11 1 . . . . . . . . .

Next, 7 must be either at the end or between 1 and 2. We display both possibilities:

11 1 7 2 . . . . . . .
11 1 . . . . . . . 2 7

The difference between these two possibilities is not significant. We have 7 numbers left to place. If there is a way to place them in the 7 dots of the first row to obtain a permutation with a yield less than 18, than by reversing the order of these 7 numbers we can also complete the second row to a permutation with the same yield, and vice versa, because a number can be placed at the end iff it can be placed next to a 1. So without loss of generality we may assume that there is only one possiblity (the first one.) We will need this argument again; I will refer to it by saying that the two possiblities are "equally good". In some cases the transformation only works one way, in which case I will say that one possibility is "better" than the other.

So we must complete

11 1 7 2 . . . . . . .

to a permutaiton. 9 may only placed next to 1 and 3, and 1 is inaccessible, so 9 must be at the end, next to 3:

11 1 7 2 . . . . . 3 9

8 may only be placed next to 1, 2, and 4, and 1 is inaccessible, so 8 must be between 2 and 4:

11 1 7 2 8 4 . . . 3 9

10 may only be placed next to 1, 2, and 5, but 1 and 2 are both inaccessible, so 10 can only have one neighbor, a contradiction. This completes the proof.

Proposition: a(12) >= 18.

This follows immediately from Lemma 2.

Proposition: a(13) >= 24.

Proof: We start with a TAN for a yield of less than 24:

13: 1
12: 1 2 3 4 6
11: 1 2
9: 1 2 3 6
8: 1 2 4
7: 1 2 3

Since 13 has only one possible neighbor, it must be at the end:

13 1 . . . . . . . . . . .

11 must be between 1 and 2, or at the end next to 2. Both ways are equally good, so we choose

13 1 11 2 . . . . . . . . .

7 must be either between 2 and 3, or at the end next to 3.

13 1 11 2 7 3 . . . . . . .
13 1 11 2 . . . . . . . 3 7

The first possiblity is better. 8 must be at the end next to 4:

13 1 11 2 7 3 . . . . . 4 8

9 must be between 3 and 6:

13 1 11 2 7 3 9 6 . . . 4 8

But now 12 must be next to both 4 and 6, which is impossible. This completes the proof.

Proposition: a(14) >= 24; a(15) >= 24; a(16) >= 24.

These follow immediately from Lemma 2.

Proposition: a(17) >= 35.

Proof: Consider the following 7 sets of numbers: {17}, {13}, {11}, {9}, {7, 14}, {5, 10, 15}, {12, 8, 16}. Observe that no member of one of these sets may be placed next to a member of another one of these sets, without producing a yield of at least 35. So we need at least 6 numbers to separate these sets from each other, but there are only 5 other numbers in {1, ..., 17}.

Proposition: a(18) >= 35.

This follows immediately from Lemma 2.