OFFSET
1,1
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.
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.
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
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Aug 03 2016
STATUS
approved