A341721 - OEIS

%I #52 Apr 05 2023 09:15:43

%S 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 16,14,12,18,12,14,19,20,14,15,21,16,22,18,15,24,24,18,16,18,18,21,27,

%U 20,18,20,20,30,30,21,31,32,20,24,21,24,34,27,24,24,36,25,37,38,24

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

%C 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 In general the best choice for d is not unique, since d and n/d give the same answer.

%C This is related to the gerrymandering question.

%C See A341578 for further information.

%H N. J. A. Sloane, <a href="/A341721/b341721.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=9ogbsh8KuEM">Exciting Number Sequences</a> (video of talk), Mar 05 2021.

%H 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 a(n) is the minimum value over all ways of writing n = d*d' of:

%F   (d+1)*(d'+1)/4 if d and d' are both odd;

%F   (d+2)*(d'+1)/4 if d is even and d' is odd;

%F   (d+1)*(d'+2)/4 if d is odd and d' is even;

%F   (d+2)*(d'+2)/4-1 if d and d' are both even.

%F 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 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 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 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 with(NumberTheory);

%p f:=proc(n) local a,v,d,dp; a:=n;

%p for d in Divisors(n) do dp:=n/d;

%p if type(d,'even') and type(dp,'even')

%p   then v:=(d+2)*(dp)/4+d/2; if v<a then a:=v; fi;

%p elif type(d,'even') and type(dp,'odd')

%p   then v:=(d+2)*(dp+1)/4; if v<a then a:=v; fi;

%p elif type(d,'odd') and type(dp,'even')

%p   then v:=(d+1)*(dp+2)/4; if v<a then a:=v; fi;

%p elif type(d,'odd') and type(dp,'odd')

%p   then v:=(d+1)*(dp+1)/4; if v<a then a:=v; fi;

%p fi;

%p od:  # od d

%p a;

%p end;

%p t1:=[seq(f(n),n=1..100)];

%t f[n_] := Module[{a, v, d, dp}, a = n;

%t Do[dp = n/d; v = Which[

%t   EvenQ[d] && EvenQ[dp], (d + 2)*(dp)/4 + d/2,

%t   EvenQ[d] && OddQ[dp], (d + 2)*(dp + 1)/4,

%t   OddQ[d] && EvenQ[dp], (d + 1)*(dp + 2)/4,

%t   OddQ[d] && OddQ[dp], (d + 1)*(dp + 1)/4];

%t   If[v < a, a = v],

%t {d, Divisors[n]}];

%t a];

%t Table[f[n], {n, 1, 100}] (* _Jean-François Alcover_, Apr 04 2023, after Maple code *)

%o (Python)

%o from sympy import divisors

%o 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 See A341578 for the case when the number of voters must be a square.

%Y See A341319 for a variant.

%Y See also A290323.

%K nonn

%O 1,2

%A _Don Reble_ and _N. J. A. Sloane_, Feb 27 2021