login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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, 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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)