A341584 Size of the largest subset of the numbers [1..n] which does not contain a 3-term arithmetic progression modulo n.

0, 1, 2, 2, 2, 2, 4, 3, 4, 4, 4, 4, 4, 4, 6, 4, 6, 5, 8, 6, 8, 6, 8, 6, 8, 7, 8, 8, 8, 8, 8, 8, 9, 8, 10, 9, 10, 10, 12, 10, 11, 9, 12, 9, 12, 10, 12, 10, 13, 10, 14, 11, 14, 11, 16, 11, 16, 12, 16, 12, 16, 13, 16, 13, 16, 14, 16, 13, 16, 14, 18, 14, 16, 14, 20, 14, 16, 14, 20, 15, 18

Offset

0,3

Comments

This is similar to A003002, but the arithmetic progression is modulo n here.

For n >= 3, a(n) can be viewed as the maximum number of vertices that can be chosen from a regular polygon with n sides so that no three of them form an isosceles or equilateral triangle.

Links

Table of n, a(n) for n=0..80.

Math StackExchange, A question about this sequence.

Example

n, a(n), example of an optimal subset:
0, 0, {}
1, 1, {1}
2, 2, {1,2}
3, 2, {1,2}
4, 2, {1,2}
5, 2, {1,2}
6, 4, {1,2,4,5}
7, 3, {1,2,4}
8, 4, {1,2,4,5}
9, 4, {1,2,4,5}
10, 4, {1,2,4,5}
11, 4, {1,2,4,5}
12, 4, {1,2,4,5}
13, 4, {1,2,4,5}
14, 6, {1,2,4,8,9,11}
15, 4, {1,2,4,5}
16, 6, {1,3,4,8,9,11}
17, 5, {1,2,6,7,9}
18, 8, {1,2,4,5,10,11,13,14}
19, 6, {1,3,4,8,9,11}
20, 8, {1,2,4,5,11,12,14,15}

Prog

(C) /* For n >= 3: */
int a(int n)
{
int upp, maxb, s, i, l, h, maxs;
uint64_t b, bs, m, mv[31], mn;
for (l = 1; l <= 31; l++) { mv[l - 1] = 1 << 2*l; mv[l - 1] |= (1 << l); mv[l - 1] |= 1; }
maxb = 1 << n; mn = maxb - 1; h = (n - 1) / 2; maxs = 2*n/3; upp = 0;
for (b = 0; b < maxb; b++) {
  for (i = 0, s = 0, m = 1; i < n; i++, m <<= 1) { if (b & m) s++; }
  if (s <= maxs) {
   for (l = 1; l <= h; l++) {
    m = mv[l - 1];
    for (i = 0; i < n; i++) { if ((b & m) == m) { l = 1000; break; } m = ((m << 1) & mn) | (m >> (n - 1)); }
   }
   if (l < 1000 && s > upp) upp = s;
  }
}
return upp;
}

Crossrefs

Cf. A003002.

Sequence in context: A098983 A097576 A029250 * A110884 A303637 A155904

Adjacent sequences: A341581 A341582 A341583 * A341585 A341586 A341587

Keyword

nonn,more

Author

Fabio Visonà, Feb 15 2021

Extensions

a(31)-a(80) from Bert Dobbelaere, Feb 20 2021

Status

approved