[seqfan] Martin's formula for the LCM (A003418)
peter.luschny
peter.luschny at googlemail.com
Sat Aug 8 18:47:28 CEST 2009
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(%);
More information about the SeqFan
mailing list