24
\$\begingroup\$

Laguerre polynomials are solutions to Laguerre's equation, a second-order linear differential equation: \$xy''+(1-x)y'+ny=0\$. For a given value of n, the solution, y, is named \$L_n(x)\$.

The polynomials can be found without calculus using recursion:

\$L_0(x)=1\$

\$L_1(x)=1-x\$

\$L_{k+1}(x)=\frac{(2k+1-x)L_k(x)-kL_{k-1}(x)}{k+1}\$

Summation can be used to the same end:

\$L_n(x)=\sum\limits_{k=0}^{n}{n\choose k}\frac{(-1)^k}{k!}x^k\$

\$L_n(x)=\sum\limits_{i=0}^n\prod\limits_{k=1}^i\frac{-(n-k+1)x}{k^2}\$

The first Laguerre polynomials are as follows:

polynomials

Coefficients can be found here.

The Challenge

Given a nonnegative integer n and a real number x, find \$L_n(x)\$.

Rules

  • This is so the shortest answer in bytes wins.

  • Assume only valid input will be given.

  • Error should be under one ten-thousandth (±0.0001) for the test cases.

Test Cases

Here, n is the first number and x is the second.

In: 1 2
Out: -1

In: 3 1.416
Out: -0.71360922

In: 4 8.6
Out: −7.63726667

In: 6 -2.1
Out: 91.86123261
\$\endgroup\$
12
  • 3
    \$\begingroup\$ I like that this challenge asks for the value of the polynomial on a certain input rather than its list of coefficients. \$\endgroup\$ – xnor Jul 13 '20 at 8:17
  • \$\begingroup\$ Thanks @xnor, it made more sense that way, being a polynomial and all \$\endgroup\$ – golf69 Jul 13 '20 at 8:19
  • 1
    \$\begingroup\$ The point of writing "real" was to imply that the imaginary part of the input is always 0. Any real number can be approximated by a rational number by the limiting process because Q is a dense set. To change the word "real" to "rational" is unnecessary. @AdHocGarfHunter \$\endgroup\$ – golf69 Jul 13 '20 at 21:57
  • 1
    \$\begingroup\$ Certainly @AdHocGarfHunter \$\endgroup\$ – golf69 Jul 13 '20 at 22:40
  • 2
    \$\begingroup\$ Another useful fact about Laguerre polynomials: $$ L_n(x) = \frac{e^x}{n!} \frac{d^n}{dx^n}( e^{-x} x^n) $$ \$\endgroup\$ – Michael Seifert Jul 15 '20 at 17:24

16 Answers 16

5
\$\begingroup\$

MATL, 5 bytes

_1iZh

Inputs are \$n\$, then \$x\$. Try it online! Or verify all test cases.

How it works

This uses the equivalence of Laguerre polynomials and the (confluent) hypergeometric function:

\$ L_n(x) = {} _1F_1(-n,1,x) \$

_    % Implicit input: n. Negate
1    % Push 1
i    % Input: x
Zh   % Hypergeometric function. Implicit output
\$\endgroup\$
12
\$\begingroup\$

Python 2, 53 bytes

f=lambda n,x:n<1or((2*n-1-x)*f(n-1,x)-~-n*f(n-2,x))/n

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Outputs True if n=0 \$\endgroup\$ – fireflame241 Jul 13 '20 at 8:37
  • 3
    \$\begingroup\$ @fireflame241 Since True is basically the same as 1 in Python, this is allowed. See this meta post for details. \$\endgroup\$ – ovs Jul 13 '20 at 9:57
  • 2
    \$\begingroup\$ 52 bytes in Python 3.8. \$\endgroup\$ – ovs Jul 13 '20 at 9:58
11
\$\begingroup\$

Wolfram Language (Mathematica), 9 bytes

LaguerreL

Try it online!

\$\endgroup\$
4
  • 6
    \$\begingroup\$ 7 bytes: lagrrel \$\endgroup\$ – golf69 Jul 13 '20 at 8:33
  • 16
    \$\begingroup\$ Wow, I did not expect a built-in to be golfable. \$\endgroup\$ – fireflame241 Jul 13 '20 at 8:35
  • 4
    \$\begingroup\$ lagrrel works on WolframAlpha but not in Mathematica. \$\endgroup\$ – Greg Martin Jul 14 '20 at 7:12
  • \$\begingroup\$ oh darn, I thought WA and mathematica were identical \$\endgroup\$ – golf69 Jul 14 '20 at 23:11
6
\$\begingroup\$

Jelly, 11 bytes

cŻ÷Ż!$ƲṚḅN}

A dyadic Link accepting \$n\$ on the left and \$x\$ on the right which yields \$L_n(x)\$.

Try it online!

How?

This makes the observation that
\$L_n(x)=\sum\limits_{k=0}^{n}{n\choose k}\frac{(-1)^k}{k!}x^k=\sum\limits_{k=0}^{n}{(-x)^k}\frac{n\choose k}{k!}\$
which is the evaluation of a base \$-x\$ number with n+1 digits of the form \$\frac{n\choose k}{k!}\$.

cŻ÷Ż!$ƲṚḅN} - Link: n, x
      Ʋ     - last four links as a monad - f(n):
 Ż          -   zero-range (n) -> [0, 1, 2, ..., n]
c           -   (n) binomial (that) -> [nC0, nC1, nC2, ..., nCn]
     $      -   last two links as a monad - g(n):
   Ż        -     zero-range (n) -> [0, 1, 2, ..., n]
    !       -     factorial (that) -> [0!, 1!, 2!, ..., n!]
  ÷         -   division -> [nC0÷0!, nC1÷1!, nC2÷2!, ..., nCn÷n!]
       Ṛ    - reverse -> [nCn÷n!, ..., nC2÷2!, nC1÷1!, nC0÷0!]
          } - use the chain's right argument for:
         N  -   negate -> -x
        ḅ   - convert from base (-x) -> -xⁿnCn÷n!+...+-x²nC2÷2!+-x¹nC1÷1!+-x°nC0÷0!
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6),  48 42  41 bytes

Expects (x)(n). May output true instead of 1.

x=>g=k=>k<1||((x-k---k)*g(k)+k*g(k-1))/~k

Try it online!

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

Python 3.8 (pre-release), 66 bytes

L=lambda n,x:((2*n-1-x)*L(d:=n-1,x)-d*L(n-2,x))/n if n>1else 1-n*x

Try it online!

Direct implementation of the recursive algorithm, with one interesting part: L(1,x) and L(0,x) can be combined as L(n,x)=1-n*x.

Could save 2 bytes using L=lambda n,x:n>1and((2*n-1-x)*L(d:=n-1,x)-d*L(n-2,x))/n or 1-n*x, but L(n) is not necessarily zero.

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

APL (Dyalog Unicode), 16 bytes

1⊥⍨0,⎕×(-÷⌽×⌽)⍳⎕

Try it online!

A full program that takes n and x from two separate lines of stdin.

How it works

1⊥⍨0,⎕×(-÷⌽×⌽)⍳⎕
              ⍳⎕  ⍝ Take n and generate 1..n
       (-÷⌽×⌽)    ⍝ Compute i÷(n+1-i)^2 for i←1..n
   0,⎕×           ⍝ Multiply x to each and prepend 0, call it B
1⊥⍨               ⍝ Convert all ones from base B to single number

The mixed base conversion looks like this:

1..n:                ... n-3          n-2          n-1          1
B:            0      ... (n-3)x/4^2   (n-2)x/3^2   (n-1)x/2^2   nx
digits:       1      ... 1            1            1            1
digit values: x^n/n! ... (nC3 x^3/3!) (nC2 x^2/2!) (nC1 x^1/1!) (nC0 x^0/0!)

It is essentially a fancy way to write the sum of product scan over 1, nx, (n-1)x/2^2, (n-2)x/3^2, .... This happens to be shorter than a more straightforward -x-base conversion (evaluating a polynomial at -x):

APL (Dyalog Unicode), 18 bytes

(-⎕)⊥⌽1,(!÷⍨⊢!≢)⍳⎕

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Functional version: 1⊥⍨0,×∘(-÷⌽×⌽)∘⍳ \$\endgroup\$ – Adám Jul 13 '20 at 14:36
3
\$\begingroup\$

Python 3.8 (pre-release), 61 bytes

L=lambda k,x:k<1or[1-x,L(w:=k-1,x)*(k+w-x)-L(k-2,x)*w][k>1]/k

Try it online!

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

JavaScript (Node.js), 36 bytes

x=>(i=0,g=n=>n?1-x*n/++i/i*g(n-1):1)

Try it online!

Just convert the formula to this, and use recursive:

$$ L_n(x) = \sum_{i=0}^n\prod_{k=1}^i\frac{-(n-k+1)x}{k^2} $$

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

J, 37 20 bytes

-5 thanks to @Bubbler

Calculates the polynomial adapted from the summation formula and uses J's p. operator to calculate that polynomial with a given x.

(p.-)~i.((!]/)%!)@,]

Try it online!

J, 45 byte

Alternative Recursive function.

1:`-@.[~ ::((>:@]%~($:*[-~1+2*])-]*($:<:))<:)

Try it online!

How it works

We define a hook (fg), which is x f (g n). f is (p.-)~ so it will be evaluated as ((i.((!]/)%!)@,]) n) p. (- x).

(p.-)~i.((!]/)%!)@,]
      i.         @,] enumerate 3 -> 0 1 2, append 3 -> 0 1 2 3, …
         (!]/)       3 over i
              %      divided by
               !     !i
   -                 negate x
 p.                  apply -x to the polynomial expressed in J as
                     1 3 1.5 0.166667, so 1-3(-x)+1.5(-x)^2+0.16(-x)^3
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Top solution can be golfed to 20 bytes. \$\endgroup\$ – Bubbler Jul 13 '20 at 23:50
  • \$\begingroup\$ @Bubbler all great tips I never would have thought of. Thanks! \$\endgroup\$ – xash Jul 14 '20 at 10:56
1
\$\begingroup\$

Charcoal, 29 bytes

⊞υ¹FN⊞υ×⌈υLυI↨Eυ∕⌈υ×ιX§⮌υκ²±N

Try it online! Link is to verbose version of code. Uses a slightly modified version of the summation given in the question. Explanation:

⊞υ¹FN⊞υ×⌈υLυ

Calculate the factorials from \$0!\$ to \$n!\$.

I↨Eυ∕⌈υ×ιX§⮌υκ²±N

For each index \$i\$ from \$0\$ to \$n\$ calculate \$\frac{n!}{i!(n-i)!^2}\$ and then perform base conversion from base \$-x\$ which multiplies each term by \$(-1)^{n-i}x^{n-i}\$ and takes the sum.

If we set \$k=n-i\$ we see that we calculate \$\sum\limits_{k=0}^{n}{\frac{n!(-1)^k}{(n-k)!k!^2}x^k}=\sum\limits_{k=0}^{n}{n\choose k}\frac{(-1)^k}{k!}x^k\$ as required.

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

05AB1E, 16 bytes

1λèN·<I-₁*N<₂*-N/

Try it online. (No test suite for all test cases at once, since there seems to be a bug in the recursive environment..)

Explanation:

 λ                # Create a recursive environment
  è               # to get the 0-based n'th value afterwards
                  # (where `n` is the first implicit input)
                  # (which will be output implicitly as result in the end)
1                 # Starting with a(-1)=0 and a(0)=1,
                  # and for every other a(N), we'll:
                  #  (implicitly push a(N-1))
   N·             #  Push `N` doubled
     <            #  Decrease it by 1
      I-          #  Decrease it by the second input `x`
        *         #  Multiply it by the implicit a(N-1)
         N<       #  Push `N`-1
           ₂*     #  Multiply it by a(N-2)
             -    #  Decrease the a(N-1)*(2N-1-x) by this (N-1)*a(N-2)
              N/  #  And divide it by `N`: (a(N-1)*(2N-1-x)-(N-1)*a(N-2))/N
\$\endgroup\$
1
\$\begingroup\$

Japt -x, 28 27 26 bytes

ò@l *VpX /Xl ²*JpX /(U-X l

Try it

Japt, 30 29 28 bytes

ò x@l *VpX /Xl ²*JpX /(U-X l

Try it

Explanation

ò x@l *VpX /Xl ²*JpX /(U-X l
ò                               // Create a array [0, 1, ..., U]
  x                             // sum the array after mapping through
   @                            // Function(X)
    l                           //    U!
      *VpX                      //    times V ** X
           /Xl ²                //    divided by X! ** 2
                *JpX            //    times (-1) ** X
                     /(U-X l    //    divided by (U - X)!
  • U is the first input
  • V is the second input
  • ** represents exponentiation
  • ! represents factorial
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 39 bytes

Using the formula \$L_n(x)=\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{k!} x^k\$.

l(n,x)=sum(k=0,n,n!*(-x)^k/(n-k)!/k!^2)

Try it online!


Pari/GP, 45 bytes

Using the generating function \$\sum_{n=0}^\infty x^n L_n(t)= \frac{1}{1-x} e^{-xt/(1-x)}\$.

l(n,t)=Vec(exp(-x*t/(1-x)+O(x^n++))/(1-x))[n]

Try it online!

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

C (gcc), 91 bytes

i;k;float f(n,x)float x;{float p,s=0;for(i=++n;k=i--;s+=p)for(p=1;--k;)p*=(k-n)*x/k/k;x=s;}

Try it online!

Straighforward implementation of polynomial expansion. Slightly golfed less

i;k;
float f(n,x)float x;{
  float p,s=0;
  for(i=++n;k=i--;s+=p)
    for(p=1;--k;)
      p*=(k-n)*x/k/k;
  x=s;
}
\$\endgroup\$
1
\$\begingroup\$

Fortran (GFortran), 69 68 bytes

read*,n,a
print*,sum([(product([((j-n-1)*a/j/j,j=1,i)]),i=0,n)])
end

-1 byte thanks to @ceilingcat

The program reads in an implicit integer n and real a. Summation and product operations are performed using arrays (initialized using implicit loops) with the intrinsics sum() and product().

Try it online!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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