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

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

Author

Don Reble and N. J. A. Sloane, Feb 27 2021

Keywords

• nonn

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.

Examples

			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.
		

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, 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
• 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).

Crossrefs

See A341578 for the case when the number of voters must be a square.

See A341319 for a variant.

See also A290323.

Programs

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
				

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 *)

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

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).