how to count elements


by epsi00
Tags: elements
epsi00
epsi00 is offline
#1
Feb23-12, 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 non-unique elements is the same since we know the total number of elements and can get the unique or non-unique 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 non-unique 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.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
bluekuma
bluekuma is offline
#2
Feb23-12, 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 non-prime number has at least two ways to generate it)
epsi00
epsi00 is offline
#3
Feb23-12, 08:53 AM
P: 84
Quote Quote by bluekuma View Post
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 non-prime number has at least two ways to generate it)
You are right of course about 6. 1*6 is discounted because it applies to every number. I am interested in counting non unique number of the form, with p primes
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 )

micromass
micromass is offline
#4
Feb23-12, 11:16 AM
Mentor
micromass's Avatar
P: 16,690

how to count elements


Are you asking for the prime factorization of 1000! ???

See homepage.smc.edu/kennedy_john/NFACT.PDF
epsi00
epsi00 is offline
#5
Feb23-12, 01:15 PM
P: 84
Quote Quote by micromass View Post
Are you asking for the prime factorization of 1000! ???

See homepage.smc.edu/kennedy_john/NFACT.PDF
nope.

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?
ramsey2879
ramsey2879 is offline
#6
Feb23-12, 05:01 PM
P: 891
Quote Quote by epsi00 View Post
nope.

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?
If i understand you correctly, the numbers a*b are unique if and only if b is always a prime greater than or equal to than a, and a is either prime or 1. In other words 1,2,3,4,5,6,7,9,10,11,13... are unique. So just count the number of primes less than 1000 then multiply that number by that number plus 1.
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.
Norwegian
Norwegian is offline
#7
Feb23-12, 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)?
SteveL27
SteveL27 is offline
#8
Feb23-12, 07:04 PM
P: 799
Quote Quote by Norwegian View Post
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)?
I think the word "unique" is being interpreted two different ways. I agree with you, the number of unique products is what the word "unique" should mean here. So if 30 = 2x15 = 3x10 we only count it once. In this case it's easy to see that these are just all numbers between 1 and n, plus the number of composites between n and n^2. (Because you can't generate any of the primes between n and n^2 as a product of numbers less than n, but you can so generate ALL of the composites).

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.
Norwegian
Norwegian is offline
#9
Feb23-12, 07:55 PM
P: 144
Quote Quote by SteveL27 View Post
In this case it's easy to see that these are just all numbers between 1 and n, plus the number of composites between n and n^2. (Because you can't generate any of the primes between n and n^2 as a product of numbers less than n, but you can so generate ALL of the composites).
I just want to remark that the statement in the above paragraph is wrong. All composites up to n2 can certainly not be written as a product of two numbers n or less. (n=3, 8= ?)
SteveL27
SteveL27 is offline
#10
Feb23-12, 08:02 PM
P: 799
Quote Quote by Norwegian View Post
I just want to remark that the statement in the above paragraph is wrong. All composites up to n2 can certainly not be written as a product of two numbers n or less. (n=3, 8= ?)
Yes thanks for the correction.
ramsey2879
ramsey2879 is offline
#11
Feb23-12, 10:11 PM
P: 891
Quote Quote by epsi00 View Post
nope.

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?
To get an understanding of what you want, let me set forth my understanding. You want to count all the numbers that can be obtained by multiplying two integers each of which are less than 1001, and you don't want to count a given number more than once. When you keep talking of a 10 by 10 matrix, 40 by 40 matrix, I envision a multiplication table. I think you are in fact referring to an a 1000 by 1000 matrix, which is a table for multiplication by numbers from 1 to 1000. In such a table primes are not unique because they appear twice. On column 1 as P*1 and on row 1 as 1*P. Composites of two or more primes also appear twice, since A*B appears in row A, column B and in row B, column A. The only unique elements are 1 and the squares of prime numbers greater than 31 and less than 1000 and certain other squares e.g. 1000000. So 37*37 lies on the diagonal and is unique because it is greater than 1000. 31*31 is not unique since it appears in the multiplication table three times: 1*961, 961* 1 and 31*31. I don't understand how to count the non-unique numbers only once though. The numbers range up to 1000000 but certainly do not include every number up to 1000000 such as primes greater than 1000.
ramsey2879
ramsey2879 is offline
#12
Feb23-12, 10:34 PM
P: 891
Quote Quote by SteveL27 View Post
I think the word "unique" is being interpreted two different ways. I agree with you, the number of unique products is what the word "unique" should mean here. So if 30 = 2x15 = 3x10 we only count it once. In this case it's easy to see that these are just all numbers between 1 and n, plus the number of composites between n and n^2. (Because you can't generate any of the primes between n and n^2 as a product of numbers less than n, but you can so generate ALL of the composites).
Of course you dont mean to include composites of primes between n and (n^2)/2 as those also can not be counted since no product of two numbers less than a prime P can equal 2P, 3P etc.
dodo
dodo is offline
#13
Feb24-12, 02:49 AM
P: 688
Quote Quote by Norwegian View Post
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.
I believe the OP's intention was to exclude products by 1; maybe a,b should be taken from {2,3,...,n}. Other than that, this was also how I interpreted the OP's request.

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 n2 have a divisor d<=n, such that k/d is also <= n?
epsi00
epsi00 is offline
#14
Feb24-12, 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 ( n-m) whichever is easier to calculate?
Norwegian
Norwegian is offline
#15
Feb24-12, 08:22 AM
P: 144
OK, so you take an n*n-matrix, 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?
micromass
micromass is offline
#16
Feb24-12, 08:25 AM
Mentor
micromass's Avatar
P: 16,690
Maybe you need to give some examples of the matrix you're looking at...
Office_Shredder
Office_Shredder is offline
#17
Feb24-12, 08:31 AM
Mentor
P: 4,499
Quote Quote by Norwegian View Post
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?
It's i*j

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).
epsi00
epsi00 is offline
#18
Feb24-12, 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(n-1)/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