Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Product of Two Primes


Date: 10/27/1999 at 10:50:39
From: Rob Amure
Subject: Discrete math problems

How many positive integers less than 100 can be written as the product 
of the first power of two different primes?


Date: 10/28/1999 at 10:33:31
From: Doctor Rob
Subject: Re: Discrete math problems

Thanks for writing to Ask Dr. Math.

First throw out all multiples of 2^2, 3^2, 5^2, and 7^2 (all squares 
of the primes up to sqrt[100] = 10):

     100*(1-1/2^2)*(1-1/3^2)*(1-1/5^2)*(1-1/7^2)

and round down to the nearest integer. Then throw out 1. Then throw 
out the 25 primes smaller than 100. Finally you have to throw out the 
multiples of 2*3*5 = 30, 2*3*7 = 42, 2*3*11 = 66, 2*3*13 = 78, and 
2*5*7 = 70 (all triple-products of distinct primes the result of which 
is < 100), whose number is

       [100/30] + [100/42] + [100/66] + [100/78] + [100/70]
     = 3 + 2 + 1 + 1 + 1
     = 8

Another way to count this would be to use generating functions. Let

    p(x) = x^log(2) + x^log(3) + x^log(5) + x^log(7) + x^log(11) + ...

Then p(x)^2 will have a term x^log(p*q) for every pair of primes 
p and q. To get rid of terms with p = q, subtract p(x^2). Then every 
pair with p < q is matched with a pair with p > q, so to remove 
double-counting, divide the result by 2. Discard all terms with an 
exponent greater than log(100). Then put x = 1, and you'll have your 
result.

Still another way to solve the problem is to use the prime-counting 
function pi(x), which gives you the number of primes less than or 
equal to x. The number of products of p*q with p < q can be split up 
according to the value of p, and p < sqrt(100), so p = 2, 3, 5, or 7 
only. For any p, the number of q's is pi(100/p) - pi(p). Add this up 
for p = 2, 3, 5, and 7, and you'll have the answer.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/