19
\$\begingroup\$

The Torian, \$x!x\$, of a non-negative integer \$x\$ can be recursively defined as

$$ x!0 = x \\ x!n = \prod^x_{i=1} i!(n-1) = 1!(n-1) \times 2!(n-1) \times \cdots \times x!(n-1) $$

The Torian is then equal to \$x!x\$ for a given \$x\$. This sequence begins \$0, 1, 2, 24, 331776, ...\$ for \$x = 0, 1, 2, 3, 4, ...\$

Alternatively, you can consider the binary function \$!\$ to be instead \$f(x, y)\$. We then have \$f(x, 0) = x\$ and \$f(x, y) = f(1, y-1) \times f(2, y-1) \times \cdots \times f(x, y-1)\$. You should then calculate \$f(x, x)\$.

You are to take a non-negative integer \$x\$ and output \$x!x\$. You may take input and output in any convenient method, and you don't have to worry about outputs exceeding your language's integer limit. This is , so the shortest code in bytes wins

Test cases

x x!x
0  0
1  1
2  2
3  24
4  331776
5  2524286414780230533120
6  18356962141505758798331790171539976807981714702571497465907439808868887035904000000
7  5101262518548258728945891181868950955955001607224762539748030927274644810006571505387259191811206793959788670295182572066866010362135771367947051132012526915711202702574141007954099155897521232723988907041528666295915651551212054155426312621842773666145180823822511666294137239768053841920000000000000000000000000000

And here is a reference program that produces output for \$0!0\$ to \$11!11\$

\$\endgroup\$
7
  • \$\begingroup\$ Brownie points for beating my 10 byte Jelly answer, which may or may not have caused a great deal of discussion around recursion in Jelly in TNB :) \$\endgroup\$ Jul 13 at 1:14
  • \$\begingroup\$ Out of curiosity does it have any applications? The wiki page didn't mention any... \$\endgroup\$
    – Jonah
    Jul 13 at 2:48
  • 2
    \$\begingroup\$ @Jonah Given that the only reference I can find to it is that wiki for large numbers, I doubt it tbh. It isn't even on OEIS, so it's either incredibly obscure, or has no practical applications (or both) \$\endgroup\$ Jul 13 at 2:57
  • 3
    \$\begingroup\$ OEIS(without 0 index): A068493 \$\endgroup\$
    – Razetime
    Jul 13 at 3:37
  • \$\begingroup\$ @Shaggy Uh... If you don't know it, forget it (though there's a challenge on it) Also forget ! and let's call it f(x,y). The definition of Torian says, the value of f(x,y) can be calculated by recursively calculating f(1,y-1), f(2,y-1), ..., f(x,y-1) and taking their product. f(x,0) is the base case, and is defined to be simply x. Then the task is to compute f(x,x) for given x. \$\endgroup\$
    – Bubbler
    Jul 13 at 8:51

18 Answers 18

14
\$\begingroup\$

Jelly, 6 bytes

R×\⁸¡Ṫ

Try it online!

APL (Dyalog Unicode), 10 bytes

{⊃⌽×\⍣⍵⍳⍵}

Try it online!

The main trick is to observe how the computation of x!y progresses as y increases.

1!0=1    2!0=2        3!0=3            4!0=4                ...
1!1=1    2!1=1*2      3!1=1*2*3        4!1=1*2*3*4          ...
1!2=1!1  2!2=1!1*2!1  3!2=1!1*2!1*3!1  4!2=1!1*2!1*3!1*4!1  ...
1!3=1!2  2!3=1!2*2!2  3!3=1!2*2!2*3!2  4!3=1!2*2!2*3!2*4!2  ...
...

Basically going to the next row is just a matter of product scan on the previous row. Therefore, to get the value of x!x, we can just run product scan on the range 1..x x times, and extract the last element.

One caveat of this approach is that the 0 case must be checked separately. In Jelly, popping from an empty array gives 0. In APL, of the empty vector is 0 (⊢/ does not work in place of ⊃⌽).

I have 16-byte J and 14-byte ngn/k answers using the same algorithm. Can you find them? (ngn/k code includes converting 0N to 0)

\$\endgroup\$
6
  • 2
    \$\begingroup\$ ngn/k {0^*|x*\/1+!x} is 14 \$\endgroup\$
    – rak1507
    Jul 13 at 2:32
  • 1
    \$\begingroup\$ J: {:@(*/\@[&1)1+i. Try it online! \$\endgroup\$
    – Jonah
    Jul 13 at 2:52
  • 2
    \$\begingroup\$ @rak1507 I had {*|0,x*\/1+!x} \$\endgroup\$
    – Razetime
    Jul 13 at 3:32
  • \$\begingroup\$ You can submit the APL answer separately and just say it uses the same algorithm as this one. That def deserves to be its own rep factory! \$\endgroup\$
    – AviFS
    Jul 13 at 20:20
  • \$\begingroup\$ @Razetime What's the 0, for? (I stumbled upon a similar solution (and with ngn's help, almost the same as yours), but I didn't see an edge case that needed 0,) \$\endgroup\$
    – user
    Aug 6 at 16:06
12
\$\begingroup\$

Jelly, 4 bytes

R¡FP

Try it online!

       (Starting from [n],)
R      Recursively replace each x with [1..x]
 ¡     n times
  F    Flatten
   P   Product

For example for the input 4 yields

[
    [[[1]]],
    [[[1]], [[1], [1, 2]]],
    [[[1]], [[1], [1, 2]], [[1], [1, 2], [1, 2, 3]]],
    [[[1]], [[1], [1, 2]], [[1], [1, 2], [1, 2, 3]], [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]]
]

and the product of all numbers in that nested list is 331776.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ That ¡ operator is just not fair! \$\endgroup\$
    – Shaggy
    Jul 13 at 20:13
9
\$\begingroup\$

Haskell, 43 bytes

f x=x!x
x!0=x
x!n=product$map(!(n-1))[1..x]

Try it online!

+8 bytes due to the problem needing a function that only takes a single argument. Thanks to @Lynn for pointing that out

Thanks to OVS for pointing out map is shorter than a list comprehension and taking 1 byte off.

My first time ever submitting a haskell answer. I am a beginner so do point out places where I can shorten my code :)


Haskell, 39 bytes

f x=x!x
x!0=x
0!_=1
x!n=x!(n-1)*(x-1)!n

Try it online!

Thanks to @Alwin for suggesting this version.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ map is a byte shorter than a list comprehension: Try it online! \$\endgroup\$
    – ovs
    Jul 13 at 10:57
  • 3
    \$\begingroup\$ I'm not sure if this is an appropriate comment, but I noticed you can reach 31 bytes using the approach I used in my python answer x!0=x 0!x=1 x!n=x!(n-1)*(x-1)!n \$\endgroup\$
    – Alwin
    Jul 13 at 10:59
  • 2
    \$\begingroup\$ I believe you need an extra line like f x=x!x for this to be a valid answer. \$\endgroup\$
    – Lynn
    Jul 13 at 14:58
8
\$\begingroup\$

Python 3 48 bytes

f=lambda x,y:f(x,y-1)*f(x-1,y)if x*y else(y>0)+x

TIO

55 bytes

if a more conventional input is required. I don't know how to initialize the default 2nd argument to equal the first, so I've rewritten everything as t=x-y without much more thought.

f=lambda x,t=0:f(x,t+1)*f(x-1,t-1)if(x-t)*x else(x>t)+x

Thanks to Arnauld for saving 3 bytes

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to PPCG :) I don't know that taking both x & y as the initial input would be valid, though, I think you'd need to initialise y to x within the function, as I've done. \$\endgroup\$
    – Shaggy
    Jul 13 at 8:35
  • 1
    \$\begingroup\$ Unfortunately, Shaggy is correct here in that you should only take one input, and the second should be initialised to the first \$\endgroup\$ Jul 13 at 11:53
  • \$\begingroup\$ Thanks for clarifying. The 57 byte answer will accept 1 argument, using default t=0 to act as though y=x, since I don't know how to set the default y=x. I hope someone teaches me a better way though! \$\endgroup\$
    – Alwin
    Jul 13 at 11:56
6
\$\begingroup\$

JavaScript (Node.js), 43 bytes

Expects and returns a BigInt.

f=(x,n=x,g=_=>x?f(x--,~-n)*g():1n)=>n?g():x

Try it online!

This actually simplifies down to ...

JavaScript (Node.js), 37 bytes

f=(x,n=x)=>n?x?f(x,~-n)*f(~-x,n):1n:x

Try it online!

... which is essentially the same as Alwin's answer.

\$\endgroup\$
5
\$\begingroup\$

Factor, 53 45 41 bytes

[ dup [1,b] [ cum-product ] repeat last ]

Try it online!

A port of @Bubbler's answers; take the product scan (cumulative product) of 1..x x times and then return the last element.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Didn't know there's a word that's literally swapd times. Nice find. \$\endgroup\$
    – Bubbler
    Jul 13 at 2:37
  • 1
    \$\begingroup\$ @Bubbler Thanks. I only learned about repeat yesterday and didn't expect to put it to use so soon. It's hidden in the wrong vocabulary. \$\endgroup\$
    – chunes
    Jul 13 at 2:42
5
+100
\$\begingroup\$

K (oK), 13 12 14 bytes

Saved 1 byte thanks to ngn

Fixed thanks to Razetime

{*|0,x*\/1+!x}

Try it online!

{*|0,x*\/1+!x}
           !x  Range [0..x-1]
         1+    Increment range
     x  /      Repeat x times:
      *\       Get the cumulative products of the list
               When this is done y times, we get [1!y, 2!y...x!y]
   0,          Prepend a 0 in case x is 0
 *|            Get the last number (x!y) by reversing and getting the head
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 46 bytes

x=>(g=p=>x>1n?x--**p*g(p*y++/i++):x)(i=1n,y=x)

Try it online!

Use

$$ f\left(n\right) = \prod_{i=1}^n i^{{2n-i-1}\choose{n-1}} $$

with exception

$$ f\left(0\right) = 0 $$

\$\endgroup\$
1
4
\$\begingroup\$

Haskell, 41 bytes

f n=product$iterate(>>= \x->[1..x])[n]!!n

Try it online!

Same idea as my Jelly answer: starting from [n], repeatedly replace each x by 1..x, n times, then take the product.

  [4]
→ [1,2,3,4]
→ [1,1,2,1,2,3,1,2,3,4]
→ [1,1,1,2,1,1,2,1,2,3,1,1,2,1,2,3,1,2,3,4]
→ [1,1,1,1,2,1,1,1,2,1,1,2,1,2,3,1,1,1,2,1,1,2,1,2,3,1,1,2,1,2,3,1,2,3,4]
→ product: 331776
\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 27 bytes

1##&@@#&//@Nest[Range,#,#]&

Try it online!

Port of Lynn's solution.


Wolfram Language (Mathematica), 33 bytes

Nest[f1##&@@f~Array~#&,D,#]@#&

Try it online!

Builds \$x!0...x!x\$:

                        D           x => x!0
     f1##&@@f~Array~#&             (x => x!n) => (x => x!(n+1))
Nest[                  , ,#]        x => x!#
                            @#      #!#
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 9 bytes

[ɾ?(⁽*r)t

Try it Online!

-1 thanks to @AUsername

\$\endgroup\$
2
  • \$\begingroup\$ 9 \$\endgroup\$
    – emanresu A
    Jul 13 at 6:46
  • \$\begingroup\$ @AUsername nice didn't know Vyxal has single function reference builtin \$\endgroup\$
    – wasif
    Jul 13 at 7:14
3
\$\begingroup\$

Julia 0.7, 32 29 bytes

-3 bytes by MarcMush.

<(x,n=x)=n>0?prod(1:x.<n-1):x

Try it online!

Or if we are allowed to take the input as it appears in Torian notation itself (essentially twice), then it becomes:

Julia 0.7, 24 bytes

x<n=n>0?prod(1:x.<n-1):x

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ you can use < in your first answer for -3 bytes \$\endgroup\$
    – MarcMush
    Jul 13 at 9:04
  • \$\begingroup\$ Ah, indeed, thanks \$\endgroup\$
    – Kirill L.
    Jul 13 at 10:01
3
\$\begingroup\$

R, 46 bytes

x=scan();i=1:x;prod(i^choose(2*x-i-1,x-1))*!!x

Try it online!

Using formula from tsh's answer (presumably adapted from OEIS page).


Straightforward recursion:

R, 50 bytes

f=function(x,n=x)"if"(n,prod(sapply(1:x,f,n-1)),x)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

’ߥⱮPðṛḷ?

Try It Online!

-1 byte thanks to caird coinherinaahing

This is a singular dyadic link. The challenge requires taking one input; however, a single dyadic chain within a monadic link will have the argument supplied to both sides so this works just fine.

’ߥⱮPðṛḷ?    Dyadic Chain
        ?    If
       ḷ     The left argument is truthy
-----ð       Evaluate on the left argument (this is a variadic chain, and its arity changes between runtimes)
   Ɱ         For each in range on the right argument
--¥          Call as dyad:
’            -  Decrement the left argument
 ß           - Recurse (the `¥` is only necessary to make this act as a dyad since it's a variadic actor)
    P        And take the product
      ṛ      Otherwise, just return x
\$\endgroup\$
1
2
\$\begingroup\$

JavaScript, 38 36 bytes

I still don't understand the challenge but Thanks to Bubbler I understand the challenge a bit better and this port of Alwin's solution seems to work - be sure to +1 them too.

Only handles inputs up to 4 as anything bigger will result in an output exceeding JavaScript's MAX_SAFE_INTEGER

f=(x,n=x)=>n?x?f(x,~-n)*f(~-x,n):1:x

Try it online!

For just one byte more, though, we can handle larger inputs by using BigInts:

f=(x,n=x)=>n?x?f(x,~-n)*f(~-x,n):1n:x

Try it online!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ I'm flattered :) (delete this comment if this is the wrong way to use comments) \$\endgroup\$
    – Alwin
    Jul 13 at 8:32
2
\$\begingroup\$

C (gcc), 51 bytes

f(n){n=g(n,n);}g(x,n){x=n?x?g(x,n-1)*g(x-1,n):1:x;}

Try it online!

Port of Arnauld's JavaScript answer (which may be based on Shaggy's JavaScript answer) which, in turn, is based on Alwin's answer.

\$\endgroup\$
4
  • \$\begingroup\$ Actually, It's my solution that's the port of Alwin's ;) \$\endgroup\$
    – Shaggy
    Jul 13 at 13:55
  • \$\begingroup\$ @Shaggy Fixed! :D \$\endgroup\$
    – Noodle9
    Jul 13 at 14:10
  • \$\begingroup\$ Scratch that, I see now that he beat me to the n?x? version over the original x*n? version by a couple of minutes. \$\endgroup\$
    – Shaggy
    Jul 13 at 14:14
  • 1
    \$\begingroup\$ @Shaggy How's that, all perfectly obscure now? T_T \$\endgroup\$
    – Noodle9
    Jul 13 at 14:18
1
\$\begingroup\$

Charcoal, 22 bytes

≔EN⊕ιθFθUMθΠ…θ⊕λI∧Lθ⊟θ

Try it online! Link is to verbose version of code. Explanation: Port of @Bubbler's answer.

≔EN⊕ιθ

Start with a range from 1 to n.

Fθ

Repeat n times...

UMθΠ…θ⊕λ

... calculate the cumulative products.

I∧Lθ⊟θ

Output the last one, unless n=0, in which case just output 0.

\$\endgroup\$
1
\$\begingroup\$

05AB1E (legacy), 5 bytes

FL}˜P

Port of @Lynn's Jelly answer, so make sure to upvote him/her as well!

Try it online or verify the first \$[0,7]\$ test cases.

Explanation:

F    # Loop the (implicit) input amount of times:
 L   #  Transform each integer `n` into a [1,n] ranged list
     #  (which uses the implicit input in the first iteration)
}˜   # After the loop: flatten the nested lists
  P  # And take the product of all integers
     # (after which the result is output implicitly)

Uses the legacy version of 05AB1E, because the new version's ˜ doesn't work on a single integer for input \$x=0\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.