Alternating factorial

Question

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 code-golf, so the code with the fewest bytes (in each language) wins.

Test cases

Please add a plain English explanation and a worked example. — Shaggy, Apr 16 at 0:42
Can you check if the recurrence relation stated is correct? Because I’m not sure it is. — The Empty String Photographer, 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)\$). — Jonathan Allan, 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. — justhalf, Apr 17 at 8:53

Jonathan Allan · Accepted Answer · 2023-04-15 22:43:01Z

10

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!

edited Apr 15 at 22:43

answered Apr 15 at 22:37

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

5

\$\begingroup\$ ...right, of course, base \$-1\$ does alternating sum, I always forget that :/ \$\endgroup\$
– caird coinheringaahin g ♦
Apr 15 at 22:39

Add a comment |

Unmitigated · Accepted Answer · 2023-04-15 23:39:46Z

8

Wolfram Language (Mathematica), 20 bytes

AlternatingFactorial

Try it online!

answered Apr 15 at 23:39

Unmitigated

2,7491 gold badge4 silver badges14 bronze badges

\$\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\$
– Greg Martin
Apr 16 at 20:55

Add a comment |

j63nu · Accepted Answer · 2023-04-16 19:59:30Z

7

APL(Dyalog Unicode), 6 bytes ^SBCS

¯1⊥∘!⍳

Try it on APLgolf!

answered Apr 16 at 19:59

j63nu

811 bronze badge

Add a comment |

Aiden Chow · Accepted Answer · 2023-04-16 02:02:10Z

6

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

answered Apr 16 at 2:02

Aiden Chow

12.7k1 gold badge14 silver badges53 bronze badges

Add a comment |

mousetail · Accepted Answer · 2023-04-16 11:01:50Z

6

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

edited Apr 16 at 11:01

answered Apr 16 at 6:56

mousetail

11.9k1 gold badge31 silver badges75 bronze badges

Add a comment |

att · Accepted Answer · 2023-04-16 17:17:50Z

5

Wolfram Language (Mathematica), 20 bytes

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

Try it online!

answered Apr 16 at 17:17

att

19.8k2 gold badges14 silver badges56 bronze badges

2

\$\begingroup\$ Ties with the built-in! \$\endgroup\$
– The Thonnu
Apr 16 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 at 17:28

Add a comment |

loopy walt · Accepted Answer · 2023-04-16 03:16:58Z

4

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.

answered Apr 16 at 3:16

loopy walt

16k2 gold badges10 silver badges65 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2023-04-16 08:48:06Z

4

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!

edited Apr 16 at 8:48

answered Apr 15 at 22:32

Arnauld

189k20 gold badges171 silver badges631 bronze badges

\$\begingroup\$ Is there a reason to use ~-n instead of n-1? \$\endgroup\$
– noodle man
Apr 16 at 12:05
1

\$\begingroup\$ @Jacob Only for BigInt compatibility. It would be n-1n otherwise. \$\endgroup\$
– Arnauld
Apr 16 at 13:01

Add a comment |

lesobrod · Accepted Answer · 2023-04-16 09:09:11Z

4

+50

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

answered Apr 16 at 9:09

lesobrod

3,2391 gold badge6 silver badges26 bronze badges

\$\begingroup\$ Here's it in 35 bytes as a port of my Haskell answer. \$\endgroup\$
– Wheat Wizard ♦
Apr 22 at 16:11

Add a comment |

Dominic van Essen · Accepted Answer · 2023-04-16 16:11:19Z

4

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!

edited Apr 16 at 16:11

answered Apr 16 at 8:07

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

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

Add a comment |

The Thonnu · Accepted Answer · 2023-04-16 16:47:25Z

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

beaker · Accepted Answer · 2023-04-16 19:53:37Z

4

MATL, 7 bytes

:Yp-1ZQ

Try it online!

answered Apr 16 at 19:53

beaker

2,6391 gold badge9 silver badges18 bronze badges

1

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

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-04-17 09:19:09Z

4

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)

edited Apr 17 at 9:19

answered Apr 17 at 8:54

Kevin Cruijssen

124k11 gold badges135 silver badges374 bronze badges

Add a comment |

Dominic van Essen · Accepted Answer · 2023-04-17 09:51:16Z

4

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

edited Apr 17 at 9:51

answered Apr 16 at 17:51

Dominic van Essen

34.6k2 gold badges18 silver badges54 bronze badges

\$\begingroup\$ You can use `*,$ instead of `/,$*. ato.pxeger.com/… \$\endgroup\$
– xigoi
Apr 17 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\$
– Dominic van Essen
Apr 17 at 9:47
1

\$\begingroup\$ @xigoi - How do you put `* into a codeblock in a comment, anyway? \$\endgroup\$
– Dominic van Essen
Apr 17 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\$
– Kevin Cruijssen
Apr 17 at 10:03
1

\$\begingroup\$ There is even a challenge about it. codegolf.stackexchange.com/questions/17650/… \$\endgroup\$
– xigoi
Apr 17 at 15:18

| Show 2 more comments

Nitrodon · Accepted Answer · 2023-04-17 20:04:28Z

4

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

answered Apr 17 at 20:04

Nitrodon

10.7k2 gold badges17 silver badges33 bronze badges

\$\begingroup\$ Wow, that's a clever and efficient way to calculate it! \$\endgroup\$
– chunes
Apr 17 at 20:11

Add a comment |

caird coinheringaahin g · Accepted Answer · 2023-04-15 22:38:20Z

3

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

edited Apr 15 at 22:38

answered Apr 15 at 22:27

caird coinheringaahin g♦

49.5k11 gold badges121 silver badges348 bronze badges

Add a comment |

lyxal · Accepted Answer · 2023-04-15 22:41:35Z

3

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

answered Apr 15 at 22:41

lyxal

32.3k2 gold badges56 silver badges138 bronze badges

Add a comment |

Kip the Malamute · Accepted Answer · 2023-04-15 23:55:04Z

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

Neil · Accepted Answer · 2023-04-16 01:07:47Z

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)

Jos Woolley · Accepted Answer · 2023-04-16 05:19:14Z

3

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.

answered Apr 16 at 5:19

Jos Woolley

1,9421 silver badge8 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2023-04-16 11:55:36Z

3

Japt, 4 bytes

õÊìJ

Try it

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

answered Apr 16 at 11:55

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Fatalize · Accepted Answer · 2023-04-17 09:17:14Z

3

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

answered Apr 17 at 9:17

Fatalize

38.4k5 gold badges67 silver badges160 bronze badges

Add a comment |

Kirill L. · Accepted Answer · 2023-04-20 18:49:03Z

3

Julia 0.7, 23 bytes

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

Try it online!

Uses the recursive formula.

answered Apr 20 at 18:49

Kirill L.

13.7k2 gold badges14 silver badges48 bronze badges

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

Add a comment |

The Thonnu · Accepted Answer · 2023-04-20 19:34:32Z

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

\$\begingroup\$ @DLosc thanks, updated \$\endgroup\$
– The Thonnu
Apr 19 at 6:32 — The Thonnu, Apr 19 at 6:32

Neil · Accepted Answer · 2023-04-15 23:27:25Z

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

south · Accepted Answer · 2023-04-16 08:13:23Z

2

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

answered Apr 16 at 8:13

south

1,6704 silver badges11 bronze badges

Add a comment |

score 2 · Accepted Answer · 2023-04-16 09:52:26Z

2

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

edited Apr 16 at 9:52

answered Apr 16 at 0:33

user117658

Add a comment |

138 Aspen · Accepted Answer · 2023-04-16 10:26:01Z

2

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

edited Apr 16 at 10:26

answered Apr 16 at 1:10

138 Aspen

4,8551 gold badge3 silver badges13 bronze badges

\$\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 at 8:42

Add a comment |

Noodle9 · Accepted Answer · 2023-04-16 18:11:58Z

2

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

answered Apr 16 at 18:11

Noodle9

20k3 gold badges20 silver badges45 bronze badges

Add a comment |

DLosc · Accepted Answer · 2023-04-17 21:41:07Z

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.

Alternating factorial

Task

Test cases

38 Answers 38

Jelly, 4 bytes

How?

Wolfram Language (Mathematica), 20 bytes

APL(Dyalog Unicode), 6 bytes SBCS

Desmos, 28 bytes

><> (Fish), 53 42 bytes

Wolfram Language (Mathematica), 20 bytes

Python, 40 bytes

JavaScript (ES6), 28 bytes

Curry (PAKCS), 48 bytes

R, 29 31 bytes

Thunno 2, 6 bytes

Explanation

MATL, 7 bytes

Oasis, 4 bytes

Nibbles, 5.5 5 bytes (10 nibbles)

Brain-Flak, 64 bytes

Jelly, 6 bytes

How it works

Vyxal, 4 bytes

Explained

Pyt, 10 bytes

Retina, 54 bytes

Excel, 38 bytes

Japt, 4 bytes

Brachylog, 11 bytes

Explanation

Julia 0.7, 23 bytes

Pip, 17 16 12 bytes

Explanation

Charcoal, 12 bytes

J, 10 bytes

minigolf, 23 22 bytes

Explanation

PARI/GP, 40 35 bytes

C (gcc), 32 bytes

FunStack alpha, 39 bytes

Worked example

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

APL(Dyalog Unicode), 6 bytes ^SBCS

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