15
\$\begingroup\$

The Lehmer-Comtet sequence is a sequence such that a(n) is the nth derivative of f(x) = xx with respect to x as evaluated at x = 1.

Task

Take a non-negative integer as input and output the nth term of the Lehmer-Comtet sequence.

This is so you should minimize the file size of your source code.

Test Cases

OEIS 5727

Here are the first couple terms in order (copied from the OEIS)

1, 1, 2, 3, 8, 10, 54, -42, 944, -5112, 47160, -419760, 4297512, -47607144, 575023344, -7500202920, 105180931200, -1578296510400, 25238664189504, -428528786243904, 7700297625889920, -146004847062359040, 2913398154375730560, -61031188196889482880
\$\endgroup\$

10 Answers 10

13
\$\begingroup\$

Haskell, 77 75 bytes, no differentiation builtins

x@(a:b)&y@(c:d)=a*c:zipWith(+)(b&y)(x&d)
s=1:s&(1:scanl(*)1[-1,-2..])
(s!!)

Try it online!

How it works

We represent a function as its infinite list of Taylor series coefficients about \$x = 1\$:

$$ f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(1)}{n!} (x - 1)^n $$

is represented by \$[f(1), f'(1), f''(1), ...]\$.

The & operator multiplies two such functions using the product rule. This lets us recursively define the function \$s(x) = x^x\$ in terms of itself using the differential equation

$$ s(1) = 1, \\ s'(x) = s(x) \cdot (1 + \ln x), $$

where

$$ \ln x = \sum_{n=1}^\infty \frac{(-1)^{n-1}(n - 1)!}{n!}(x - 1)^n. $$

\$\endgroup\$
7
\$\begingroup\$

Mathematica, 19 bytes

D[x^x,{x,#-1}]/.x->1&

-18 bytes from @Not a tree

\$\endgroup\$
4
  • 9
    \$\begingroup\$ Unless I'm missing something, you can get this a lot shorter: D[x^x,{x,#}]/.x->1&, 19 bytes. \$\endgroup\$
    – Not a tree
    Jul 3, 2017 at 0:13
  • \$\begingroup\$ actually 21 bytes.. but yes! a lot shorter! \$\endgroup\$
    – ZaMoC
    Jul 3, 2017 at 6:52
  • \$\begingroup\$ I don't think you need the -1 — the sequence from OEIS starts at n = 0. \$\endgroup\$
    – Not a tree
    Jul 3, 2017 at 7:11
  • 1
    \$\begingroup\$ ok then! 19 bytes it is \$\endgroup\$
    – ZaMoC
    Jul 3, 2017 at 7:15
5
\$\begingroup\$

Octave with Symbolic Package, 36 32 bytes

syms x
@(n)subs(diff(x^x,n),x,1)

The code defines an anonymous function which outputs a symbolic variable with the result.

Try it online!

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

Haskell, 57 bytes

f 0=1
f n=f(n-1)-foldl(\a k->f(k-1)/(1-n/k)-a*k)0[1..n-1]

Try it online!

No built-ins for differentiating or algebra. Outputs floats.

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

Python with SymPy, 77 75 58 57 bytes

1 byte saved thanks to @notjagan

17 bytes saved thanks to @AndersKaseorg

from sympy import*
lambda n:diff('x^x','x',n).subs('x',1)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ lambda n:diff('x**x','x',10).subs('x',1) doesn’t require sympy.abc. \$\endgroup\$ Jul 2, 2017 at 22:42
  • 1
    \$\begingroup\$ Ummm ... where do you use n? \$\endgroup\$
    – Adalynn
    Jul 2, 2017 at 23:05
  • \$\begingroup\$ @ZacharyT thanks! coincidentally I tested anders' proposal right with n=10, so it gave the same result :) fixed now \$\endgroup\$
    – Uriel
    Jul 2, 2017 at 23:13
  • \$\begingroup\$ -1 byte by replacing x**x with x^x. \$\endgroup\$
    – notjagan
    Jul 3, 2017 at 1:17
3
\$\begingroup\$

SageMath, 33 32 bytes

lambda n:diff(x^x,x,n).subs(x=1)

Try it on SageMathCell

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

Python 3, 150 bytes

lambda n:0**n or sum(L(n-1,r)for r in range(n))
L=lambda n,r:0<=r<=n and(0**n or n*L(n-2,r-1)+L(~-n,r-1)+(r-~-n)*L(~-n,r)if r else n<2or-~-n*L(n-1,0))

Try it online!

Exponential runtime complexity. Uses the formula given in the OEIS page.

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

Python 3, 288 261 bytes

Differentiation without differentiation built-in.

p=lambda a,n:lambda v:v and p(a*n,n-1)or a
l=lambda v:v and p(1,-1)
e=lambda v:v and m(e,a(p(1,0),l))or 1
a=lambda f,g:lambda v:v and a(f(1),g(1))or f(0)+g(0)
m=lambda f,g:lambda v:v and a(m(f(1),g),m(g(1),f))or f(0)*g(0)
L=lambda n,f=e:n and L(n-1,f(1))or f(0)

Try it online!

How it works

Each of the first five lines define functions and their derivatives and their results when evaluated at 1. Their derivatives are also functions.

  • p is power i.e. a*x^n
  • l is logarithm i.e. ln(x)
  • e is exponential i.e. exp(x)
  • a is addition i.e. f(x)+g(x)
  • m is multiplication i.e. f(x)*g(x)

Usage: for example, exp(ln(x)+3x^2) would be represented as e(l()+p(3,2)). Let x=e(l()+p(3,2)). To find its derivative, call x(1). To find its result when evaluated at 1, call x(0).

Bonus: symbolic differentiation

\$\endgroup\$
1
  • \$\begingroup\$ You can save a lot of bytes by using exec compression. Try it online! \$\endgroup\$
    – Wheat Wizard
    Jul 3, 2017 at 4:08
1
\$\begingroup\$

Python3+mpmath 52 bytes

from mpmath import*
lambda n:diff(lambda x:x**x,1,n)

-3 bytes, Thanks @Zachary T

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You should change the language to python3+mpmath, since mpmath is not a standard library. \$\endgroup\$
    – Wheat Wizard
    Jul 2, 2017 at 22:42
  • 2
    \$\begingroup\$ You can change your first line to from mpmath import*, and the second to diff(lambda x:x**x,1,n). (just removing unnecessary spaces) \$\endgroup\$
    – Adalynn
    Jul 2, 2017 at 23:04
0
\$\begingroup\$

Pari/GP, 32 bytes

n->n!*Vec((y=1+x+O(x^n++))^y)[n]

Try it online!

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