# Alternating factorial

The alternating factorial is an alternating sum of decreasing factorials. For example, we could calculate the alternating factorial of 4 as follows:

• First, calculate the factorials from 4 down to 1:

$$4!\quad3!\quad2!\quad1!\quad = \\ 4\cdot3\cdot2\cdot1\qquad3\cdot2\cdot1\qquad2\cdot1\qquad1\quad= \\ 24\quad6\quad2\quad1$$

• Next, insert alternating signs between the products, always starting with $$\\;-\$$.

$$24-6+2-1 = \\ 19$$

So 19 is the alternating factorial of 4. Mathematically, the alternating factorial is defined as $$\large\operatorname{af}(n) = \sum_{i=1}^n(-1)^{n-i}i!$$

For example, $$\operatorname{af}(4)=(-1)^3\times1!+(-1)^2\times2!+(-1)^1\times3!+(-1)^0\times4!=19$$ The alternating factorial can also be calculated by the recurrence relation $$\operatorname{af}(n) = \begin{cases} 0, & \text{if \;n=0} \\ n!-\operatorname{af}(n-1), & \text{if \;n>0} \end{cases}$$ The sequence of alternating factorials is OEIS A005165.

Given a non-negative integer as input, output its alternating factorial. You don't need to worry about values exceeding your language's integer limit. This is , so the code with the fewest bytes (in each language) wins.

## Test cases

n   af(n)
0   0
1   1
2   1
3   5
4   19
5   101
6   619
7   4421
8   35899
9   326981

• Please add a plain English explanation and a worked example. Apr 16 at 0:42
• @Shaggy I took a stab at it. Apr 16 at 7:11
• Can you check if the recurrence relation stated is correct? Because I’m not sure it is. Apr 16 at 11:00
• @Hippopotomonstrosesquipedalian It's correct, just note how the last summand, when $i=n$ is $(-1)^{(n-n)}n! = (-1)^{0}n!=n!$ and by removing it we're left with $-\operatorname{af}(n-1)$ (since the remaining signs are in the other alternating order to that of $\operatorname{af}(n-1)$). Apr 16 at 15:54
• @Hippopotomonstrosesquipedalian the alternating is counted from the n downwards, not from 0 upwards, so, e.g., the role of 1! to the result will alternate with odd and even n too. Apr 17 at 8:53

# Jelly, 4 bytes

R!ḅ-


A monadic Link that accepts a non-negative integer, $$\n\$$, and yields its alternating factorial.

Try it online!

### How?

R!ḅ- - Link: n
R    - range (n) -> [1, ..., n-1, n]
!   - factorial -> [1!, ..., (n-1)!, n!]
- - -1
ḅ  - convert from base -1 -> n! - (n-1)! + ... [+/-] 1!

• ...right, of course, base $-1$ does alternating sum, I always forget that :/ Apr 15 at 22:39

# Wolfram Language (Mathematica), 20 bytes

AlternatingFactorial


Try it online!

• I use Mathematica all the time and even I'm sometimes surprised by the builtins ... this sounds like a joke but it's not! Apr 16 at 20:55

# APL(Dyalog Unicode), 6 bytes SBCS

¯1⊥∘!⍳


Try it on APLgolf!

# Desmos, 28 bytes

f(k)=∑_{n=1}^k(-1)^{k-n}n!


Try It On Desmos!

Yea, I really could not think of any golfier way than to just copy the formula provided in the question. Not the most creative answer out there but at least it's the golfiest in Desmos (at least it better be....).

# ><> (Fish), 53 42 bytes

i:?vl1=?n-30.
:?v\:1$:@*$1-
1.\6
00.\~~$1-  Try it The bottom 3 lines calculate the factorial of a number and push it to the stack, the top line just subtracts the top 2 elements from the stack, and prints the top of the stack if there is just one. After a number is printed, the - crashes and the program exits. # Wolfram Language (Mathematica), 20 bytes Nest[++i!-#&,i=0,#]&  Try it online! • Ties with the built-in! Apr 16 at 17:20 • @TheThonnu Yes, in Mathematica there are many ways to code, between self-explained but long keywords to cool golfed versions Apr 16 at 17:28 # Python, 40 bytes f=lambda n:n>1and~-n*f(n-1)+n*f(n-2)or n  Attempt This Online! Port of @Arnauld's JS answer. # JavaScript (ES6), 28 bytes f=n=>n<2?n:n*f(n-2)+--n*f(n)  Try it online! This is based on the recurrence formula given on OEIS for $$\n > 1\$$: $$a(n) = n\times a(n-2) + (n-1)\times a(n-1)$$ This alternate form accepts either Numbers or Bigints as input: f=n=>n<2?n:n--*f(~-n)+n*f(n)  Try it online! • Is there a reason to use ~-n instead of n-1? Apr 16 at 12:05 • @Jacob Only for BigInt compatibility. It would be n-1n otherwise. Apr 16 at 13:01 # Curry (PAKCS), 48 bytes f 0=1 f x|x>0=x*f(x-1) g 0=0 g x|x>0=f(x)-g(x-1)  Try it online! My first answer in Curry. I had to determine the factorial because I couldn’t find it in the standard library # R, 29 31 bytes Edit: +2 bytes and complete change of approach to fix bug spotted by pajonk \(x)Reduce(-,gamma(x:1+1),,T)  Attempt This Online! • This doesn't match the test-case for 1. Apr 16 at 11:32 • @pajonk - Drat! Well spotted. Hopefully fixed now (with complete re-think...) Apr 16 at 16:12 # Thunno 2, 6 bytes RR€puḋ  (Thunno 2 isn't on ATO yet) It seems that I forgot to add a "factorial" built-in to Thunno 2... Port of Jonathan Allan's Jelly answer. #### Explanation RR€puḋ # Implicit input 5 R # Push the range [1..input] [1, 2, 3, 4, 5] R # For each number in this, push its range [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]] €p # Product of each inner list [1, 2, 6, 24, 120] uḋ # Convert from base -1 101 # Implicit output  # MATL, 7 bytes :Yp-1ZQ  Try it online! • Cumulative product and evaluate polynomial, good idea! Apr 16 at 23:46 # Oasis, 4 bytes n!-0  Try it online. Explanation:  0 # Start with a(0)=0 (Oasis programs implicitly start with a(0)=1 unfortunately) # And calculate every following a(n) by: - # Subtracting # the implicit previous term a(n-1) n! # from n! # (and output the a(implicit input-argument)'th term implicitly as result)  # Nibbles, 5.5 5 bytes (10 nibbles) Edit: -0.5 bytes (1 nibble) thanks to xigoi /.\,$*,$-  Attempt This Online! Port of my R answer. /.\,$/,$*- . # map over \ # reverse of ,$       # 1..input:
*     #   product of
,$# 1..each element # (at this point we have list of # factorials in reverse order); / # now, fold over this from right to left - # by subtraction  • You can use *,$ instead of /,$*. ato.pxeger.com/… Apr 17 at 9:11 • @xigoi - Oh, yes, thanks. Somehow I always forget that  * exists (or maybe using Nibbles for a bit has made me think of folds for almost everything)... Apr 17 at 9:47 • @xigoi - How do you put * into a codeblock in a comment, anyway? Apr 17 at 9:49 • Found it: If a backtick is somewhere in the middle, you can use double enclosing backticks: likethis, resulting in likethis. If it's at the start or end, you can use singular enclosing backticks, and escape the backticks within the code: \like\this\, resulting in likethis. So the comment *,$ is accomplished with \*,$. Apr 17 at 10:03 • There is even a challenge about it. codegolf.stackexchange.com/questions/17650/… Apr 17 at 15:18 # Brain-Flak, 64 bytes {(({})[()]<({([{}]()({}))([{}]({}))}{}{}([{}])((){}))>)}{}({}<>)  Try it online! This does not compute any factorials as intermediate results. Instead, it multiplies by successively smaller numbers and either adds or subtracts one. Sample calculation for the alternating factorial of 5: 0 *6 +1 = 1 1 *5 -1 = 4 4 *4 +1 = 17 17 *3 -1 = 50 50 *2 +1 = 101  • Wow, that's a clever and efficient way to calculate it! Apr 17 at 20:11 # Jelly, 6 bytes R!_@ƒ0  Try it online! ## How it works R!_@ƒ0 - Main link. Takes n on the left R - Range; [1, 2, ..., n] ! - Factorial; [1, 2, 6, ..., n!] ƒ0 - Reduce by the following, beginning with 0: _@ - y - x  For a list [a, b, c, d, e], _@ƒ0 calculates ((((0 _@ a) _@ b) _@ c) _@ d) _@ e = e _ (d _ (c _ (b _ (a _ 0)))) = e - d + c - b + a - 0  # Vyxal, 4 bytes ɾ¡uβ  Try it Online! Port of the 4 byte jelly answer ## Explained ɾ¡uβ ɾ # range [1, n] ¡ # factorial of each uβ # converted from base -1  # Pyt, 10 bytes řĐ1~⇹^⇹!·Å  Try it online! ř implicit input (n); řangify [1,2,...,n] Đ Đuplicate 1~ -1 ⇹ swap top two elements ^ -1^[1,2,3,...,n] ⇹ swap top two elements ! factorial [1!,2!,3!,...,n!] · dot product Å Åbsolute value; implicit print  Uses that fact that $$\\text{af}(n)=\left|\sum_{i=1}^n(-1)^i i!\right|\$$ # Retina, 54 bytes ~(.+ .+¶$$.($$'$&*
+_(_(_+))
$$(.&*2.1*1) __ _  Try it online! Link includes test cases. Explanation: Port of @Arnauld's JavaScript answer. ~(  Run the output of the rest of the program on the original input. .+ .+¶$$.($$'&*  Convert the input to unary and replace it with a command that replaces the input with an expression that converts the literal unary string back to decimal. The unary string represents f(n) at this point. +_(_(_+))$$($.&$*$2$.1$*$1)


For n>2, repeatedly apply the recurrence relation f(n)=n*f(n-2)+(n-1)*f(n-1) to the unary string. n and (n-1) are represented in decimal while f(n-2) and f(n-1) remain represented in unary for the next pass.

__
_


f(2)=1 while f(n)=n for n<2 which is already correct.

Example: if n=7, then the rest of the program produces the following output:

.+
$.($'$(7*$(5*$(3*_2*_)4*$(4*_3*$(3*_2*_)))6*$(6*$(4*_3*$(3*_2*_))5*$(5*$(3*_2*_)4*$(4*_3*$(3*_2*_)))))


Retina will evaluate the expression using big integers so the limit is the length of the generated expression which has to fit in memory.

Note that there's an extra $' in the final expression in case it is empty to work around a Retina bug whereby $.() crashes Retina when it has no elements, but it's fine if it has a non-zero number of empty elements.

The recurrence relation is not used for f(2) because that would invoke f(0) whose representation would be empty, but * defaults to a RHS of _ i.e. 1. It could be done by representing f(n) with $(n) except that this triggers the empty length bug, so it needs another 3 bytes for a second copy of the workaround, making it overall a byte longer: .+ .+¶$$.($$'$&*
~)+_(_(_*))
$.&$*$$($$'$2)$.1$*$$($1)


# Excel, 38 bytes

Defined Name a:

=LAMBDA(n,IF(n,FACT(n)-a(n-1),))


After which, within the worksheet:

=a(A1)


for an input in cell A1.

# Japt, 4 bytes

õÊìJ


Try it

õÊìJ     :Implicit input of integer U
õ        :Range [1,U]
Ê       :Factorials
ì      :Convert from base
J     :-1


# Brachylog, 11 bytes

0|-₁↰I&ḟ;I-


Try it online!

### Explanation

Uses the recurrence relation.

0             af(0) = 0
|            Or
-₁↰I        I = af(Input - 1)
&ḟ;I-   Output = Input! - I


# Julia 0.7, 23 bytes

!n=n>0?prod(1:n)-!~-n:0


Try it online!

Uses the recursive formula.

• -1 byte (and also works with Julia 1.0) !n=n>0&&prod(1:n)-!~-n Apr 22 at 23:22

# Pip, 17 16 12 bytes

$* *\,\,aFDv  Attempt This Online! Port of Jonathan Allan's Jelly answer. -4 thanks to @DLosc #### Explanation $* *\,\,aFDv   ; Input on command line
\,a      ; Range from 1 to input
\,         ; Range from 1 to each
$* * ; Product of each inner list FDv ; From a list of digits in base -1 ; Implicit output  Old: ({$*\,a}M\,a)FDv   ; Input on command line
\,a       ; Range from 1 to input
{     }M          ; Map over this list:
\$*               ;   Product of...
\,a            ;   ...range from 1 to the number
(           )FD    ; Convert from a list of digits...
v   ; ...in base -1
; Implicit output

• @DLosc thanks, updated Apr 19 at 6:32

# Charcoal, 12 bytes

Ｉ↨ＥＮΠ…¹⁺²ι±¹


Attempt This Online! Link is to verbose version of code. Explanation:

   Ｎ            First input as a number
Ｅ             Map over implicit range
…          Range from
¹         Literal integer 1 to
ι      Current value
⁺        Plus
²       Literal integer 2
Π           Take the product
↨        ±¹    Interpret as base -1
Ｉ               Cast to string
Implicitly print


# J, 10 bytes

_1#.1!@+i.


Port of Jonathan Allan's smart Jelly answer.

Attempt This Online!

_1#.1!@+i.
i.  NB. range [0,n)
1  +    NB. vectorized increment
!@     NB. factorial of each
_1#.        NB. convert from base -1


# minigolf, 23 22 bytes

Ti,n;o,T*:1n,n*_*;+s,_


Attempt This Online!

## Explanation

T            Push -1 (b)
i,n;         [1..n] range of input
o            Reverse it
,            Map in [n..1]:
T*:          Multiply (b) by -1 (since -1^0 = 1
1            Push 1
n            Push curr. item
,n*_         Reduce 1..n by product
*            mul. w/ b
;            End map
+            sum (works for 0 case since sum of [] is 0)
s,_          drop b

implicit output


# PARI/GP, 40 35 bytes

saved 5 bytes thanks to the comment.

Try it online!

f(n)=abs(sum(m=1,n,prod(k=1,m,-k)))

• A port of @KiptheMalamute's Pyt answer is only 35 bytes: f(n)=abs(sum(m=1,n,prod(k=1,m,-k))).
– Neil
Apr 16 at 8:42

# C (gcc), 32 bytes

f(n){n=n<2?n:n*f(n-2)+f(--n)*n;}


Try it online!

# FunStack alpha, 39 bytes

Minus foldl 0 Product map IFrom1 IFrom1


Try it at Replit!

### Worked example

                4
IFrom1          [1,2,3,4]
IFrom1          [[1],[1,2],[1,2,3],[1,2,3,4]]
Product map     [1,2,6,24]
Minus foldl 0   19


where the last bit is

Minus          Subtract first argument from second
foldl    Left-fold on that function
0  starting with an accumulator value of 0


and so our result is -(-(-(-0+1)+2)+6)+24 = 19.