Of Different Prime-Factorization Exponents

[franktaw at netscape.net]

I think this pretty well justifies (as well as explicating) my original 
comment.

Franklin T. Adams-Watters

-----Original Message-----
From: Dan Dima <dimad72 at gmail.com>

  n = p_1^{u_1} * p_2^{u_2} * ... * p_k^{u_k}
  Consider for each (2^k-2) subsets A_i of {1,2,...,k}, && 1 \leq {card 
A_i} \leq k-1:
  - all (2^{k-{card A_i}}-1) subsets B_i,j of {1,2,...,k} \ A_i, && 1 
\leq {card B_i,j} \leq k-{card A_i}
 - A_i && B_i,j -disjoint and their reunion is a subset of {1,2,...,k}
  - for all (3^k - 2^{k+1} + 1) such possible pairs (A_i,B_i,j) we have 
to count a floor term:

a(n) = (p_1^{u_1} - 1) * (p_2^{u_2} - 1) * ... * (p_k^{u_k} - 1) -
  - \sum_{all pairs (A_i,B_i,j)} (-1)^{k-{card A_i}-{card B_i,j}} floor( 
(\prod_{all i in A_i} p_i^{u_i} - 1) / (\prod_{all j in B_i,j} p_j) ).

 for ex.if k=3, n=p_1^{u_1} * p_2^{u_2} * p_3^{u_3}:
 a(n) = (p_1^{u_1} - 1) * (p_2^{u_2} - 1) * (p_3^{u_3} - 1) -
 - floor( (p_1^{u_1} * p_2^{u_2} - 1) / p_3 )
 - floor( (p_2^{u_2} * p_3^{u_3} - 1) / p_1 )
 - floor( (p_3^{u_3} * p_1^{u_1} - 1) / p_2 )
  + floor( (p_1^{u_1} - 1) / p_2 ) + floor( (p_1^{u_1} - 1) / p_3 ) - 
floor( (p_1^{u_1} - 1) / (p_2 * p_3) )
  + floor( (p_2^{u_2} - 1) / p_3 ) + floor( (p_2^{u_2} - 1) / p_1 ) - 
floor( (p_2^{u_2} - 1) / (p_3 * p_1) )
  + floor( (p_3^{u_3} - 1) / p_1 ) + floor( (p_3^{u_3} - 1) / p_2 ) - 
floor( (p_3^{u_3} - 1) / (p_1 * p_2) ).

 I hope it's OK now...

 Regards,
 Dan Dima

>4) Looking at the function in (3), we have a(p^i) = 1, and if n 
=p^i*q^j,
>
>a(n) = floor(n/p^i) - floor(n/p^{i+1}) + floor(n/q^j) -
>floor(n/q^{j+1}) - 1.
>
>For numbers with 3 or more prime factors, we can get similar but
>increasingly more complex formulae based on the inclusion/exclusion
>principle.

___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com