[seqfan] Martin's formula for the LCM (A003418)

[peter.luschny]

Martin's formula for the LCM (A003418).

Some times ago...

PL> The following nice non-recursive way
PL> to compute the Farey Tree has been
PL> discussed by Norman Routledge.

Olivier Gerard answered:
OG> It is not recursive on the previous set but it
OG> is recursive internally.

Recently Greg Martin showed a cute little formula
for the lcm{1,2,3,..,n} = LCM(n).

Jonathan Vos Post reported this in A003418:
"The product of the gamma-function sampled over the
set of all rational numbers in the open interval (0, 1)
whose denominator in lowest terms is at most n equals
((2*pi)^(1/2))*LCM(n)^(-1/2)."

Thus we look at a Farey sequence. If a/b is a member
of this sequence 1-a/b is also a member. We have to
compute a product and so we can trade in two Gamma
evaluations for one sin evaluation by the Ergänzungssatz.

The Pi factor can be pulled out of the product raised
to the power of Sum(phi(i),i=1..n)-1, see A015614.

Thus Martin's formula

   LCM(n) = mul{i=Farey(n),0<i<1} 2Pi/Gamma(i)^2

becomes for n > 1 the cheaper and more elementary

   LCM(n) = (1/2)[mul{i=Farey(n),0<i<=1/2} 2sin(iPI)]^2

Cheers Peter

Let's check it with Maple:

HalfFarey := proc(n) local a,b,c,d,k,s;
a := 0; b := 1; c := 1; d := n; s := NULL;
do k := iquo(n + b, d);
   a, b, c, d := c, d, k*c - a, k*d - b;
   if 2*a > b then break fi;
   s := s,(a/b);
od: [s] end:

LCM := proc(n) local i;
(1/2)*mul(2*sin(Pi*i),i=HalfFarey(n))^2 end:

seq(LCM(n),n=2..16): evalf(%);