login
A341721
a(n) = minimum number of total votes needed for one party to win if there are n voters divided into equal districts.
3
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, 16, 14, 12, 18, 12, 14, 19, 20, 14, 15, 21, 16, 22, 18, 15, 24, 24, 18, 16, 18, 18, 21, 27, 20, 18, 20, 20, 30, 30, 21, 31, 32, 20, 24, 21, 24, 34, 27, 24, 24, 36, 25, 37, 38, 24
OFFSET
1,2
COMMENTS
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.
In general the best choice for d is not unique, since d and n/d give the same answer.
This is related to the gerrymandering question.
See A341578 for further information.
FORMULA
a(n) is the minimum value over all ways of writing n = d*d' of:
(d+1)*(d'+1)/4 if d and d' are both odd;
(d+2)*(d'+1)/4 if d is even and d' is odd;
(d+1)*(d'+2)/4 if d is odd and d' is even;
(d+2)*(d'+2)/4-1 if d and d' are both even.
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).
EXAMPLE
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.
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.
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.
MAPLE
with(NumberTheory);
f:=proc(n) local a, v, d, dp; a:=n;
for d in Divisors(n) do dp:=n/d;
if type(d, 'even') and type(dp, 'even')
then v:=(d+2)*(dp)/4+d/2; if v<a then a:=v; fi;
elif type(d, 'even') and type(dp, 'odd')
then v:=(d+2)*(dp+1)/4; if v<a then a:=v; fi;
elif type(d, 'odd') and type(dp, 'even')
then v:=(d+1)*(dp+2)/4; if v<a then a:=v; fi;
elif type(d, 'odd') and type(dp, 'odd')
then v:=(d+1)*(dp+1)/4; if v<a then a:=v; fi;
fi;
od: # od d
a;
end;
t1:=[seq(f(n), n=1..100)];
MATHEMATICA
f[n_] := Module[{a, v, d, dp}, a = n;
Do[dp = n/d; v = Which[
EvenQ[d] && EvenQ[dp], (d + 2)*(dp)/4 + d/2,
EvenQ[d] && OddQ[dp], (d + 2)*(dp + 1)/4,
OddQ[d] && EvenQ[dp], (d + 1)*(dp + 2)/4,
OddQ[d] && OddQ[dp], (d + 1)*(dp + 1)/4];
If[v < a, a = v],
{d, Divisors[n]}];
a];
Table[f[n], {n, 1, 100}] (* Jean-François Alcover, Apr 04 2023, after Maple code *)
PROG
(Python)
from sympy import divisors
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
CROSSREFS
See A341578 for the case when the number of voters must be a square.
See A341319 for a variant.
See also A290323.
Sequence in context: A096125 A140828 A262907 * A290323 A260254 A337853
KEYWORD
nonn
AUTHOR
Don Reble and N. J. A. Sloane, Feb 27 2021
STATUS
approved