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

Author

Fabio Visonà, Feb 15 2021

Keywords

• nonn
• more

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.

Examples

			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}
		

Links

• Math StackExchange, A question about this sequence.

Crossrefs

Cf. A003002.

Programs

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;
}

Extensions

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