Of Different Prime-Factorization Exponents

[Dan Dima]

There is a straightforward formula for this - as simple as for the Euler-phi
or sigma functions.
It is quite difficult to write it in plain text but I'll try :D :

n=p^u:
a(n) = p^u-1

n=p_1^{u_1} * p_2^{u_2}:
a(n) = p_1^{u_1} * p_2^{u_2} - p_1^{u_1} + 1 - p_2^{u_2} + 1 = (p_1^{u_1} -
1)*(p_2^{u_2} - 1) + 1

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) + 1

The general formula for n=p_1^{u_1} * p_2^{u_2} * ... * p_k^{u_k} as:
a(n) = (p_1^{u_1} - 1)*(p_2^{u_2} - 1)*...*(p_k^{u_k} - 1) + 1

Just count for the inverse condition and pay attention for the multiple
counting.

Best regards,
Dan Dima



On 3/18/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
>
> 1) Here's a few more values:
> 0,1,2,3,4,3,6,7,8,6,10,8,12,9,9,15,16,13,18,15,14,15,22,17,24,18,26,21,28
> ,15
>
> 2) I think it would make more sense to have a(1) = 1.  You would have
> to change the "m < n" to "m <= n" - which affects only this value.
>
> 3) It might be more productive to look at the inverse condition, the
> number of m s.t. b(m,p) = b(n,p) for some p|n.  This is n - a(n):
>
> 0,1,1,1,1,3,1,1,1,4,1,4,1,5,6,1,1,5,1,5,7,7,1,7,1,8,1,7,1,15
>
> 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.
>
> 5) I don't at this point see any sort of simple formula.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Leroy Quet <qq-quet at mindspring.com>
>
> A couple of days ago I sent to the EIS this sequence:
>
> >%S A000001 0,1,2,3,4,3,6,7,8,6,10,8,12,9
> >%N A000001 If n = product{p=primes,p|n} p^b(n,p), where each b(n,p) is
> a
> >positive integer, then a(n) is number of positive integers m, m < n,
> >such that each b(m,p) does not equal b(n,p).
> >%e A000001 12 = 2^2 * 3^1. Of the positive integers < 12, there are 8
> >integers where no prime divides these integers the same number of
> times
> >the prime divides 12: 1, 2 = 2^1, 5 = 5^1, 7 = 7^1, 8 = 2^3, 9 = 3^2,
> 10 =
> >2^1 *5^1, and 11 = 11^1.
> >So a(12) = 8.
> >The other positive integers < 12 (3 = 3^1, 4 = 2^2, and 6 = 2^1
> >* 3^1) each are divisible by at least one prime the same number of
> times
> >this prime divides 12.
> >%O A000001 1
> >%K A000001 ,more,nonn,
>
> (Unfortunately, this sequence has not yet appeared, given that Neil is
> currently on vacation.)
>
> Is there a direct way (say, a sum involving the Moebius function,
> perhaps) to calculate this sequence's terms?
>
> If someone finds a formula, please post it as a comment to this
> sequence
> when the sequence finally appears (as well as posting it to seq.fan).
> I myself am not as good at math as I used to be, and cannot find a
> formula for a(n).
>
> thanks,
> Leroy Quet
>
>
> ___________________________________________________
> Try the New Netscape Mail Today!
> Virtually Spam-Free | More Storage | Import Your Contact List
> http://mail.netscape.com
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060319/b7e32885/attachment-0001.htm>