# Convert to and from the factorial number system

The Factorial Number System, also called factoradic, is a mixed radix numeral system. The factorials determine the place value of a number.

In this system, the right most digit can be either 0 or 1, the second rightmost digit can be 0, 1 or 2, and so on. This means that an n digit factoradic number can have a maximum value of (n + 1)!.

For example, to convert the factoradic number 24201 to decimal you would do this:

2 * 5! = 240
4 * 4! = 96
2 * 3! = 12
0 * 2! = 0
1 * 1! = 1
240 + 96 + 12 + 0 + 1 = 349


Hence the factoradic number 24201 is 349 base 10.

To convert a decimal number (with 349 as an example) into a factoradic number, you would do this:

Take the largest factorial less than the number. In this case it is 120, or 5!.

349 / 5! = 2 r 109
109 / 4! = 4 r 13
13 / 3! = 2 r 1
1 / 2! = 0 r 1
1 / 1! = 1 r 0


Hence 349 base 10 is the factoradic number 24201.

Your challenge is to create the shortest program or function that converts an input number to the other base.

The input will be a string representation of a non-negative integer. A factoradic number will be preceded by a ! (eg. !24201), while a decimal number will not be preceded by anything. You may assume that the maximum input will be 10! - 1 - 3628799 in decimal and 987654321 in factoradic. This means that letters will not appear in a factoradic input/output.

The program doesn't need to prepend a ! to a factoradic output, and may output a string or an integer. The input may be in any reasonable format.

Test cases:

Input: 1234
Output: 141120

Input: 746
Output: 101010

Input: !54321
Output: 719

Input: !30311
Output: 381


### APL, 39 37 characters

{A B←(9⍴10)(⌽1+⍳9)⌽⍨'!'∊⍵⋄A⊥B⊤⍎⍵~'!'}


Examples:

      {A B←(9⍴10)(⌽1+⍳9)⌽⍨'!'∊⍵⋄A⊥B⊤⍎⍵~'!'}'1234'
141120
{A B←(9⍴10)(⌽1+⍳9)⌽⍨'!'∊⍵⋄A⊥B⊤⍎⍵~'!'}'!54321'
719

• I think you can replace ⍴⍵∩'!' with '!'∊⍵ to save a character. – Volatility May 19 '13 at 23:17
• @Volatility Yes you can. I also found another one. – Howard May 20 '13 at 6:58
• IMO having the word "pwn" in your script is well worth the extra character. – ejrb May 23 '13 at 12:42
• I agree with ejrb. Would you break this down please? – Titus Jul 2 '16 at 13:38
• Replace ~'!' with ∩⎕D to save a character. – Adám Jun 7 '17 at 18:13

## Python 2.7 (163157 152)

i=raw_input()
exec("b='';a=362880;j=int(i);x=9;"+'b+=j//a;j%=a;a/=x;x-=1;'*9,"a=x=1;b=0;"+'b+=a*int(i[-x]);x+=1;a*=x;'*~-len(i))['!'in i]
print int(b)


i=raw_input()
if'!'in i:a=x=1;b=0;c='b+=a*int(i[-x]);x+=1;a*=x;'*~-len(i)
else:b='';a=362880;j=int(i);x=9;c='b+=j//a;j%=a;a/=x;x-=1;'*9
exec c;print int(b)


Breakdown:

Factoradic -> Decimal, when i is in the form !(number)
a=1   #Factorial value (multiplied every iteration)
x=1   #Index value
b=0   #Output
iterate ~-len(i) times:    #PSEUDOCODE! bitwisenot(a) = ~a = -a-1
b+=a*int(i[-x])        #add the value of the xth last character in the factoradic #
x+=1                   #Increment x
a*=x                   #Set a to x!, (x-1)! * x = x!

b=''                       #Output
a=362880                   #Factorial value, set to 9! here
j=int(i)                   #Integer value of the input
x=9                        #Index value
iterate 9 times:           #PSEUDOCODE! This block is in an exec() loop
b+=j/a               #Add floor(j/a) to b
j%=a                   #Take out all multiples of a in j
a/=x                   #Set a to (x-1)!, x! / x = (x-1)!
x-=1                   #Decrement x

• Nice solution. I think you can replace '!'==i[0] with '!'in i, and can use a=x=1. Also, you don't need brackets around the exec statement. – grc May 19 '13 at 3:52
• You could also replace (len(i)-1) with ~-len(i). – Volatility May 19 '13 at 4:11
• @Volatility, grc: Thanks! I should learn my bitwise operators :) – beary605 May 19 '13 at 5:48
• Nice answer, I took the liberty of trying to replace the if statement with (a,b)['!'in i] and managed to shave off 6 characters. It's not as readable as it was though... pastebin link – ejrb May 20 '13 at 12:15
• @erjb: Thanks for the suggestion! I used a 2-tuple with the code as a string in-line with the exec function, which saves two more characters :) – beary605 May 20 '13 at 21:18

## GolfScript (48 44 43 chars)

.~\{1{):?\.?%\?/@}9*{*+}+9*}:^{:N,{^N=}?}if


This is a self-contained program. The factoriadic => decimal conversion is quite slow, because it does a search using the decimal => factoriadic conversion rather than a direct base conversion.

The input format allows for a very short mode switch: .~ copies the input string and evaluates it, so if the input is just a number we end up with e.g. "1234" 1234 on the stack, and if it starts with ! (logical not, with any non-empty string being truthy) we end up with e.g. 0 30311 on the stack. Then the value at the bottom of the stack is truthy for decimal => factoriadic and falsy for factoriadic => decimal.

# PHP <7.1 178 171 170 168 164 155 147 144 138 126 123 bytes

for($b=$j=1,$i=strlen($x=$argn);+$x?$b<=$x:--$i;$b*=++$j)$r+=$x[$i]*$b;if(+$x)for(;$j>1;$x%=$b)$r.=$x/($b/=$j--)|0;echo+$r;


Run as pipe with -r or test it online.

• no extension required
• no sub function needed: the factorial base is being reused (incresed/decreased in the loops)
• pure integer and string arithmetics, should even work in php 3 (and still works in php 7):
• decimal 0 returns empty string instead of 0. (both other PHP answers do too.) If that is unacceptable, add +5 for the extra case.

ungolfed:

// two loops in one: compute the decimal number from a factorial
// or find the first factorial larger than a decimal $x // the latter inits$r with '0': $i=strlen ->$x[$i]=='' -> (int)$x[$i]==$x[$i]*$b==0
// $b is the current digit´s base;$j is the bases´ latest factor
for($b=$j=1,$i=strlen($x=$argn);+$x?$b<=$x:--$i;$b*=++$j)$r+=$x[$i]*$b; // and now for dec->fact ... if(+$x)
for(;$j>1;$x%=$b) // both$b and $j are one step too far in the first iteration; // -> decrement must precede the actual loop body // -> can be merged into the digit calculation -> all braces golfed$r.=$x/($b/=$j--)|0; // now: go on with the remainder (see loop head) echo+$r; // final type cast removes leading zeros (from the first loop)
// and fixes the '0' result (no operations at all on that input!)


abandoned golfing ideas:

• $b<=$x --> $b<$x (-1)
would break pure decimal factorials (i.e. those that result in a factorial number with only one non-zero digit). JMPC´s solution suffers from that; HamZa´s does not.
• floor($x/$b) -> (int)($x/$b)
could be a bit faster, but type casting precedes division, so I need the parentheses and don´t gain a byte.
$x/$b|0 does the trick
• The loop in fact->dec is similar to the factorial-find in dec->fact. Same increment, body does not matter, but unfortunately different preset and different post condition. Dang; could have golfed -21 there.
YAY I found a solution. Took quite a bit of golfing, but chopped off another -4 (no: -9) and closed all bugs/loopholes.

Any more potential ... or am I done golfing?

• @JörgHülsermann Thanks for the hint. – Titus Jun 7 '17 at 17:49
• +$r instead of $r|0 save one byte. Same for if($x|0) – Jörg Hülsermann Jun 7 '17 at 21:06 # JavaScript (ES 6) 139 137 122 113 111 tried a different approach using some array magic; but I ended up at 174 172 bytes with that: f=x=>{if('!'==x[0]){a=x.split.reverse();i=b=1;r=0;a.pop();a.map(d=>{r+=d*b;b*=++i})}else{t=[];for(i=b=1;b<=x;b*=++i){t.unshift(b)}r='';t.map(b=>{r+=x/b|0;x%=b})}return r}  So I just took my PHP code and translated it. Could remove all the $s and a few ;, but the necessity to initialize vars ate up some of that benefit. Managed to golf both answers down a bit further, though.

golfed

f=x=>{for(r=0,b=j=1,i=x.length;x|0?b<=x:--i;b*=++j)r+=x[i]*b;if(x|0)for(r='';j>1;x%=b)r+=x/(b/=j--)|0;return r}

• first version returns '' for decimal 0; add +2 to fix
• second version requires string input
• both tested in Firefox, Edge and Opera

ungolfed

f=x=>
{
for(r=0,b=j=1,i=x.length;x|0?b<=x:--i;b*=++j)
r+=x[i]*b;
if(x|0)
for(r='';j>1;x%=b)
r+=x/(b/=j--)|0;
return r
}


test suite

<table id=out border=1><tr><th>dec</th><th>result<th>expected</th><th>ok?</th></tr></table>
<script>
samples={'349':'24201','1234':'141120','746':'101010','719':'54321','381':'30311','24':'1000','0':'0'};
for(d in samples){test(d,samples[d]);test('!'+samples[d],d)}
</script>

• ES5 doesn't have arrow notation IIRC. And if you're going to use ES6, then .split('') => .split – Zacharý Jul 11 '17 at 19:58
• @Zacharý Gna I should have noted what browser I tested it in ... probably Firefox or Opera. So ES 6? – Titus Jul 11 '17 at 20:03
• Yeah, arrow notation is ES6. – Zacharý Jul 11 '17 at 20:05
• Oh, that caught me off guard, I thought the code block at the top was your solution! Regardless, I don't think you need to say f=. Also, can r+=(x/(b/=j--)|0) be r+=x/(b/=j--)|0? – Zacharý Jul 12 '17 at 12:38

# Perl 6, 6665 60 bytes

-1 byte thanks to Jo King

{/\!/??:1[.flip.chop.comb Z*[\*] 1..*]!![R~] .polymod(2..*)}


Try it online!

### GolfScript, 69 characters

10,1>{1$*}*](.0=33={1>01/-1%0\{~@(@*@+}/\}{~\-1%{1$<},{1$1$/@@%}/}if;


Takes input from STDIN as usual and prints the result. Online test.

m v@(a:b)|a=='!'=(sum.zipWith(*)g.map(read.(:[])).reverse) b|True=(fst.until((<0).fst.snd)(\(s,(i,b))->(s*10+bquotf i,(i-1,bremf i))).(\n->(0,((1+).last.takeWhile((n>=).f)$[1..], n))).read) v;g=scanl1(*)[1..];f=(g!!)  ### Usage $ ghci factorial.hs
ghci> m "1234"
141120
ghci> m "!54321"
719


### Ungolfed code

parse v@(a:b) | a == '!' = to b
| otherwise = from v

to = sum . zipWith (*) factorials . map (read . (:[])) . reverse

from = fst . until finished next . boostrap . read
where finished = ((<0) . fst . snd)
next (s,(i,r)) = (s * 10 + r quot factorial i, (i-1 ,r rem factorial i))
bootstrap n = (0, (lastFact n, n))
lastFact n = (1+) . last . takeWhile ((n>=) . factorial) $[1..] factorials = scanl1 (*) [1..] factorial = (factorials!!)  • By far the most readable entry. Haskell FTW! – Soham Chowdhury May 23 '13 at 1:57 # Mathematica 213 177 175 A factorial number is wrapped in f[], whether it is input or output. g@{n_,j_,r_}:=If[j==0,FromDigits@r,g@{q=QuotientRemainder[n,j!];q[[2]],j-1,Append[r,q[[1]]]}] z@n_:=If[!IntegerQ@n, g[{n[[1]],9,{}}], f@Tr@(p=1;# (p++)!&/@Reverse@IntegerDigits@n)]  Usage z[24201]  f[349] z[f[349]]  24201 Conversion of factorial to decimal number. QuotientRemainder[n,j!] recursively acts on the digits of the factorial number from left to right, decrementing j at each step. QuotientRemainder[349, 5!], for instance, returns {2, 109} and so on. Conversion of decimal to factorial number. Moving right to left, the pure function, # (p++)! &, multiplies each digit,#, by the appropriate factorial. ## Python, 128 chars This takes about half an hour to run, but it's small: A=[xfor x in xrange(10**9)if all(x/10**d%10<d+2 for d in range(9))] i=raw_input() print A.index(i[1:])if'!'in i else A[int(i)]  It builds a list of all <= 9 digit factoradic numbers in numeric order, then does a lookup or index to convert. If you want to test, just replace 10**9 with 10**6 and restrict yourself to 6-digit variadic numbers. I could technically save a character by using range(10**9) instead of xrange(10**9). Don't try this at home. • No space is needed between d+2 and for – Zacharý Jul 11 '17 at 20:06 # PHP 231214 204 Newest Answer function g($x){return $x?$x*g($x-1):1;}function f($x,$e){if($x[0]=="!"){for($t=1;$t<$c=strlen($x);$t++){$e+=$x[$t]*g($c-$t);}}else{while(g(++$p)<=$x);while(--$p){$e.=floor($x/g($p));$x%=g($p);}}return$e;}  Old Answer  function f($n){if($n[0]=="!"){$n=str_split($n);$c=count($n);$f=$y=1;while($c-->1){$e+=($f*$n[$c]);$f*=++$y;}return$e;}else{for($i=$c=1;$i<$n;$i*=$c){$r[$c++]=$i;}foreach(array_reverse($r)as$t){$e.=floor($n/$t);$n=$n%$t;}return$e;}}  ### Example echo f('349')."\n" .f('!24201')."\n" .f('1234')."\n" .f('746')."\n" .f('!54321')."\n" .f('!30311');  ### Output 24201 349 141120 101010 719 381  • I count 212 for the new answer, not 214.$e needs no initialization (-6) and the foreach(range()) can be replaced with a simple for loop (-9). I like the idea, though. – Titus Jul 2 '16 at 14:00
• wrong result for pure factorials. 24 should return 1000 but returns 400. fix: g(++$p)<$x --> g(++$p)<=$x (+1) – Titus Jul 4 '16 at 14:29
• @Titus Thanks for both of your replies! I updated my answer. I appreciate you helping me improve my answer when yours seems far superior. – JPMC Jul 5 '16 at 14:52
• 1) I count 2 less than you, again: 204, not 206. Do You include a Windows line break in your byte count? 2) syntax error in for construct: , should be ; 3) I have another 7 changes saving 20 bytes on that code. Want them? – Titus Jul 5 '16 at 20:27
• Well, it´s actually only 5 changes, but one of them has three parts. a) obsolete second argument for f() (-3) b) obsolete blank in function g (-1) c) obsolete braces in the true branch (-4) d) swap true and false branches, invert the if condition, then use my sexy type cast to int (-6) This will not affect the decimal 0 result! e) the remaining for construct can be rewritten with a very nice while(++$t<$c=strlen($x)): increment before body -->$t needs no initialization (-6) – Titus Jul 5 '16 at 21:26

# JELLY, 5 bytes

Æ!ŒṘ€


Explanation

Æ!ŒṘ€
Æ!     -Convert to factoriadic (list form)
ŒṘ€  -Construct string


*Jelly is younger than the age of the question therefore my answer is noncompeting.

• Welcome to PPCG! I think Jelly is younger than this challenge, hence you should mark your answer as non-competing. – Laikoni Jun 7 '17 at 16:11
• Oh I didn't realize that that was a rule. Will do. – DaggerOfMesogrecia Jun 7 '17 at 16:35
• Aren't answers to this challenge meant to work both ways? This only seems to work one way; you might want to fix that. (On a separate note, if you're converting between integers and strings in Jelly, it's normally tersest to use some combination of V and Ṿ.) – user62131 Jun 8 '17 at 1:51

# Jelly, 15 bytes

ḊV€;0Æ¡µÆ!ṖḌƊ¬?


Try it online!

### How it works

ḊV€;0Æ¡µÆ!ṖḌƊ¬?     Main link (monad). Input: integer or string
¬?  *) If the given input is a string, run 1); otherwise run 2)

ḊV€;0Æ¡  1) Factorial base -> integer
ḊV€         Remove "!" and map each char to number
;0       Append zero (this is needed to run the built-in correctly)
Æ¡     Built-in conversion

Æ!ṖḌ  2) Integer -> factorial base
Æ!       Built-in conversion
ṖḌ     Remove a zero at the end, and convert to decimal


### Why *) works

¬ is element-wise logical NOT. When given a single integer, it becomes a single zero, which is false. However, when given a string, each element (character) is turned to a zero, and the whole result is an array of zeroes which is true.

Zero as an integer is a special case. It goes through the "factorial -> integer" route, but it still gives zero which is correct.

# Without factorial base built-in, 25 bytes

⁵R!µ³%Ḋ:ṖUḌ
⁵R!ḋḊUV€ƊµÇ¬?


Try it online!

### How it works

⁵R!µ³%Ḋ:ṖUḌ  Aux. link (monad). Integer -> factorial base
⁵R!µ         Set (1..10)! as left argument
³%Ḋ:Ṗ    Compute each digit: (input % (2..10)!) // (1..9)!
UḌ  Reverse and convert the digit array to decimal

µÇ¬?  If the input is a string, apply the left chain;
otherwise, apply the aux. link above
⁵R!            (1..10)!
ḋ           Dot product with...
ḊUV€Ɗ      Remove "!", reverse, map each character to digit


# K, 102

"I"$,/$*:'|:'{{(x-y*g),g:_(x:*x)%y:*/1+!y}\[x,0n;|1+!{$[(x>(*/1+!y))&x<*/1+!y+1;y;.z.s[x;1+y]]}[x;0]]}  Could definitely be improved. k)"I"$,/$*:'|:'{{,[;g]x-y*g:_(x:*x)%y:*/1+!y}\[(x;0n);|1+!{{$[(x>(*/1+!y))&x<*/1+!y+1;y;.z.s[x;1+y]]}[x;0]}x]} 349
24201
k)"I"$,/$*:'|:'{{,[;g]x-y*g:_(x:*x)%y:*/1+!y}\[(x;0n);|1+!{{$[(x>(*/1+!y))&x<*/1+!y+1;y;.z.s[x;1+y]]}[x;0]}x]} 746 101010 k)"I"$,/$*:'|:'{{,[;g]x-y*g:_(x:*x)%y:*/1+!y}\[(x;0n);|1+!{{$[(x>(*/1+!y))&x<*/1+!y+1;y;.z.s[x;1+y]]}[x;0]}x]} 1234
141120


# D (159 chars)

int x(string n){import std.conv;int r,i=9,f=9*'鶀',d;if(n[0]<48){while(r.text.x<n[1..$].to!int)r++;}else{d=n.to!int;while(i){r=r*10+d/f;d%=f;f/=i--;}}return r;}  ## Ungolfed and with program entry point All command line arguments are printed as <original> -> <converted>. Only decimal to factoradic is actually implemented in x. The other way round just calls x with all decimal numbers (0..*) until the result equals the input. This takes ~3 seconds for the largest input (!987654321). Executable online version: http://dpaste.dzfl.pl/46e425f9 void main(string[] args) { import std.stdio; foreach (arg; args[1 ..$]) {
writefln("%s -> %s", arg, x(arg));
}
}

int x(string n) {
import std.conv;
int r, i=9, f=9*'鶀', d;  // 鶀's Unicode index equals 8*7*6*5*4*3*2*1

// If the first character value is less than 48 ('0') it should be a '!'.
if (n[0] < 48) {
// Call x with different input (0..*) until it matches our n.
// r.text.x is rewritten as x(text(r)).
while (r.text.x < n[1..$].to!int) r++; } else { d = n.to!int; // Try d / 9!, d / 8!, etc. just as in the problem description. while (i) { r = r*10 + d/f; d %= f; f /= i--; } } return r; }  • I think it might be possible to change string n to char[]n to save one byte (I know I'm late here). – Zacharý Jul 12 '17 at 12:42 • Also, I think if(n[0]<48){while(r.text.x<n[1..$].to!int)r++;} can become if(n[0]<48)while(r.text.x<n[1..$].to!int)r++; to save two bytes. – Zacharý Jul 12 '17 at 12:47 ## VBA 225 Thanks to Titus for the help! Still looking to golf some more. Sub a(b) Set w=WorksheetFunction e=Len(b) If IsNumeric(b) Then i=0 For d=0To 8 h=w.Fact(9-d) g=b Mod h If g<b+i Then i=1 f=f &Int(b/h) b=g End If Next Else For d=2To e f=f+w.Fact(e-d-1)*Mid(b,d,1) Next End If MsgBox f End Sub  • I don´t know VBA, but is there a way to check b for a numeric value instead of comparing the first character? – Titus Jul 3 '16 at 13:20 • @Titus There is a numeric check, and the equivalent here would be: If Not IsNumeric(b) Then, but that takes more characters. Now, I didn't go in and re-examine all the code; there may be a slightly better way to do this with IsNumeric overall. -- Correction, there is a slight improvement here. Thanks! – Gaffi Jul 3 '16 at 13:44 • I found another four bytes: For d=9To 1Step-1 and Fact(d) --> For d=0To 8 and Fact(9-d) and another two if you do For d=2To e and Fact(e-d+1)*Mid(b,d,1) – Titus Jul 3 '16 at 14:00 • Can the type cast to Int be written in another way? – Titus Jul 3 '16 at 14:02 • @Titus Look at you, running circles around me. :) I'm tweaking now... As for Int(), I don't think there is a simpler(smaller) method, no. – Gaffi Jul 3 '16 at 14:06 # PHP, 124 bytes for($f=1;("$">$a=$argn)&&~$c=strrev($a)[$n];)$r+=$c*$f*=++$n;for(;$a>=$f*=++$i;);for(;~-$i;$a%=$f)$r.=0|$a/$f/=$i--;echo+$r;  Try it online! Extended for($f=1;("$">$a=$argn)&&~$c=strrev($a)[$n];) # runs in case of "!" at the beginning
$r+=$c*$f*=++$n; #reverse string multiply with the next factorial "!"*$f=0 for(;$a>=$f*=++$i;); # runs not in case of "!" at the beginning string comparing. search the factorial that is higher as input value
for(;~-$i;$a%=$f) # runs only when the second loop had runs$r.=0|$a/$f/=$i--; # concat the value of the division with the highest factorial used echo+$r; # Output result


# Perl 6, 150 bytes

{/^\!/??([+] [Z*] .comb.skip.reverse,[\*] 1..*)!!(reduce
->\a,\b{a[0]~a[1] div b,a[1]%b},("",+$_),|(first *[*-1]>$_,[\,] [\*] 1..*).reverse[1..*])[0]}


# APL(NARS), 36 chars, 72 bytes

{⍵⊆⎕D:10⊥(9..2)⊤⍎⍵⋄t+.×⌽!⍳≢t←⍎¨,1↓⍵}


it seems that 10⊥(9..2)⊤ is better than the recursive function, thanks to Howard for the other APL solution that show that... (even if i not understand 100%). Input for numbers without '!' <10!. Test:

  u←{⍵⊆⎕D:10⊥(9..2)⊤⍎⍵⋄t+.×⌽!⍳≢t←⍎¨,1↓⍵}
u¨'1234' '746' '!54321' '!30311' '!24201'
141120 101010 719 381 349
u '0'
0
u '!0'
0
u '9'
111
u '!111'
9
u '!9'
9