This site is supported by donations to The OEIS Foundation.
Complete non-self-adjacent paths:Analysis:Longest CNSAPs
There are no approved revisions of this page, so it may not have been Lengths of the longest CNSAPs in a square lattice bounded by rectangles of different dimensions.
Let L2(a,b) denote the lengths of the longest CNSAPs for different values of a and b, the dimensions of the rectangle.
Values of L2(a,b) found empirically are given in the table below:
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 2 3 5 6 8 9 11 12 14 15 17 18 20 21 23 24 26 27 29 30 32 33 35 36 38 3 5 7 9 11 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 4 6 9 11 14 17 20 22 25 28 30 33 36 38 41 44 46 49 52 54 5 8 11 14 17 21 24 27 30 34 37 40 43 46 49 52 6 9 14 17 21 24 29 32 36 40 44 47 51 7 11 16 20 24 29 33 38 42 46 50 8 12 18 22 27 32 38 42 48 52 9 14 20 25 30 36 42 48 53 58 10 15 22 28 34 40 46 52 58 64 11 17 24 30 37 44 50 12 18 26 33 40 47 13 20 28 36 43 51 14 21 30 38 46 15 23 32 41 49 16 24 34 44 52 17 26 36 46 18 27 38 49 19 29 40 52 20 30 42 54 21 32 44 22 33 46 23 35 48 24 36 50 25 38 52
Note that L2(a,b) has been calculated over all starting nodes except for L2(10,9) and L2(10,10). L2(10,9) = 58 for starting nodes 0, 1, 2, 3, 4, 10, 20, 30, 40, a complete set of non-symmetric lattice boundary nodes. L2(10,10) is >= 64 for starting node 0. The run for L2(10,10) did not complete.
Let SL2(n) = Sum(L2(a,b)for all a, b : a + b = n), i.e. the sum of the values on each anti-diagonal.
n SL2(n) D1 D2 4 3 5 10 7 6 19 9 2 7 34 15 6 8 51 17 2 9 78 27 10 10 107 29 2 11 146 39 10 12 186 40 1 13 240 54 14 14 297 57 3 15 368 71 14 16 444 76 5 17 534 90 14 18 625 91 1
Table of first differences, L2(a,b) - L2(a-1,b):
a 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 3 2 3 3 3 2 3 3 2 3 3 2 3 3 2 3 3 2 5 3 3 3 4 3 3 3 4 3 3 3 3 3 3 6 5 3 4 3 5 3 4 4 4 3 4 7 5 4 4 5 4 5 4 4 4 8 6 4 5 5 6 4 6 4 9 6 5 5 6 6 6 5 5 10 7 6 6 6 6 6 6 6 11 7 6 7 7 6 12 8 7 7 7 13 8 8 7 8 14 9 8 8 15 9 9 8 16 10 10 8 17 10 10 18 11 11 19 11 12 20 12 12 21 12 22 13 23 13 24 14 25 14
Table of leading-diagonal differences, L2(a,b) - L2(a-1,b-1).
a 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 3 4 4 5 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 4 4 4 5 6 6 6 7 8 8 9 10 10 11 12 12 13 14 14 5 5 5 6 7 7 7 8 9 9 10 10 10 11 11 6 6 6 7 7 8 8 9 10 10 10 11 7 7 6 7 8 9 9 10 10 10 8 7 6 7 8 9 9 10 10 9 8 7 8 9 10 10 11 10 10 8 8 9 10 10 10 10 11 11 9 8 9 10 10 12 9 9 10 10 13 10 10 10 11 14 10 10 10 15 11 11 11 16 11 12 11 17 12 12 18 12 13 19 13 14 20 13 14 21 14 22 14 23 15 24 15 25 16
Frequency (F) of leading-diagonal differences (D).
D F 4 4 5 4 6 9 7 13 8 14 9 16 10 32 Incomplete from here on. 11 14 12 8 13 6 14 8 15 4 16 2
Table of absolute values of anti-diagonal differences, |L2(a-1,b) - L2(a,b-1)|.
a 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 3 0 1 1 2 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 4 1 0 0 0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 5 1 0 0 0 1 2 2 2 4 4 4 5 5 5 6 6 2 0 0 0 0 2 2 2 3 4 4 5 7 3 1 1 0 0 1 2 2 2 3 8 4 2 2 2 1 0 0 2 2 9 4 2 2 2 2 0 0 1 10 5 3 2 2 2 2 1 0 11 5 4 4 3 2 2 12 6 4 4 4 3 13 6 5 4 4 14 7 6 5 5 15 7 6 5 16 8 7 5 17 8 8 6 18 9 8 19 9 9 20 10 10 21 10 10 22 11 23 11 24 12 25 12
Frequency (F) of absolute values of anti-diagonal differences (D).
F increases with a and b.
D F 0 18 1 12 2 28 3 8 4 18 5 14 6 10 7 6 8 8 9 6 10 8 11 4 12 4
Sum of absolute values of anti-diagonal differences over each anti-diagonal.
Let SAD(n) = Sum|L2(a-1,b) - L2(a,b-1)| over all values of a and b such that a + b = n, where a >= 3, b >= 3, then L2(ceil(n/2),floor(n/2)) = L2(n-2,2) + SAD(n)/2.
n SAD(n)/2 D1 L2(n-2,2) L2(ceil(n/2),floor(n/2)) 4 3 3 5 0 0 5 5 6 1 1 6 7 7 1 0 8 9 8 2 1 9 11 9 3 1 11 14 10 5 2 12 17 11 7 2 14 21 12 9 2 15 24 13 12 3 17 29 14 15 3 18 33 15 18 3 20 38 16 21 3 21 42 17 25 4 23 48 18 29 4 24 53
This suggests that the sequence might continue:
19 33 4 26 59 58 appears to be correct 20 37 4 27 64 64 is a lower bound 21 41 4 29 70 22 46 5 30 76 23 51 5 32 83 24 56 5 33 89 25 61 5 35 96 26 66 5 36 102 27 71 5 38 109 28 77 6 39 116 29 83 6 41 124 30 89 6 42 131 31 95 6 44 139 32 101 6 45 146 33 107 6 47 154 34 113 6 48 161
where the 1st differences (D1) for n >= 7 have the sequence: one 0, two 1's, three 2's, four 3's, five 4's, six 5's, seven 6's etc.
The general term for the sequence 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5 ... is ceil((sqrt(1+8n) - 1)/2). So the general term for the sequence 0,1,1,2,2,2,3,3,3,3,4,4,4,4,4 ... is ceil((sqrt(1+8n) - 1)/2) - 1. As L2(10,9) = 58 for starting nodes 0, 1, 2, 3, 4, 10, 20, 30, 40 and L2(10,10) is >= 64 for starting node 0, it could be conjectured that SAD(n)/2 is approximately equal to sum(ceil((sqrt(1+8(k - 6)) - 1)/2) - 1, k = 7, n) + 1, n >= 7.
Upper bound for L2(a,b) appears to be ceil(3ab/4).
Table of L2(a,b) against ceil(3ab/4).
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
b
2 3 5 6 8 9 11 12 14 15 17 18 20 21 23 24 26 27 29 30 32 33 35 36 38 L2(a,2) = ceil(3a/2)
3 5 6 8 9 11 12 14 15 17 18 20 21 23 24 26 27 29 30 32 33 35 36 38 ceil(3a/2)
3 5 7 9 11 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 L2(a,3) = 2(a + 1), a > 5
5 7 9 12 14 16 18 21 23 25 27 30 32 34 36 39 41 43 45 48 50 52 54 57 ceil(9a/4)
4 6 9 11 14 17 20 22 25 28 30 33 36 38 41 44 46 49 52 54 L2(a,4) = ceil(3a) - floor((a - 2)/3), a > 4
6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 ceil(3a) = 3a
5 8 11 14 17 21 24 27 30 34 37 40 43 46 49 52 L2(a,5) = 3(a + 1) + 1, a > 9
8 12 15 19 23 27 30 34 38 42 45 49 53 57 60 ceil(15a/4)
6 9 14 17 21 24 29 32 36 40 44 47 51 L2(a,6)
9 14 18 23 27 32 36 41 45 50 54 59 ceil(9a/2)
7 11 16 20 24 29 33 38 42 46 50
11 16 21 27 32 37 42 48 53 58
8 12 18 22 27 32 38 42 48 52
12 18 24 30 36 42 48 54 60
9 14 20 25 30 36 42 48 53 58
14 21 27 34 41 48 54 61 68
10 15 22 28 34 40 46 52 58 64
15 23 30 38 45 53 60 68 75
11 17 24 30 37 44 50
17 25 33 42 50 58
12 18 26 33 40 47
18 27 36 45 54
13 20 28 36 43 51
20 30 39 49 59
14 21 30 38 46
21 32 42 53
15 23 32 41 49
23 34 45 57
16 24 34 44 52
24 36 48 60
17 26 36 46
26 39 51
18 27 38 49
27 41 54
19 29 40 52
29 43 57
20 30 42 54
30 45 60
21 32 44
32 48
22 33 46
33 50
23 35 48
35 52
24 36 50
36 54
25 38 52
38 57
Table of ceil(3ab/4) - L2(a,b).
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 4 0 0 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 5 0 1 1 2 2 3 3 4 4 5 5 6 7 8 8 6 0 0 1 2 3 3 4 5 5 6 7 8 7 0 0 1 3 3 4 4 6 7 8 8 0 0 2 3 4 4 6 6 8 9 0 1 2 4 5 6 6 8 10 10 0 1 2 4 5 7 8 10 11 11 0 1 3 5 6 8 12 0 1 3 5 7 13 0 2 3 6 8 14 0 2 4 7 15 0 2 4 8 16 0 2 4 8 17 0 3 5 18 0 3 5 19 0 3 5 20 0 3 6 21 0 4 22 0 4 23 0 4 24 0 4 25 0 5
Frequency (F) of values of (ceil(3ab/4) - L2(a,b)) (D).
D F 0 OO 1 17 2 17 3 21 4 23 5 16 + 6? Incomplete from here on. 6 11 + 12? 7 6 + 14? 8 11 + 14? 10 2 + ? 11 1 + ?
Smallest value starting node of a longest CNSAP for different values of a and b.
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 b 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 5 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 6 0 1 0 0 0 1 0 0 1 2 0 0 7 0 1 1 0 1 1 1 1 1 0 8 0 1 0 0 0 1 1 1 1 9 0 1 0 0 0 1 1 2 0 10 0 1 1 1 1 1 1 0 11 0 1 0 1 2 0 12 0 1 0 1 0 13 0 1 1 1 0 14 0 1 0 1 15 0 1 0 1 16 0 1 1 0 17 0 1 0 18 0 1 0 19 0 1 1 20 0 1 0 21 0 1 22 0 1 23 0 1 24 0 1 25 0 1
Lengths of the longest CNSAPs in a cubic lattice bounded by rectangular cuboids of different dimensions.
Let L3(a,b,c) denote the lengths of the longest CNSAPs for different values of a, b and c, the dimensions of the rectangular cuboid.
Values of L3(a,b,c) found empirically are given in the set of tables below:
c = 2
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
b
2 5 8 10 13 15 18 20 23 25 28 30 33 35 38 40 43 45 48 50
3 8 11 14 18 22 25 28 32 35 39 42 45
4 10 14 19 24 28 33 37 42 46
5 13 18 24 30 35 41 46
6 15 22 28 35 41
7 18 25 33 41
8 20 28 37 46
9 23 32 42
10 25 35 46
11 28 39
12 30 42
13 33 45
14 35
15 38
16 40
17 43
18 45
19 48
20 50
c = 3
a 2 3 4 5 6 7 8 9 10 11 12 13
b
2 8 11 14 18 22 25 28 32 35 39 42 45
3 11 16 21 27 31 36 41 47
4 14 21 28 34 40
5 18 27 34 42
6 22 31 40
7 25 36
8 28 41
9 32 47
10 35
11 39
12 42
13 45
c = 4
a 2 3 4 5 6 7 8 9 10
b
2 10 14 19 24 28 33 37 42 46
3 14 21 28 34 40
4 19 28 36 44
5 24 34 44
6 28 40
7 33
8 37
9 42
10 46
c = 5
a 2 3 4 5 6 7 8
b
2 13 18 24 30 35 41 46
3 18 27 34 42
4 24 34 44
5 30 42
6 35
7 41
8 46
Table of absolute values of anti-diagonal differences, |L3(a-1,b,2) - L3(a,b-1,2)|.
a 3 4 5 6 7 8 9 10 11 12 13 14 b 3 0 1 1 3 4 5 5 7 7 9 9 10 4 1 0 1 2 3 5 5 7 7 5 1 1 0 2 2 4 4 6 3 2 2 0 0 7 4 3 2 0 8 5 5 4 9 5 5 4 10 7 7 11 7 7 12 9 13 9 14 10
Sum of absolute values of anti-diagonal differences over each anti-diagonal.
Let SAD(n,2) = Sum|L3(a-1,b,2) - L3(a,b-1,2)| over all values of a and b such that a + b = n, where a >= 3, b >= 3, then L3(ceil(n/2),floor(n/2),2) = L3(n-2,2,2) + SAD(n,2)/2.
n SAD(n)/2 D1 L3(n-2,2,2) L3(ceil(n/2),floor(n/2),2) 4 5 5 5 0 0 8 8 6 1 1 10 11 7 1 0 13 14 8 4 1 15 19 9 6 2 18 24 10 10 4 20 30 11 12 2 23 35 12 16 4 25 41
Upper bound for L3(a,b,c) appears to be ceil(5abc/8).
Tables of L3(a,b,c) against ceil(5abc/8).
c = 2
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
b
2 5 8 10 13 15 18 20 23 25 28 30 33 35 38 40 43 45 48 50 L3(a,2,2) = ceil(5a/2)
5 8 10 13 15 18 20 23 25 28 30 33 35 38 40 43 45 48 50 ceil(5a/2)
3 8 11 14 18 22 25 28 32 35 39 42 45 L3(a,3,2)
8 12 15 19 23 27 30 34 38 42 45 49 ceil(15a/4)
4 10 14 19 24 28 33 37 42 46 L3(a,4,2)
10 15 20 25 30 35 40 45 50 ceil(5a) = 5a
5 13 18 24 30 35 41 46 L3(a,5,2)
13 19 25 32 38 44 50 ceil(25a/4)
6 15 22 28 35 41 L3(a,6,2)
15 23 30 38 45 ceil(15a/2)
7 18 25 33 41 L3(a,7,2)
18 27 35 44 ceil(35a/4)
8 20 28 37 46 L3(a,8,2)
20 30 40 50 ceil(10a) = 10a
9 23 32 42 L3(a,9,2)
23 34 45 ceil(45a/4)
10 25 35 46 L3(a,10,2)
25 38 50 ceil(25a/2)
11 28 39 L3(a,11,2)
28 42 ceil(55a/4)
12 30 42 L3(a,12,2)
30 45 ceil(15a) = 15a
13 33 45 L3(a,13,2)
33 49 ceil(65a/4)
14 35
35
15 38
38
16 40
40
17 43
43
18 45
45
19 48
48
20 50
50
c = 3
a 2 3 4 5 6 7 8 9 10 11 12 13
b
2 8 11 14 18 22 25 28 32 35 39 42 45 L3(a,2,3)
8 12 15 19 23 27 30 34 38 42 45 49 ceil(15a/4)
3 11 16 21 27 31 36 41 47 L3(a,3,3)
12 17 23 29 34 40 45 51 ceil(45a/8)
4 14 21 28 34 40 L3(a,4,3)
15 23 30 38 45 ceil(15a/2)
5 18 27 34 42 L3(a,4,3)
19 29 38 47 ceil(75a/8)
6 22 31 40 L3(a,4,3)
23 34 45 ceil(45a/4)
7 25 36 L3(a,4,3)
27 40 ceil(105a/8)
8 28 41 L3(a,8,3)
30 45 ceil(15a) = 15a
9 32 47 L3(a,9,3)
34 51 ceil(135a/8)
10 35
38
11 39
42
12 42
45
13 45
49
Tables of ceil(5abc/8) - L3(a,b,c).
c = 2
a 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
b
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 1 1 1 1 2 2 2 3 3 3 4
4 0 1 1 1 2 2 3 3 4
5 0 1 1 2 3 3 4
6 0 1 2 3 4
7 0 2 2 3
8 0 2 3 4
9 0 2 3
10 0 3 4
11 0 3
12 0 3
13 0 4
14 0
15 0
16 0
17 0
18 0
19 0
20 0
c = 3
a 2 3 4 5 6 7 8 9 10 11 12 13
b
2 0 1 1 1 1 2 2 2 3 3 3 4
3 1 1 2 2 3 4 4 4
4 1 2 2 4 5
5 1 2 4 5
6 1 3 5
7 2 4
8 2 4
9 2 4
10 3
11 3
12 3
13 4
If a = b = c = n,
n ceil(5abc/8) L3(n,n,n) D1 Freq ceil(5abc/8) - L3(n,n,n) 2 5 5 48 0 3 17 16 11 192 1 4 40 36 20 192 4 5 78 67? 31 11? 6 135 118? 51 17?
Does L3(n,n,n) = 2*L3(n-1,n-1,n-1) - L3(n-3,n-3,n-3) for n >= 5?
a L3(a,5,5) 2 30 3 42 4 >=54 5 >=64
