Table of σd(n) Values

Let us denote σd(n) the maximum number of distinct primitively rooted squares over all string of length n containing exactly d distinct letters.

The following are (d, n-d) table and (d, n-2d) table with entries of σd(n).

n - d
d 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
2 2 2 3 3 4 5 6 7 7 8 9 10 11 12 12 13 13 14 15 16 17 18 19 20 20 21 22 23 23 23 24 25 26 27 28 29 30 31 32 33 33 34 35 36 36 37 37 38 39 40 41 42 43 44 44 45 46 47 48 48 49 50 51 52 53 54 55
3 2 3 3 4 4 5 6 7 8 8 9 10 11 12 13 13 14 14 15 16 17 18 19 20 21 21 22 23 24 24 25 26 26 27 28 29 30 31 32 33 34
4 2 3 4 4 5 5 6 7 8 9 9 10 11 12 13 14 14 15 15 16 17 18 19 20 21 22 22 23 24 25 25 26 27
5 2 3 4 5 5 6 6 7 8 9 10 10 11 12 13 14 15 15 16 16 17 18 19 20 21 22 23 23 24 25 26
6 2 3 4 5 6 6 7 7 8 9 10 11 11 12 13 14 15 16 16 17 17 18 19 20 21 22 23 24
7 2 3 4 5 6 7 7 8 8 9 10 11 12 12 13 14 15 16 17 17 18 18 19 20 21 22 23 24 25
8 2 3 4 5 6 7 8 8 9 9 10 11 12 13 13 14 15 16 17 18
9 2 3 4 5 6 7 8 9 9 10 10 11 12 13 14 14 15 16 17 18 19
10 2 3 4 5 6 7 8 9 10 10 11 11 12 13 14 15 15 16 17 18 19 20
11 2 3 4 5 6 7 8 9 10 11 11 12 12 13 14 15 16 16 17 18 19 20 21
12 2 3 4 5 6 7 8 9 10 11 12 12 13 13 14 15 16 17
13 2 3 4 5 6 7 8 9 10 11 12 13 13 14 14 15 16 17 18
14 2 3 4 5 6 7 8 9 10 11 12 13 14 14 15 15 16 17 18 19
15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 16 16 17 18 19 20
16 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 16 17 17 18 19
17 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 18 18
18 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18 19
19 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 20
20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20
21 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
23 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
24 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
n - 2d
d 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
2 2 2 3 3 4 5 6 7 7 8 9 10 11 12 12 13 13 14 15 16 17 18 19 20 20 21 22 23 23 23 24 25 26 27 28 29 30 31 32 33 33 34 35 36 36 37 37 38 39 40 41 42 43 44 44 45 46 47 48 48 49 50 51 52 53 54 55
3 3 3 4 4 5 6 7 8 8 9 10 11 12 13 13 14 14 15 16 17 18 19 20 21 21 22 23 24 24 25 26 26 27 28 29 30 31 32 33 34
4 4 4 5 5 6 7 8 9 9 10 11 12 13 14 14 15 15 16 17 18 19 20 21 22 22 23 24 25 25 26 27
5 5 5 6 6 7 8 9 10 10 11 12 13 14 15 15 16 16 17 18 19 20 21 22 23 23 24 25 26
6 6 6 7 7 8 9 10 11 11 12 13 14 15 16 16 17 17 18 19 20 21 22 23 24
7 7 7 8 8 9 10 11 12 12 13 14 15 16 17 17 18 18 19 20 21 22 23 24 25
8 8 8 9 9 10 11 12 13 13 14 15 16 17 18
9 9 9 10 10 11 12 13 14 14 15 16 17 18 19
10 10 10 11 11 12 13 14 15 15 16 17 18 19 20
11 11 11 12 12 13 14 15 16 16 17 18 19 20 21
12 12 12 13 13 14 15 16 17
13 13 13 14 14 15 16 17 18
14 14 14 15 15 16 17 18 19
15 15 15 16 16 17 18 19 20
16 16 16 17 17 18 19
17 17 17 18 18
18 18 18 19
19 19 19 20
20 20 20
21 21
22 22
23 23
24 24


Table of ρd(n) - σd(n) Values

Let ρd(n) be the maximum number of runs over all string of length n containing exactly d distinct letters. The data of ρd(n) was obtained from Andrew Baker's research listed here.

n - d
d 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
2 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 4 3 3 3 3 2 2 2 2 3 2 3 3 3 3 4 4 5 5 5 5 5 4 4 4 5 5 5 5 5 6 6 6 5 5 5 5 5
3 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 3 2 3 3 3 2 2 2 3 3 2
4 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 3 2
5 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2
6 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1
7 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2
8 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0
9 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0
10 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1
11 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
n - 2d
d 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
2 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 4 3 3 3 3 2 2 2 2 3 2 3 3 3 3 4 4 5 5 5 5 5 4 4 4 5 5 5 5 5 6 6 6 5 5 5 5 5
3 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 3 2 3 3 3 2 2 2 3 3 2
4 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2 2 2 2 3 3 2
5 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1 1 1 1 1 2
6 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2 1 1 1
7 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 2
8 0 0 0 1 1 0 0 0 1 1 1 0 0 0
9 0 0 0 1 1 0 0 0 1 1 1 0 0
10 0 0 0 1 1 0 0 0 1 1
11 0 0 0 1 1 0
12 0 0 0 1 1
13 0 0 0
14 0 0


Click here to check out the strings that are both square-maximal and run-maximal for 2<= d, n-d <=10

Last updated on September 21, 2012.

Valid HTML 4.01 Transitional