A275339 a(n) is the smallest number which has a water-capacity of n.

60, 120, 440, 168, 264, 840, 2448, 528, 1904, 624, 1360, 2295, 816, 1632, 20128, 1824, 48300, 3105, 15392, 2208, 13024, 2400, 10656, 4080, 8288, 2784, 5920, 2976, 3552, 9120, 243600, 11840, 28560, 7104, 124352, 13120, 115776, 7872, 107200, 8256, 98624, 15040, 685608

Offset: 1

Author

Peter Luschny, Aug 03 2016

Keywords

• nonn
• look

Comments

Define the water-capacity of a number as follows: If n has the prime factorization p1^e1*p2^e2*...*pk^ek let ci be a column of height pi^ei and width 1. Juxtaposing the ci leads to a bar graph which figuratively can be filled by water from the top. The water-capacity of a number is the maximum number of cells which can be filled with water.

Examples

			For example 48300 has the prime factorization 2^2*3*5^2*7*23. The bar graph below has to be rotated counterclockwise for 90 degree.
2^2   ****
3     ***W
5^2   *************************
7     *******WWWWWWWWWWWWWWWW
23    ***********************
48300 is the smallest number which has a water-capacity of 17.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..250
• Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher, The water capacity of integer compositions, Online Journal of Analytic Combinatorics, Issue 13, 2018, #6.
• Guy L. Steele, Four Solutions to a Trivial Problem, Google Tech Talk 12/1/2015.

Programs

Maple

water_capacity := proc(N) option remember; local x,k,n,left,right,wc;
x := [seq(f[1]^f[2], f = op(2,ifactors(N)))]; n := nops(x);
if n = 0 then return 0 fi; left := [seq(0,i=1..n)]; left[1] := x[1];
for k from 2 to n do left[k] := max(left[k-1],x[k]) od;
right := [seq(0,i=1..n)]; right[n] := x[n];
for k from n-1 by -1 to 1 do right[k] := max(right[k+1],x[k]) od;
wc := 0; for k from 1 to n do wc := wc + min(left[k], right[k]) - x[k] od;
wc end:
a := proc(n, search_limit) local j;
for j from 1 to search_limit do if water_capacity(j) = n then return j fi od:
return 0; end: seq(a(n,50000), n=1..30);

Mathematica

w[k_] := With[{fi = Power @@@ FactorInteger[k]}, (fi //. {a___, b_, c__, d_, e___} /; AllTrue[{c}, # < b && # < d &] :> {a, b, Sequence @@ Table[ Min[b, d], {Length[{c}]}], d, e}) - fi // Total];
a[n_] := For[k = 1, True, k++, If[w[k] == n, Return[k]]];
Array[a, 30] (* Jean-François Alcover, Jul 21 2019 *)

Python

from functools import cache
from sympy import factorint
@cache
def WaterCapacity(N: int) -> int:
    if N < 2: return 0
    x: list[int] = [p**e for p, e in factorint(N).items()]
    n = len(x); wc = 0
    left  = [0] * n;  left[0]  = x[0]
    right = [0] * n; right[n-1] = x[n-1]
    for k in range(n): left[k] = max(left[k - 1], x[k])
    for k in range(n - 2, -1, -1): right[k] = max(right[k + 1], x[k])
    for k in range(n): wc += min(left[k], right[k]) - x[k]
    return wc
def a(n: int) -> int:
    j = 1
    while True:
        if WaterCapacity(j) == n: return j
        j += 1
print([a(n) for n in range(1, 20)])  # Peter Luschny, Dec 16 2024

SageMath

from functools import cache
from itertools import count, accumulate as y
from operator import sub
@cache
def c(n):
    F = [f[0]^f[1] for f in list(factor(n))]
    A = lambda k: list(y(F[::k], max))[::k]
    return sum(map(sub, map(min, zip(A(1), A(-1))), F))
a = lambda n: next((x for x in count(1) if c(x) == n))
print([a(n) for n in range(1, 20)])  # Peter Luschny, Dec 18 2024

Formula

Let n = p_1^e_1...p_k^e^k be the canonical prime factorization of n and F = [p_1^e_1, ..., p_k^e^k]. Let L denote the max-accumulation of F and R denote the reverse of the max-accumulation of the reversed F. Then the water-capacity of n is Sum_{j=1..k} (min(L(j), R(j)) - F(j)). (See the Sage implementation.) - Peter Luschny, Dec 18 2024