25
\$\begingroup\$

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.

Task

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
Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Please add a plain English explanation and a worked example. \$\endgroup\$
    – Shaggy
    Apr 16 at 0:42
  • \$\begingroup\$ @Shaggy I took a stab at it. \$\endgroup\$
    – chunes
    Apr 16 at 7:11
  • \$\begingroup\$ Can you check if the recurrence relation stated is correct? Because I’m not sure it is. \$\endgroup\$
    – The Empty String Photographer
    Apr 16 at 11:00
  • 1
    \$\begingroup\$ @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)\$). \$\endgroup\$
    – Jonathan Allan
    Apr 16 at 15:54
  • \$\begingroup\$ @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. \$\endgroup\$
    – justhalf
    Apr 17 at 8:53

38 Answers 38

Reset to default
1
2
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ {(0,{abs $_-=$*=++$}...*)[$_]} \$\endgroup\$
    – naffetS
    Apr 20 at 0:45
  • \$\begingroup\$ @naffetS Nice spot! Doesn't work for the pure sequence version though sadly \$\endgroup\$
    – Jo King ♦
    Apr 20 at 0:52
2
\$\begingroup\$

Haskell, 31 bytes

x!1=abs x
x!y=(1-x*y)!(y-1)

(0!)

Attempt This Online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 4 bytes

L!®β

Port of @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

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!
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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