Register to reply 
How to count elementsby epsi00
Tags: elements 
Share this thread: 
#1
Feb2312, 08:10 AM

P: 84

say you are multiplying integers from 1 to 1000 and you want to count the number of "unique" elements. How would you do that? Is there a closed form expression for that?
counting the unique or nonunique elements is the same since we know the total number of elements and can get the unique or nonunique by simple substraction. an example of unique element is 2*3 because there is only one way to generate it by multiplication. But 24 is a nonunique element since there are few ways to generate it (3*8, 2*12, 6*4...) and you don't want to count it in as many ways as you can generate it or you simply want to count it once. In other words, a 10*10 matrix will have 100 elements but we want to know how many of those 100 are unique and how many are non unique. 


#2
Feb2312, 08:39 AM

P: 7

Hey there!
It seems to me that your definition of unique is lacking something. why would 6 be unique? 2*3 and 1*6 are two ways to generate it. if "unique" means "there is only one combination of numbers that multiplied generate this number" then you'd be looking for prime numbers (every nonprime number has at least two ways to generate it) 


#3
Feb2312, 08:53 AM

P: 84

p1*p2*p3*p4*...pn=p1*(p2*p3...pn)=(p1*p2)*(p2*p3*...pn)=.... my question is how many ways ( exactly not just order of magnitude ) are there to generate such a number ( as a function of n ) 


#4
Feb2312, 11:16 AM

Mentor
P: 18,334

How to count elements



#5
Feb2312, 01:15 PM

P: 84

take this number as an example: 3*7*5=105. This number can also be written as: 21*5=105 and 3*35=105, and 7*15=105. So in a matrix of say 40x40, the number 105 will appear 3 times ( forget the 1*105). I do not want to count it 3 times because the value is the same, 105, but there are three ways to produce this number. The total number of matrix elements is 40*40=1600 but the total number of "unique numbers" is less because it makes no sense counting an element with the same value 3 times ( or as many times as it appears in the matrix). My question is how do we count the number of non unique numbers like 105. Is there a closed form expression for those elements? 


#6
Feb2312, 05:01 PM

P: 894

Edit If you want to denote the cube of a prime as unique , say 8 = 2*4, then add to the previous number the number of primes less than 100. 2nd edit: If one can say 3*7 is not unique since it also equals 7*3 since you can't order the pair by size then the number of unique elements is the number of primes under 1000. That is by counting all numbers p*p as the only unique elements. 


#7
Feb2312, 06:52 PM

P: 144

We can perhaps interpret the question as follows:
Let u(n) be the cardinality of the set {a*b: a,b in {1,2,...,n}}. For example, u(3)=6 and u(7)=25. Is there some kind of general formula, or a clever way to determine u(n)? In particular, what is u(1000)? 


#8
Feb2312, 07:04 PM

P: 800

But I believe the OP means something else. He's calling a product "unique" if it only has one expression. He already said he means 6 = 2x3 is a "unique" because it can only be expressed one way. (OP rejects 1x6) So the question is now reduced to how many numbers less than n^2 have at least three distinct prime factors. Also, OP has not said what to do about exact powers such as 2^4 = 2*8 = 4*4. I think there's enough ambiguity in what the OP is asking to create some confusion in this thread. 


#9
Feb2312, 07:55 PM

P: 144




#10
Feb2312, 08:02 PM

P: 800




#11
Feb2312, 10:11 PM

P: 894




#12
Feb2312, 10:34 PM

P: 894




#13
Feb2412, 02:49 AM

P: 688

An alternative formulation of the same thing could be this (though I don't know if it helps towards a solution): How many numbers 'k' between 4 and n^{2} have a divisor d<=n, such that k/d is also <= n? 


#14
Feb2412, 07:39 AM

P: 84

I will try to rephrase my question in the hope that we get an answer.
Take an n*n matrix (products of integers not necessarily primes ), how many of those numbers are distinct. We know the total number of matrix elements is n^2 but we also know that the number of distinct numbers ( out of the n^2) is m<n. The important word here is Distinct. We are not allowed to count any number more than once even it occurs more than once. Is there a way to calculate m or ( nm) whichever is easier to calculate? 


#15
Feb2412, 08:22 AM

P: 144

OK, so you take an n*nmatrix, the entries of which are products of integers, and you ask about how many distinct numbers are to be found in the matrix.
Now, you have posted four times in this thread, and you have yet to inform us what those entries are. In particular, what is the entry in row i, colomn j? 


#16
Feb2412, 08:25 AM

Mentor
P: 18,334

Maybe you need to give some examples of the matrix you're looking at...



#17
Feb2412, 08:31 AM

Emeritus
Sci Advisor
PF Gold
P: 4,500

Here's a small matrix example of what he's talking about [tex] \left( \begin{array}{ccc} 1*1 & 1*2 & 1*3 \\ 2*1 & 2*2 & 2*3 \\ 3*1 & 3*2 & 3*3 \end{array} \right) [/tex] The question can be rephrased as: [tex] u(n) =  \{ a*b \\ a\leq n,\ b\leq n \} [/tex] calculate u(n). 


#18
Feb2412, 08:44 AM

P: 84

Thank you Office Shredder. What I meant was in fact that simple.
Let's even write it as M(i,j)=i*j for i=j=1,n. 


Register to reply 
Related Discussions  
A set A of n elements has n(n1)/2 subsets of 2 elements  Precalculus Mathematics Homework  2  
Count all even from 1 to n  Linear & Abstract Algebra  2  
Question: Can elements above iron actually be clusters of smaller elements?  Atomic, Solid State, Comp. Physics  3  
Some elements react with certain elements better than others...?  Chemistry  8  
Kronecker product on only a few elements in a matrix: How to align resulting elements  Linear & Abstract Algebra  0 