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

Raku, 25 bytes

{[[&(&[R-])]] [\*] 1..$_}  Try it online! There has got to be a better way of doing that second reduce. For reference, the [op] means reduce, the \ means keep the intermediate values, and the R metaoperator reverses the order of the subtraction. So [\*] the range 1 to input will return a list of factorials from 1 to input. From this we want to fold right over the list with reversed subtraction, which would be [R-] right? However R- also has reversed precedence, so a R- b R- c is equivalent to c - b - a rather than c - (b - a). So we have to make it a function rather than an operator with &[R-], but inserting it into the reduction operator requires an extra pair of []s as well as an &() for some reason (but *R-* also doesn't work for reasons). This bloats it up to the point where reduce &[R-] is now the same length, blergh. Alternatively, we can construct a sequence and index into it: Raku, 30 bytes -1 byte thanks to Steffan {(0,{abs$_-=$*=++$}...*)[$_]}  Try it online! If this IO method ends up allowed as default, then this can be shortened to 23 bytes. • {(0,{abs$_-=$*=++$}...*)[$_]} Apr 20 at 0:45 • @naffetS Nice spot! Doesn't work for the pure sequence version though sadly – Jo King Apr 20 at 0:52 Haskell, 31 bytes x!1=abs x x!y=(1-x*y)!(y-1)  (0!)  Attempt This Online! 05AB1E, 4 bytes L!®β  Port of @JonathanAllan's Jelly answer. Outputting the infinite sequence would be 5 bytes: 0λN!α  Try it online. Explanation: L # Push a list in the range [1, (implicit) input-integer] ! # Get the factorial of each ®β # Convert it from a base-(-1) list to a base-10 integer # (which is output implicitly as result) λ # Start a recursive environment, # to output the infinite sequence # (which is output implicitly at the end) 0 # Start with a(0)=0 # Where every other a(n) is calculated by: # (implicitly push the previous term a(n-1) α # Get the absolute difference between it N! # and n!  Ohm v2, 15 bytes ?@(!1→ρΓ³#R(ⁿ*Σ  Try it online! Ohm is very weird. It thinks that the factorial of 1 is nil, doesn't do base conversion from -1 like other answers and doesn't like formatting numbers correctly sometimes. Explained ?@(!1→ρΓ³#R(ⁿ*Σ ? # only execute this program if the input is not 0 @( # the range 2..input ! # factorial of each 1→ρ # append 1 to that and rotate right. This is because 1! gives nil Γ # Push -1 ³#R( # range(0, n - 1)[::-1] ⁿ # -1 to the power of each of those numbers Σ # summed.  Rust, 54 bytes fn a(n:i64)->i64{if n<2{n}else{n*a(n-2)+(n-1)*a(n-1)}}  All my attempts at golfing this straightforward recursive solution just made the code longer, so I welcome any help! Attempt This Online! Pyth, 5 bytes aF.!S  Try it online! Explanation aF.!SQ # implicitly add Q # implicitly assign Q = eval(input()) SQ # inclusive range from 1 to Q .! # map to factorial aF # fold over the absolute difference  Zsh, 49 bytes r=i=$[$1>0] for n ({$1..2})((r=r*n+(i=-i)))
<<<$r  Try it online! This turned into a super interesting problem, because managing the right base cases for a recursive solution takes too many bytes. Instead, I came up with an equivalent form: $$\mbox{af}(n)=\mbox{af}'(1,-1,n)=\begin{cases} r,i,0 :& 0 \\ r,i,1 :& r \\ r,i,n :& \mbox{af}'(r\cdot n+i,-i,n-1) \end{cases}$$ There's probably a way to make both this form and the program shorter. I had to use r=i=$[$1>0] instead of r=i=1 to get the $$\ n=0 \$$ case, otherwise this program will output -1. Also, you may notice that since my program uses a range between $1 and 2, that it doesn't follow the recursion above for $$\n = 1\$$. It turns out, looping upwards to 2 results in $$\(1\cdot 1 -1)\cdot 2 + 1 = 1\$$, so it all works out okay.

x86-64 machine code, 29 bytes

Uses standard System V ABI with signature long afact(int n). The input n is taken in rdi, and the output is given in rax.

31 c0 85 ff 74 16 ff c0 57 59 48 f7 e1 e2 fb 50 ff cf e8 e9 ff ff ff 48 29 04 24 58 c3


Try it online!

Explanation

The function implements the recurrence relation $$\\operatorname{af}(n)\$$ as given in the question.

afact:
; clear rax
xor eax, eax

; return if n=0
test edi, edi
jz __afact_retn

; factorial first
; set eax to 1
inc eax

; n into rcx
push rdi
pop rcx

; n times:
__afact_flp:
; rax *= n(--)
mul rcx
loop __afact_flp

; n! is in rax
; save it
push rax

; get afact(n-1) in rax
dec edi
call afact

; subtract rax from qword [rsp] (n!)
sub qword [rsp], rax

; pop and return
pop rax

__afact_retn:
ret