Multiply Then Add, Smallest Possible Integer

[Leroy Quet]

sequences need extending.
submitted the terms I calculated (by hand and with calculator) without 
Return-Path: <gijswijt at science.uva.nl>
X-Ids: 164
X-Organisation: Faculty of Science, University of Amsterdam, The Netherlands
X-URL: http://www.science.uva.nl/
Message-ID: <10561.86.82.53.79.1168191262.squirrel at webmail.science.uva.nl>
In-Reply-To: <200701071644.LAA52837 at fry.research.att.com>
References: <200701071644.LAA52837 at fry.research.att.com>
Date: Sun, 7 Jan 2007 18:34:22 +0100 (CET)
Subject: Re: a possible duplicate pair of long standing
From: "Dion Gijswijt" <gijswijt at science.uva.nl>
To: njas at research.att.com
Cc: seqfan at ext.jussieu.fr
User-Agent: SquirrelMail/1.4.6-rc1
MIME-Version: 1.0
Content-Type: text/plain;charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Priority: 3 (Normal)
Importance: Normal
X-Virus-Scanned: by amavisd-new
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-2.0.2 (shiva.jussieu.fr [134.157.0.164]); Sun, 07 Jan 2007 18:34:25 +0100 (CET)
X-j-chkmail-Score: MSGID : 45A12F21.000 on shiva.jussieu.fr : j-chkmail score : X : 0/50 0 0.548 -> 1
X-Miltered: at shiva.jussieu.fr with ID 45A12F21.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

Dear Neil,

The two sequences A055773 and A094300 are the same. Both calculate
the product of primes p for which p divides n!, but p^2 does not (i.e.
ord_p(n!)=1). See details below.

Dion Gijswijt.

-------------------------------------------------------------------------
A055773: a(n)=F(n)/(GCD(F(n),Q(n)))
Here Q(n) is the largest square divisor of n! and F(n) is the square-free
part of n! (i.e. F(n)=n!/Q(n)).

Compute the order of primes p for these numbers:
k:=ord_p(n!). Then
ord_p(Q(n))=k   if k even
            k-1 if k odd

ord_p(F(n))=0   if k even
            1   if k odd

Taking the minimum:
ord_p(GCD(F(n),Q(n))=1 if k odd, k-1>0 (i.e. k=3,5,7,9,...)
                    =0 otherwise

Subtracting:
ord_p(a(n))=1 if k=1
            0 otherwise
------------------------------------------------------------------------
A094300: a(1)=1; a(n)=n*(a(n-1) if n prime, least integer multiple of
a(n-1)/n otherwise

It is again not too hard to see that a(n) is the product of the primes p
for  which ord_p(n)=1 (say by induction). For n prime it is clear, in the
other case observe that ord_p(a(n))=max(0, ord_p(a(n-1))-ord_p(n)).

It also follows directly from the given formula: a(n)= product of primes p
with n/2<p<=n.
------------------------------------------------------------------------




>
> Leroy reminds me that the question
>
>    does A055773 = A094300 ?
>
> remains unanswered.
>
> Neil
>