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
\$\endgroup\$
5
  • \$\begingroup\$ Please add a plain English explanation and a worked example. \$\endgroup\$
    – Shaggy
    Apr 16, 2023 at 0:42
  • \$\begingroup\$ @Shaggy I took a stab at it. \$\endgroup\$
    – chunes
    Apr 16, 2023 at 7:11
  • \$\begingroup\$ Can you check if the recurrence relation stated is correct? Because I’m not sure it is. \$\endgroup\$ Apr 16, 2023 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\$ Apr 16, 2023 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, 2023 at 8:53

38 Answers 38

10
\$\begingroup\$

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!
\$\endgroup\$
1
  • 5
    \$\begingroup\$ ...right, of course, base \$-1\$ does alternating sum, I always forget that :/ \$\endgroup\$ Apr 15, 2023 at 22:39
8
\$\begingroup\$

Wolfram Language (Mathematica), 20 bytes

AlternatingFactorial

Try it online!

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

APL(Dyalog Unicode), 6 bytes SBCS

¯1⊥∘!⍳

Try it on APLgolf!

\$\endgroup\$
6
\$\begingroup\$

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....).

\$\endgroup\$
0
6
\$\begingroup\$

><> (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.

enter image description here

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

Wolfram Language (Mathematica), 20 bytes

Nest[++i!-#&,i=0,#]&

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Ties with the built-in! \$\endgroup\$
    – The Thonnu
    Apr 16, 2023 at 17:20
  • 2
    \$\begingroup\$ @TheThonnu Yes, in Mathematica there are many ways to code, between self-explained but long keywords to cool golfed versions \$\endgroup\$
    – lesobrod
    Apr 16, 2023 at 17:28
4
\$\begingroup\$

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.

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ Is there a reason to use ~-n instead of n-1? \$\endgroup\$
    – noodle man
    Apr 16, 2023 at 12:05
  • 1
    \$\begingroup\$ @Jacob Only for BigInt compatibility. It would be n-1n otherwise. \$\endgroup\$
    – Arnauld
    Apr 16, 2023 at 13:01
4
+50
\$\begingroup\$

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

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

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!

\$\endgroup\$
2
  • \$\begingroup\$ This doesn't match the test-case for 1. \$\endgroup\$
    – pajonk
    Apr 16, 2023 at 11:32
  • \$\begingroup\$ @pajonk - Drat! Well spotted. Hopefully fixed now (with complete re-think...) \$\endgroup\$ Apr 16, 2023 at 16:12
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

MATL, 7 bytes

:Yp-1ZQ

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Cumulative product and evaluate polynomial, good idea! \$\endgroup\$
    – Luis Mendo
    Apr 16, 2023 at 23:46
4
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ You can use `*,$ instead of `/,$*. ato.pxeger.com/… \$\endgroup\$
    – xigoi
    Apr 17, 2023 at 9:11
  • \$\begingroup\$ @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)... \$\endgroup\$ Apr 17, 2023 at 9:47
  • 1
    \$\begingroup\$ @xigoi - How do you put `* into a codeblock in a comment, anyway? \$\endgroup\$ Apr 17, 2023 at 9:49
  • 1
    \$\begingroup\$ Found it: If a backtick is somewhere in the middle, you can use double enclosing backticks: ``like`this``, resulting in like`this. 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 `like`this`. So the comment `*,$ is accomplished with `\`*,$`. \$\endgroup\$ Apr 17, 2023 at 10:03
  • 1
    \$\begingroup\$ There is even a challenge about it. codegolf.stackexchange.com/questions/17650/… \$\endgroup\$
    – xigoi
    Apr 17, 2023 at 15:18
4
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Wow, that's a clever and efficient way to calculate it! \$\endgroup\$
    – chunes
    Apr 17, 2023 at 20:11
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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|\$

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Japt, 4 bytes

õÊìJ

Try it

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

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
\$\endgroup\$
3
\$\begingroup\$

Julia 0.7, 23 bytes

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

Try it online!

Uses the recursive formula.

\$\endgroup\$
1
  • \$\begingroup\$ -1 byte (and also works with Julia 1.0) !n=n>0&&prod(1:n)-!~-n \$\endgroup\$
    – MarcMush
    Apr 22, 2023 at 23:22
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ @DLosc thanks, updated \$\endgroup\$
    – The Thonnu
    Apr 19, 2023 at 6:32
2
\$\begingroup\$

Charcoal, 12 bytes

I↨ENΠ…¹⁺²ι±¹

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

   N            First input as a number
  E             Map over implicit range
     …          Range from
      ¹         Literal integer `1` to
         ι      Current value
       ⁺        Plus
        ²       Literal integer `2`
    Π           Take the product
 ↨        ±¹    Interpret as base `-1`
I               Cast to string
                Implicitly print
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)))
\$\endgroup\$
1
  • \$\begingroup\$ A port of @KiptheMalamute's Pyt answer is only 35 bytes: f(n)=abs(sum(m=1,n,prod(k=1,m,-k))). \$\endgroup\$
    – Neil
    Apr 16, 2023 at 8:42
2
\$\begingroup\$

C (gcc), 32 bytes

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

Try it online!

Port of Arnauld's JavaScript answer

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

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.

\$\endgroup\$

Your Answer

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

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