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.
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when your opponent has 22: (1) Locations of voters
N. J. A. Sloane, Exciting Number Sequences (video of talk), Mar 05 2021.
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).
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
KEYWORD
nonn
AUTHOR
Don Reble and N. J. A. Sloane, Feb 27 2021
STATUS
approved