| Bytes | Lang | Time | Link |
|---|---|---|---|
| 205 | C++ gcc | 241119T041237Z | ioveri |
| 177 | Python 2 | 241117T234001Z | Lucenapo |
| 145 | JavaScript ES6 | 241116T232957Z | Arnauld |
| 023 | Japt | 241118T122632Z | Shaggy |
| 015 | 05AB1E | 241118T095956Z | Kevin Cr |
| 018 | Jelly | 241118T041559Z | Jonathan |
| 066 | Charcoal | 241117T215949Z | Neil |
| 025 | MATL | 241117T185149Z | Luis Men |
| 177 | R+numbers | 241117T060021Z | Eonema |
| 039 | J | 241117T113106Z | ovs |
C++ (gcc), 273 237 208 207 205 bytes
[](int c,int&n){int w,m,p,q;for(n=2;q=c!=w;){vector<int>v;w=0;p=2;for(m=++n;m>1|q>1;)m%p?++p,q>1?v.push_back(q),q=1:0:(m/=p,q*=p);for(int&i:v)w+=min(*max_element(&v[0],&i+1),*max_element(&i,&*end(v)))-i;}}
Thanks to ceilingcat and emanresu for reduction
Update: changed to lambda function and ternary operator. I had to switch to gcc because there's an unknown bug for c=0 with clang
Python 2, 238 210 192 177 bytes
def T(d):
a=e=0
while d+e:
A=a=a-1;D=[];x=1
while~A:
c=1;x+=1
while A%x<1:A/=x;c*=x
D+=[c]*(c>1)
e=sum(h-min(max(D[:b+1]),max(D[b:]))for b,h in enumerate(D))
print-a
JavaScript (ES6), 145 bytes
-21 bytes and faster code thanks to @tsh
c=>{for(d=n=[];d.reduce(t=>t-Math.min(Math.max(...[v,...d]=d),m=m>v?m:v)+v,c);)for(x=1,m=--n;~m;m%++x||d.push(g()))g=_=>m%x?1:x*g(m/=x);return-n}
Method
For each integer \$n\$, we compute the values \$d_k=k^{e_k}\$ where \$1\le k\le n\$ and \$e_k\$ is the highest value such that \$k^{e_k}\$ is a divisor of \$n\$. We go on until we have:
$$n=\prod{d_k}$$
This gives us a list in which each \$1\$ corresponds to either a composite value or a prime number that is not a divisor of \$n\$.[1]
For instance, \$120\$ gives the list \$[1,8,3,1,5]\$:
$$120=1^0\times 2^3\times 3^1\times 4^0 \times 5^1$$
For each value \$d_k\neq 1\$ in this list, we compute the amount of water that can be poured in this column with:
$$\min(max\_b_k,max\_a_k)-d_k$$
Where \$max\_b_k\$ (maximum before) and \$max\_a_k\$ (maximum after) are the maximum values in the list up to and from the current value respectively. (Note that the current value is included in both cases.)
We return the smallest integer \$n\$ for which the sum of these water amounts is the target capacity.
1. In the last revision of the code, composite values are not included at all in the list. But the reasoning remains the same.
Japt, 25 23 bytes
Gets slower the larger the expected output.
@¶Xk ü Ë×õÃÕcÈð änÃxÉ}a
Try it or verify the first 30 values in the sequence
@¶Xk ü Ë×õÃÕcÈð änÃxÉ}a :Implicit input of integer U
@ :Function taking an integer X as argument
¶ : Is U equal to
Xk : Prime factors of X
ü : Group (& sort)
Ë : Map each group
× : Reduce by multiplication
õ : Range [1,×]
à : End map
Õ : Transpose (padding left with null)
c : Flat map by
È : Passing each through the following function
ð : Truthy (not null) indices
ä : Consecutive pairs reduced by
n : Inverse subtraction
à : End map
x : Reduce by addition after
É : Subtracting 1
} :End function
a :Get the first integer that returns true when passed through that function
05AB1E, 15 bytes
∞.ΔÒγPLζðδÚ˜ð¢Q
Try it online or verify four test cases. (It's very slow, so it'll time out for \$n=3\$ or \$n\geq6\$..)
Explanation:
∞ # Push an infinite positive list: [1,2,3,...]
.Δ # Pop and find the first value that's truthy for:
Ò # Pop and push its prime factors (including duplicates)
γ # Group the same adjacent factors together
P # Take the product of each inner group
L # Map each product to a ranged [1,product]-list
ζ # Zip/transpose; swapping rows/columns, using " " as filler-char
# for unequal length rows
δ # Map over each inner list:
ð Ú # Trim all leading/trailing " "
˜ # Then flatten this list of lists
ð¢ # Count the amount of " " that are left
Q # Check whether this equals the (implicit) input-integer
# (after which the found result is output implicitly as result)
Jelly, 18 bytes
ÆF*/€Rz0t€0Fċ0⁼ð1#
A monadic Link that accepts a positive integer and yields a singleton list containing the first number with that capacity
...or a full program that prints the number.
How?
Starting at the given capacity, and then counting up, find the first number with the given capacity (a number can't have a capacity greater than itself).
Find the capacity of a number by building its prime-factor landscape, overfilling it with water (as if walls of the highest peak were on each side), removing any water not held, and counting the remaining water units.
ÆF*/€Rz0t€0Fċ0⁼ð1# - Link: positive integer, Capacity
ð1# - set k=Capacity and find the smallest k such that:
ÆF - prime factorization of {k}
*/€ - reduce each {prime, exponent} by exponentiation
R - range (vectorises) -> [[1..p^e] for each [p,e]]
z0 - transpose with filler zero (water)
t€0 - trim zeros from each end of each
F - flatten
ċ0 - count the remaining zeros -> k's capacity
⁼ - equals {Capacity}?
Charcoal, 66 bytes
NθW¬⁼θω«→≔⟦⟧υ≔ⅈηF…²η«≔Xκ⌕X⁰⮌↨ηκ⁰ζ≧÷ζη¿⊖ζ⊞υζ»≔ΣEυ⁻⌊⟦⌈…υ⊕λ⌈✂υλ⟧κω»Iⅈ
Try it online! Link is to verbose version of code. Too slow on TIO for results of four or more digits. Explanation: Port of @Arnauld's JavaScript answer.
Nθ
Input n.
W¬⁼θω«
Repeat until a number with a water capacity of n is found.
→≔⟦⟧υ≔ⅈηF…²η«
Start factorising the next number.
≔Xκ⌕X⁰⮌↨ηκ⁰ζ
Try to raise each factor to its multiplicity.
≧÷ζη
Divide by the result.
¿⊖ζ⊞υζ
Save the prime factorisation if it was nontrivial.
»≔ΣEυ⁻⌊⟦⌈…υ⊕λ⌈✂υλ⟧κω
Calculate the water capacity.
»Iⅈ
Output the found number.
72 bytes for a slightly faster version that can produce four-digit results but not five:
NθW¬⁼θω«→≔⟦⟧υ≔²η≔ⅈζW⊖ζ«W﹪ζη≦⊕η≔Xη⌕X⁰⮌↨ζη⁰ε≧÷εζ⊞υε»≔ΣEυ⁻⌊⟦⌈…υ⊕λ⌈✂υλ⟧κω»Iⅈ
Try it online! Link is to verbose version of code. Explanation: As above except:
→≔⟦⟧υ≔²η≔ⅈζW⊖ζ«
Start factorising the next number.
W﹪ζη≦⊕η
Find the next (prime) factor.
≔Xη⌕X⁰⮌↨ζη⁰ε
Raise it to its multiplicity.
≧÷εζ
Divide by the result.
⊞υε
Save the prime factorisation.
R+numbers, 186 177 bytes
\(x,n=0)repeat{if({a=numbers::primeFactors(n<-n+1);b=unique(a)^table(a);d=(0*b+1)%o%b;sum(pmax(pmin(apply(d*upper.tri(d),1,max),apply(d*lower.tri(d),1,max))-b,0))}==x)return(n)}
Test sequence:
f<-\(x,n=0)repeat{if({a=numbers::primeFactors(n<-n+1);b=unique(a)^table(a);d=(0*b+1)%o%b;sum(pmax(pmin(apply(d*upper.tri(d),1,max),apply(d*lower.tri(d),1,max))-b,0))}==x)return(n)}
`names<-`(sapply(1:24,f),1:24)
#> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#> 60 120 440 168 264 840 2448 528 1904 624 1360 2295 816 1632 20128
#> 16 17 18 19 20 21 22 23 24
#> 1824 48300 3105 15392 2208 13024 2400 10656 4080
Ungolfed:
\ (x,n=0) {
repeat{
if (
{
# increment n in the arguments of `primeFactors`
a=numbers::primeFactors(n<-n+1)
# heights of bars
b=unique(a)^table(a)
# repeat b as length(b) rows to make a square matrix
d=(0*b+1)%o%b
# calculate amount of water per bar and sum
sum(pmax(
# the lesser height of the tallest bars on either side, minus the bar height
pmin(
# vector of tallest bars to the left for each position
apply(d*upper.tri(d),1,max),
# vector of tallest bars to the right for each position
apply(d*lower.tri(d),1,max)
)-b,
0
))
} == x )
{
return(n)
}
}
}
J, 39 bytes
(]+[~:1#.[:(-~>./\<.>./\.)__^/@q:])^:_~
( )^:_~ Starting with the input, call the inner function
until the output does not change.
__^/@q:] prime factorization as a list of prime powers.
(-~>./\<.>./\.) water capacity of each column:
<. element-wise minimum of ...
>./\ cumulative maximum and ...
>./\. cumulative maximum from the back.
-~ subtract the column heights from this.
1#. sum to get total water capacity.
[~: is this not equal to the input?
]+ add to the current value.