A290323 Minimal number of supporters among total of n voters that may make (but not guarantee) their candidate win in a multi-level selection based on the majority vote at each level.

1, 2, 2, 3, 3, 4, 4, 5, 4, 6, 6, 6, 7, 8, 6, 9, 9, 8, 10, 9, 8, 12, 12, 10, 9, 14, 8, 12, 15, 12, 16, 15, 12, 18, 12, 12, 19, 20, 14, 15, 21, 16, 22, 18, 12, 24, 24, 18, 16, 18, 18, 21, 27, 16, 18, 20, 20, 30, 30, 18, 31, 32, 16, 25, 21, 24, 34, 27

Offset

1,2

Comments

Each group in a given level must have the same number of voters. A tie in the voting results in a win for the opposition. (A003960 appears to describe the case in which a tie results in a loss for the opposition.) - Peter Kagey, Aug 16 2017

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

Links

Peter Kagey, Table of n, a(n) for n = 1..10000

Author?, Solution to problem M1 (in Russian), Kvant 7 (1970), 49-51.

Author?, Problem M1 with solution (in Russian)

Wikipedia, Gerrymandering.

Formula

Let n = 2^m*p1*...*pk, where pi are odd primes. Then a(n) = c*(p1+1)/2*...*(pk+1)/2 = c*A003960(n), where c=2 if m=1; c=5^b if m=3b; c=3*5^b if m=3b+2; c=9*5^b, if m=3b+4 (b>=0). [So c(m) = A005517(m+1). - Andrey Zabolotskiy, Jan 27 2022]

Example

For n=9, four supporters are enough in the following 2-level selection with (s)upporters and (o)pponents: ((sso),(sso),(ooo)). On the other hand, no smaller number of supporters can lead to a win in any multi-level selection. Hence, a(9)=4.

Mathematica

f[p_, e_] := ((p + 1)/2)^e; f[2, e_] := Switch[Mod[e, 3], 1, 9/5, 2, 3, 0, 1] * 5^Floor[e/3]; f[2, 1] = 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 18 2023 *)

Prog

(PARI) A290323(n) = my(m=valuation(n, 2), f=factor(n>>m)); if(m==1, 2, [1, 9/5, 3][m%3+1]*5^(m\3)) * prod(i=1, #f~, ((f[i, 1]+1)/2)^f[i, 2]);
(Ruby)
def divisors_of(n); (2..n).select { |d| n % d == 0 } end
def f(n, group_size); (group_size/2 + 1) * a(n / group_size) end
def a(n); n == 1 ? 1 : divisors_of(n).map { |d| f(n, d) }.min end
# Peter Kagey, Aug 16 2017
(Python)
from sympy import factorint
from functools import reduce
from operator import mul
def A290323(n):
    f = factorint(n)
    m = f[2] if 2 in f else 0
    a, b = divmod(m, 3)
    c = 2 if m == 1 else 3**(b*(b+1)%5)*5**(a-(b%2))
    return c*reduce(mul, (((d+1)//2)**f[d] for d in f if d != 2), 1) # Chai Wah Wu, Mar 05 2021

Crossrefs

Cf. A003960, A005517.

Sequence in context: A140828 A262907 A341721 * A260254 A337853 A282711

Adjacent sequences: A290320 A290321 A290322 * A290324 A290325 A290326

Keyword

nonn,easy,nice,mult

Author

Max Alekseyev, Jul 27 2017

Extensions

Keyword:mult added by Andrew Howroyd, Aug 06 2018

Status

approved