cp's OEIS Frontend

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

%I A275339 #69 Dec 20 2024 02:37:58
%S A275339 60,120,440,168,264,840,2448,528,1904,624,1360,2295,816,1632,20128,
%T A275339 1824,48300,3105,15392,2208,13024,2400,10656,4080,8288,2784,5920,2976,
%U A275339 3552,9120,243600,11840,28560,7104,124352,13120,115776,7872,107200,8256,98624,15040,685608
%N A275339 a(n) is the smallest number which has a water-capacity of n.
%C A275339 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.
%H A275339 Michael De Vlieger, <a href="/A275339/b275339.txt">Table of n, a(n) for n = 1..250</a>
%H A275339 Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher, <a href="https://hosted.math.rochester.edu/ojac/vol13/161.pdf">The water capacity of integer compositions</a>, Online Journal of Analytic Combinatorics, Issue 13, 2018, #6.
%H A275339 Guy L. Steele, <a href="https://www.youtube.com/watch?v=ftcIcn8AmSY&amp;t=514s">Four Solutions to a Trivial Problem</a>, Google Tech Talk 12/1/2015.
%F A275339 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
%e A275339 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.
%e A275339 2^2   ****
%e A275339 3     ***W
%e A275339 5^2   *************************
%e A275339 7     *******WWWWWWWWWWWWWWWW
%e A275339 23    ***********************
%e A275339 48300 is the smallest number which has a water-capacity of 17.
%p A275339 water_capacity := proc(N) option remember; local x,k,n,left,right,wc;
%p A275339 x := [seq(f[1]^f[2], f = op(2,ifactors(N)))]; n := nops(x);
%p A275339 if n = 0 then return 0 fi; left := [seq(0,i=1..n)]; left[1] := x[1];
%p A275339 for k from 2 to n do left[k] := max(left[k-1],x[k]) od;
%p A275339 right := [seq(0,i=1..n)]; right[n] := x[n];
%p A275339 for k from n-1 by -1 to 1 do right[k] := max(right[k+1],x[k]) od;
%p A275339 wc := 0; for k from 1 to n do wc := wc + min(left[k], right[k]) - x[k] od;
%p A275339 wc end:
%p A275339 a := proc(n, search_limit) local j;
%p A275339 for j from 1 to search_limit do if water_capacity(j) = n then return j fi od:
%p A275339 return 0; end: seq(a(n,50000), n=1..30);
%t A275339 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];
%t A275339 a[n_] := For[k = 1, True, k++, If[w[k] == n, Return[k]]];
%t A275339 Array[a, 30] (* _Jean-François Alcover_, Jul 21 2019 *)
%o A275339 (Python)
%o A275339 from functools import cache
%o A275339 from sympy import factorint
%o A275339 @cache
%o A275339 def WaterCapacity(N: int) -> int:
%o A275339     if N < 2: return 0
%o A275339     x: list[int] = [p**e for p, e in factorint(N).items()]
%o A275339     n = len(x); wc = 0
%o A275339     left  = [0] * n;  left[0]  = x[0]
%o A275339     right = [0] * n; right[n-1] = x[n-1]
%o A275339     for k in range(n): left[k] = max(left[k - 1], x[k])
%o A275339     for k in range(n - 2, -1, -1): right[k] = max(right[k + 1], x[k])
%o A275339     for k in range(n): wc += min(left[k], right[k]) - x[k]
%o A275339     return wc
%o A275339 def a(n: int) -> int:
%o A275339     j = 1
%o A275339     while True:
%o A275339         if WaterCapacity(j) == n: return j
%o A275339         j += 1
%o A275339 print([a(n) for n in range(1, 20)])  # _Peter Luschny_, Dec 16 2024
%o A275339 (SageMath)
%o A275339 from functools import cache
%o A275339 from itertools import count, accumulate as y
%o A275339 from operator import sub
%o A275339 @cache
%o A275339 def c(n):
%o A275339     F = [f[0]^f[1] for f in list(factor(n))]
%o A275339     A = lambda k: list(y(F[::k], max))[::k]
%o A275339     return sum(map(sub, map(min, zip(A(1), A(-1))), F))
%o A275339 a = lambda n: next((x for x in count(1) if c(x) == n))
%o A275339 print([a(n) for n in range(1, 20)])  # _Peter Luschny_, Dec 18 2024
%K A275339 nonn,look
%O A275339 1,1
%A A275339 _Peter Luschny_, Aug 03 2016