login
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.
4
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
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
Sequence in context: A140828 A262907 A341721 * A260254 A337853 A282711
KEYWORD
nonn,easy,nice,mult
AUTHOR
Max Alekseyev, Jul 27 2017
EXTENSIONS
Keyword:mult added by Andrew Howroyd, Aug 06 2018
STATUS
approved