cp's OEIS Frontend

A341721 a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.

%I A341721 #52 Apr 05 2023 09:15:43
%S A341721 1,2,2,3,3,4,4,5,4,6,6,6,7,8,6,8,9,8,10,9,8,12,12,10,9,14,10,12,15,12,
%T A341721 16,14,12,18,12,14,19,20,14,15,21,16,22,18,15,24,24,18,16,18,18,21,27,
%U A341721 20,18,20,20,30,30,21,31,32,20,24,21,24,34,27,24,24,36,25,37,38,24
%N A341721 a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.
%C A341721 This is a two-party election. The size d of each district must divide n, so there are d' = n/d equal districts. The districts are winner-takes-all, and tied districts go to neither candidate. For an even number of districts, it is enough to win half the districts and tie in one further district.
%C A341721 In general the best choice for d is not unique, since d and n/d give the same answer.
%C A341721 This is related to the gerrymandering question.
%C A341721 See A341578 for further information.
%H A341721 N. J. A. Sloane, <a href="/A341721/b341721.txt">Table of n, a(n) for n = 1..10000</a>
%H A341721 N. J. A. Sloane, <a href="/A341578/a341578.pdf">How to use Gerrymandering to win with only 14 votes when your opponent has 22: (1) Locations of voters</a>
%H A341721 N. J. A. Sloane, <a href="/A341578/a341578_1.pdf">How to use Gerrymandering to win with only 14 votes when your opponent has 22: (2) Make three districts with 12 voters in each, drawn so that your 14 votes win 2 out of the 3 districts</a>
%H A341721 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=9ogbsh8KuEM">Exciting Number Sequences</a> (video of talk), Mar 05 2021.
%H A341721 N. J. A. Sloane, <a href="https://vimeo.com/704569041/4ffa06b95e">The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems</a>, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: <a href="https://sites.math.rutgers.edu/~zeilberg/EM22/C27.pdf">Slides</a>; <a href="http://NeilSloane.com/doc/Math640.04.2022.pdf">Slides (an alternative source)</a>.
%F A341721 a(n) is the minimum value over all ways of writing n = d*d' of:
%F A341721   (d+1)*(d'+1)/4 if d and d' are both odd;
%F A341721   (d+2)*(d'+1)/4 if d is even and d' is odd;
%F A341721   (d+1)*(d'+2)/4 if d is odd and d' is even;
%F A341721   (d+2)*(d'+2)/4-1 if d and d' are both even.
%F A341721 a(n) is bounded roughly between n/4 and n/2 (see graph). More precise bounds, which are attained infinitely often, are floor((n+1)/4 + sqrt(n)/2) <= a(n) <= floor((n/2)+1).
%e A341721 For n=25 voters the smallest number of votes needed to win is 9: gerrymander 5 districts of 5 voters each, with three votes for the party in each of three districts.
%e A341721 For n=36 voters the smallest number of votes needed to win is 14: gerrymander 3 districts of 12 voters each, with seven votes for the party in each of two districts.
%e A341721 For n=64 voters the smallest number of votes needed to win is 24: gerrymander 8 districts of 8 voters each, with five votes for the party in each of four districts and four votes in a fifth district.
%p A341721 with(NumberTheory);
%p A341721 f:=proc(n) local a,v,d,dp; a:=n;
%p A341721 for d in Divisors(n) do dp:=n/d;
%p A341721 if type(d,'even') and type(dp,'even')
%p A341721   then v:=(d+2)*(dp)/4+d/2; if v<a then a:=v; fi;
%p A341721 elif type(d,'even') and type(dp,'odd')
%p A341721   then v:=(d+2)*(dp+1)/4; if v<a then a:=v; fi;
%p A341721 elif type(d,'odd') and type(dp,'even')
%p A341721   then v:=(d+1)*(dp+2)/4; if v<a then a:=v; fi;
%p A341721 elif type(d,'odd') and type(dp,'odd')
%p A341721   then v:=(d+1)*(dp+1)/4; if v<a then a:=v; fi;
%p A341721 fi;
%p A341721 od:  # od d
%p A341721 a;
%p A341721 end;
%p A341721 t1:=[seq(f(n),n=1..100)];
%t A341721 f[n_] := Module[{a, v, d, dp}, a = n;
%t A341721 Do[dp = n/d; v = Which[
%t A341721   EvenQ[d] && EvenQ[dp], (d + 2)*(dp)/4 + d/2,
%t A341721   EvenQ[d] && OddQ[dp], (d + 2)*(dp + 1)/4,
%t A341721   OddQ[d] && EvenQ[dp], (d + 1)*(dp + 2)/4,
%t A341721   OddQ[d] && OddQ[dp], (d + 1)*(dp + 1)/4];
%t A341721   If[v < a, a = v],
%t A341721 {d, Divisors[n]}];
%t A341721 a];
%t A341721 Table[f[n], {n, 1, 100}] (* _Jean-François Alcover_, Apr 04 2023, after Maple code *)
%o A341721 (Python)
%o A341721 from sympy import divisors
%o A341721 def A341721(n): return min((d+2-(d%2))*(e+2-(e%2))//4+int((d%2)or(e%2))-1 for d,e in ((v,n//v) for v in divisors(n) if v*v <= n)) # _Chai Wah Wu_, Mar 05 2021
%Y A341721 See A341578 for the case when the number of voters must be a square.
%Y A341721 See A341319 for a variant.
%Y A341721 See also A290323.
%K A341721 nonn
%O A341721 1,2
%A A341721 _Don Reble_ and _N. J. A. Sloane_, Feb 27 2021