login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A275339
a(n) is the smallest number which has a water-capacity of n.
7
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,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
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
Sequence in context: A337098 A252953 A309315 * A049058 A056501 A056491
KEYWORD
nonn,look,changed
AUTHOR
Peter Luschny, Aug 03 2016
STATUS
approved