how to count elements

epsi00

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.

bluekuma

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

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

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

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

epsi00

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

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

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

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

I just want to remark that the statement in the above paragraph is wrong. All composites up to n² can certainly not be written as a product of two numbers n or less. (n=3, 8= ?)

SteveL27

Yes thanks for the correction.

ramsey2879

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

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

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 n² have a divisor d<=n, such that k/d is also <= n?

epsi00

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

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

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

Office_Shredder

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).