

A341584


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


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



