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

Author

Max Alekseyev, Jul 27 2017

Keywords

• nonn
• easy
• nice
• mult

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

Examples

			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.
		

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.

Crossrefs

Cf. A003960, A005517.

Programs

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

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]);

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

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

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]

Extensions

Keyword:mult added by Andrew Howroyd, Aug 06 2018