phi(n!!)

[Max Alekseyev]

It is easy to see that
eulerphi(x*y) = x*eulerphi(y) as soon as x divides y.

Since n!! = n * (n-2)!!, if n divides (n-2)!! then
a(n) = eulerphi(n!!) = eulerphi(n * (n-2)!!)
= n * eulerphi((n-2)!!) = n * a(n-2).

The only cases when n does not divide (n-2)!! are:

1) n is prime. In this case n is coprime to (n-2)!!, implying that
eulerphi(n*(n-2)!!) = eulerphi(n)*eulerphi((n-2)!!) = (n-1)*a(n-2)

2) n=2p where p is odd prime. Then
eulerphi(2p*(n-2)!!) = eulerphi(p)*eulerphi(2*(n-2)!!)
= (p-1)*2*eulerphi((n-2)!!) = (n-2)*a(n-2)

In the other cases we have the following five cases:
1) n=p*q, where p and q are distinct odd factors >1. Then (n-2)!!
contains both p,q as factors and hence is divisible by n.
2) n=p^2 where p is odd prime. Then (n-2)!! contains p and 2p as
factor and hence is divisible by n.
3) n=2*p*q, where p and q are distinct factors >1. Then (n-2)!!
contains 2p and 2q as factors and hence is divisible by n.
4) n=2*p^2 where p is odd prime. Then (n-2)!! contains 2p and 4p as
factors and hence is divisible by n.
5) n=2*2^2. Then (n-2)!! = 6!! = 6*4*2 is divisible by n.

Max

On 5/26/07, Leroy Quet <qq-quet at mindspring.com> wrote:
> I just submitted the following sequence.
>
> >%S A000001 1,1,2,4,8,16,48,128,432,1024,4320
> >%N A000001 a(n) = Number of positive integers which are coprime to n!! and
> >are <= n!! (where n!! = n*(n-2)*(n-4)*..*(1 or 2)).
> >%F A000001 a(n) = a(n-2)*(n-1) if n is prime. a(n) = a(n-2)*(n-2) if n is
> >even and n/2 = an odd prime. a(n) = a(n-2)*n otherwise.
> >%Y A000001 A006882,A048855
> >%O A000001 1
> >%K A000001 ,more,nonn,
>
> I am pretty absolutely sure that I am right about the recursion in the
> F-line. But I am not absolutely absolutely sure I am correct.
>
> Did I make a mistake? (Sorry for the dumb question. But I thought I
> better double-check with seq.fan, since EIS entries are suppose to be
> totally accurate.)
>
> Thanks,
> Leroy Quet
>
>