A073087(5)

[David Wilson]

----- Original Message ----- 
From: "Mitchell Harris" <harris at tcs.inf.tu-dresden.de>
To: "Lambert Klasen" <Lambert.Klasen at gmx.net>
Cc: <seqfan at ext.jussieu.fr>
Sent: Wednesday, September 14, 2005 1:34 PM
Subject: Re: A073087(5)


> On Wed, 14 Sep 2005, Lambert Klasen wrote:
>
>>ID Number: A073087
>>URL:       http://www.research.att.com/projects/OEIS?Anum=A073087
>>Sequence:  1,6,30,210
>>Name:      Least k such that sigma(k^k)>=n*k^k.
>
> ...
>>and the next term in the sequence a(5) is most likely 30030.
>
> a(5) is certainly 30030...
>
>>but i cannot compute a(5) due to lack of memory.
>>using PARI, it needs more then 1GB of memory which i unfortunately
>>do not possess.
>>
>>anyone help ?
>
> Instead of computing k^k and then sigma of that (for large k), just use
> the identity
>
>  sigma(k^k) = prod (p^(k r + 1) - 1)/(p - 1)
>
> (where the product is over all prime power factors p^r). This speeds
> things up enormously for a(5) (using Mathematica). I am not so patient for
> a(6) though...
>
> Mitch
>

Another way to interpret this sequence is a(n) = smallest k with 
floor(sigma(k^k)/(k^k)) = n.

Now, if the prime factorization of k is PROD(p^e), then sigma(k^k)/(k^k) = 
PROD((p^(ek+1)-1)/(p-1))/PROD(p^ek) = PROD((p-p^(-ek))/(p-1)).  Note that 
for every moderate k, p^(-ek) < 2^(-ek) will be very small.  This means that 
(p-p^(-ek))/(p-1) is slightly smaller than p/(p-1), so that 
PROD((p-p^(-ek))/(p-1)) is slightly smaller than PROD(p/(p-1)) = k/phi(k). 
That is, sigma(k^k)/(k^k) = k/phi(k)-e where e >= 0 is a small epsilon (e = 
0 only when k = 1).

In fact, we can show that e < 1/k <= 1/phi(k) (Handwaving admittedly, but 
true handwaving).  This means that unless k/phi(k) is an integer, k/phi(k)-e 
 > k/phi(k)-1/phi(k) giving floor(sigma(k^k)/(k^k)) = floor(k/phi(k)-e) = 
floor(k/phi(k)).  If k/phi(k) is an integer, then either k = 1, in which 
case e = 0 and floor(sigma(k^k)/(k^k)) = floor(k/phi(k)-e) = 
floor(k/phi(k)); or else k is of the form 2^x*3^y with x >= 1 and y >= 0, in 
which case e > 0 and floor(sigma(k^k)/(k^k)) = floor(k/phi(k)-e) = 
floor(k/phi(k))-1, since k/phi(k)-e is slightly less than the integer 
k/phi(k).

Now let's consider when floor(k/phi(k)) reaches a new maximum.  If k = 
PROD(p^e), then k' = PROD(p) <= k with k'/phi(k') = k/phi(k).  Thus k/phi(k) 
achieves a new maximum only for k a product of distinct primes (squarefree 
k).  Also, if k is the product of x >= 1 distinct primes, k/phi(k) is 
maximized when k is as small as possible, that is when k = p(x)#.  Hence 
k/phi(k) reaches a new maximum only when k is a primorial number.  This in 
turn implies that floor(k/phi(k)) reaches a new maximum only when k is a 
primorial number, however, we can show computationally that floor(k/phi(k)) 
does not achieve a new maximum for every primorial, but only for certain 
ones.

Now here comes the handwaving.  I claim that sigma(k^k)/(k^k) is close 
enough to k/phi(k) that floor(sigma(k^k)/(k^k)) can achieve a new maximum 
only when floor(k/phi(k)) does, that is, only when k is a primorial number. 
Letting k = p# with p >= 5, k/phi(k) is not an integer, so that 
floor(sigma(k^k)/(k^k)) = floor(k/phi(k)) by an above paragraph.  This means 
that k >= 5# = 30, floor(sigma(k^k)/(k^k)) will reach a new maximum 
precisely when floor(k/phi(k)) does.  So starting at a(3), A073087(n) = (the 
smallest k with floor(sigma(k^k)/(k^k)) = n) = (the smallest k with 
floor(k/phi(k)) = n), and we know that k must be primorial.  This makes 
computation of A073087 extremely easier.

floor(k/phi(k)) = n for the first time when k = p# for p =

1 2 3 7 13 23 43 79 149 257 461 821 1451 2549 4483 7879 13859 24247 42683 
75037

(Note: I computed this sequence using integer arithmetic, not floating 
point, so I believe it to be accurate).

floor(sigma(k^k)/(k^k)) = n for the first time when k = p# for p =

1 3 5 7 13 23 43 79 149 257 461 821 1451 2549 4483 7879 13859 24247 42683 
75037

A073087 will consist of the primorials of this latter sequence.  a(2) and 
a(3) differ between the two sequences because floor(sigma(k^k)/(k^k)) = 
floor(k/phi(k)) for all primorials k except 2# and 3#.  The two sequences 
coincide starting at a(4).