Sean Chorney - cp's OEIS frontend

User: Sean Chorney

Sean Chorney has authored 2 sequences.

A341578 a(n) is the minimum number of total votes needed for one party to win if there are n^2 voters divided into equal districts.

1, 3, 4, 8, 9, 14, 16, 24, 25, 33, 36, 45, 49, 60, 64, 80, 81, 95, 100, 117, 121, 138, 144, 165, 169, 189, 196, 224, 225, 247, 256, 288, 289, 315, 324, 350, 361, 390, 400, 429, 441, 473, 484, 528, 529, 564, 576, 624, 625, 663, 676, 728, 729, 770, 784, 825, 841, 885, 900, 943

Offset: 1

Sean Chorney, Feb 14 2021

nonn

Comments from Jack W Grahl and Andrew Weimholt, Feb 26 2021: (Start):
This is a two-party election. The size d of each district must divide n^2, so there are n^2/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.
So for 5 districts of 5 votes each, one party could win with 3 votes in each of 3 districts, and 0 in all other districts, for a total of a(5) = 9 votes.
For 8 districts of size 8, 5 votes in each of 4 districts and 4 votes in a fifth district are enough, for a total of a(8) = 24 votes.
d need not equal n. For n=6, it is better to gerrymander the 36 votes into 3 districts with 12 votes each, and then a(6) = 14 = 7+7+0 votes are enough to win. (End)
This is related to the gerrymandering question. What is the asymptotic behavior of a(n)? - N. J. A. Sloane, Feb 20 2021. Answer from Don Reble, Feb 26 2020: The lower bound is [(n^2+1)/4 + n/2]; the upper bound is [n^2/4 + n]. Each bound is reached infinitely often. In general the best choice for d is not unique, since d and n/d give the same answer.

			For a(2), divisors of 2^2 are 1, 2, 4:
d=1: (floor(1/2)+1)*(floor(2^2/(2*1))+1) = 1*3 = 3
d=3: (floor(2/2)+1)*(floor(2^2/(2*2))+1) = 2*2 = 4
d=9: (floor(4/2)+1)*(floor(2^2/(2*4))+1) = 3*1 = 3
OR
since n is even, ((2/2)+1)^2-1=3
Party A only needs 3 cells out of 4 to win a majority of districts.
For a(6), divisors of 6^2 are 1, 2, 3, 4, 6, 9, 12, 18, 36:
By symmetry we can ignore d = 9, 12, 18 and 36;
d=1: (floor(1/2)+1)*(floor(6^2/(2*1))+1) = 1*19 = 19
d=2: (floor(2/2)+1)*(floor(6^2/(2*2))+1) = 2*10 = 20
d=3: (floor(3/2)+1)*(floor(6^2/(2*3))+1) = 2*7  = 14
d=4: (floor(4/2)+1)*(floor(6^2/(2*4))+1) = 3*5  = 15
d=6: (floor(6/2)+1)*(floor(6^2/(2*6))+1) = 4*4  = 16
OR
since n is even, ((6/2)+1)^2-1=15
Party A only needs 14 cells out of 36 to win a majority of districts.

N. J. A. Sloane, Table of n, a(n) for n = 1..5000
N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when you opponent has 22: (1) Locations of voters
N. J. A. Sloane, How to use Gerrymandering to win with only 14 votes when you 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).
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 21.

See A341721 for an analog where there are n voters, not n^2.
See A341319 for a variant.
See also A290323.

Table[Min[Table[(Floor[d/2]+1)*(Floor[n^2/(2*d)]+1),{d,Divisors[n^2]}],If[EvenQ[n],(n/2+1)^2-1,Infinity]],{n,60}](* Stefano Spezia, Feb 15 2021 *)

from sympy import divisors
def A341578(n):
    c = min((d//2+1)*(n**2//(2*d)+1) for d in divisors(n**2,generator=True) if d<=n)
    return c if n % 2 else min(c,(n//2+1)**2-1) # Chai Wah Wu, Mar 05 2021

a(n) is the minimum value of {(floor(d/2)+1)*(floor(n^2/(2*d))+1) over all divisors d of n^2 AND (n/2+1)^2-1, if n is even}.

Entry revised by N. J. A. Sloane, Feb 26 2021.

A341319 Minimum number of cells needed in an n X n grid to win a majority of districts when all districts are required to be the same size.

Original entry on oeis.org

1, 3, 4, 9, 9, 14, 16, 25, 25, 33, 36, 45, 49, 60, 64, 81, 81, 95, 100, 117, 121, 138, 144, 165, 169, 189, 196, 225, 225, 247, 256, 289, 289, 315, 324, 350, 361, 390, 400, 429, 441, 473, 484, 529, 529, 564, 576, 625, 625, 663, 676, 729, 729, 770, 784, 825, 841, 885, 900, 943

Offset: 1

Sean Chorney, Feb 08 2021

nonn

Consider an n X n grid in which each cell represents a vote for a political party "A" or "B". The grid is divided into equal-sized districts and the winner of each district is decided by a majority of "A"s or "B"s. This sequence is the minimum number of "A"s needed to win more districts than "B" if n = 1, 2, 3, ... A tie within a district is not accepted. For example, if n=5, and the district size is also 5, party "A" needs 3 cells in 3 districts (total = 3*3=9) to win 3 districts to 2.

This is related to the gerrymandering question. - N. J. A. Sloane, Feb 27 2021

			For a(3), divisors of 3^2 are 1, 3, 9:
  d=1: (floor(1/2)+1)*(floor(3^2/(2*1))+1) = 1*5 = 5
  d=3: (floor(3/2)+1)*(floor(3^2/(2*3))+1) = 2*2 = 4
  d=9: (floor(9/2)+1)*(floor(3^2/(2*9))+1) = 5*1 = 5
Party A only needs 4 cells out of 9 to win a majority of districts.
For a(6), divisors of 6^2 are 1, 2, 3, 4, 6, 9, 12, 18, 36:
By symmetry we can ignore d = 9, 12, 18 and 36;
  d=1: (floor(1/2)+1)*(floor(6^2/(2*1))+1) = 1*19 = 19
  d=2: (floor(2/2)+1)*(floor(6^2/(2*2))+1) = 2*10 = 20
  d=3: (floor(3/2)+1)*(floor(6^2/(2*3))+1) = 2*7  = 14
  d=4: (floor(4/2)+1)*(floor(6^2/(2*4))+1) = 3*5  = 15
  d=6: (floor(6/2)+1)*(floor(6^2/(2*6))+1) = 4*4  = 16
Party A only needs 14 cells out of 36 to win a majority of districts.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A341578 (ties are allowed), A002265(n+6) (US Electoral College system: unequal sizes of districts, winner in each district takes all its votes), A290323 (multiple levels).

See A341721 for a case where the number of voters need not be a square.

a:= n->min(map(d->(iquo(d, 2)+1)*(iquo(n^2, 2*d)+1), numtheory[divisors](n^2))):
seq(a(n), n=1..60);  # Alois P. Heinz, Feb 09 2021

a[n_] := Table[(Floor[d/2]+1)*(Floor[n^2/(2d)]+1), {d, Divisors[n^2]}] // Min;
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Apr 04 2023 *)

a(n)={vecmin([(floor(d/2) + 1)*(floor(n^2/(2*d)) + 1) | d<-divisors(n^2)])} \\ Andrew Howroyd, Feb 09 2021

from sympy import divisors
def A341319(n): return min((d//2+1)*(e//2+1) for d,e in ((v,n**2//v) for v in divisors(n**2) if v <= n)) # Chai Wah Wu, Mar 05 2021

a(n) is the minimum value of (floor(d/2)+1)*(floor(n^2/(2*d))+1) over all divisors d of n^2.

Terms a(29) and beyond from Andrew Howroyd, Feb 09 2021

cp's OEIS Frontend

User: Sean Chorney

A341578 a(n) is the minimum number of total votes needed for one party to win if there are n^2 voters divided into equal districts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions