cp's OEIS Frontend

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

%I A341584 #24 Feb 21 2021 14:08:33
%S A341584 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,
%T A341584 10,9,10,10,12,10,11,9,12,9,12,10,12,10,13,10,14,11,14,11,16,11,16,12,
%U A341584 16,12,16,13,16,13,16,14,16,13,16,14,18,14,16,14,20,14,16,14,20,15,18
%N A341584 Size of the largest subset of the numbers [1..n] which does not contain a 3-term arithmetic progression modulo n.
%C A341584 This is similar to A003002, but the arithmetic progression is modulo n here.
%C A341584 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.
%H A341584 Math StackExchange, <a href="https://math.stackexchange.com/questions/4012158/number-of-points-chosen-form-a-polygon-to-have-no-isosceles-and-equilateral-tria">A question about this sequence</a>.
%e A341584 n, a(n), example of an optimal subset:
%e A341584 0, 0, {}
%e A341584 1, 1, {1}
%e A341584 2, 2, {1,2}
%e A341584 3, 2, {1,2}
%e A341584 4, 2, {1,2}
%e A341584 5, 2, {1,2}
%e A341584 6, 4, {1,2,4,5}
%e A341584 7, 3, {1,2,4}
%e A341584 8, 4, {1,2,4,5}
%e A341584 9, 4, {1,2,4,5}
%e A341584 10, 4, {1,2,4,5}
%e A341584 11, 4, {1,2,4,5}
%e A341584 12, 4, {1,2,4,5}
%e A341584 13, 4, {1,2,4,5}
%e A341584 14, 6, {1,2,4,8,9,11}
%e A341584 15, 4, {1,2,4,5}
%e A341584 16, 6, {1,3,4,8,9,11}
%e A341584 17, 5, {1,2,6,7,9}
%e A341584 18, 8, {1,2,4,5,10,11,13,14}
%e A341584 19, 6, {1,3,4,8,9,11}
%e A341584 20, 8, {1,2,4,5,11,12,14,15}
%o A341584 (C) /* For n >= 3: */
%o A341584 int a(int n)
%o A341584 {
%o A341584 int upp, maxb, s, i, l, h, maxs;
%o A341584 uint64_t b, bs, m, mv[31], mn;
%o A341584 for (l = 1; l <= 31; l++) { mv[l - 1] = 1 << 2*l; mv[l - 1] |= (1 << l); mv[l - 1] |= 1; }
%o A341584 maxb = 1 << n; mn = maxb - 1; h = (n - 1) / 2; maxs = 2*n/3; upp = 0;
%o A341584 for (b = 0; b < maxb; b++) {
%o A341584   for (i = 0, s = 0, m = 1; i < n; i++, m <<= 1) { if (b & m) s++; }
%o A341584   if (s <= maxs) {
%o A341584    for (l = 1; l <= h; l++) {
%o A341584     m = mv[l - 1];
%o A341584     for (i = 0; i < n; i++) { if ((b & m) == m) { l = 1000; break; } m = ((m << 1) & mn) | (m >> (n - 1)); }
%o A341584    }
%o A341584    if (l < 1000 && s > upp) upp = s;
%o A341584   }
%o A341584 }
%o A341584 return upp;
%o A341584 }
%Y A341584 Cf. A003002.
%K A341584 nonn,more
%O A341584 0,3
%A A341584 _Fabio Visonà_, Feb 15 2021
%E A341584 a(31)-a(80) from _Bert Dobbelaere_, Feb 20 2021