How many coprimes ?

Dec 2015
972
128
Earth
How many coprimes are in interval \(\displaystyle [1,100]\).
method required !
 
Aug 2012
2,482
776
Is a coprime a composite? That's not a standard term. Two numbers are coprime if the have no common factors, like 25 and 36. The word coprime refers to pairs of integers. Clarify question please.
 
May 2013
94
10
so, a coprime is two numbers that don't share any factors
2 is coprime to 50 numbers between 1 and 100
3 is coprime to 66 numbers between 1 and 100
4 is also coprime to 50 numbers between 1 and 100.
5 is coprime to 80 numbers between 1 and 100.
and so on.
 

skipjack

Forum Staff
Dec 2006
21,379
2,410
The number of coprime pairs of integers, where both integers are in the interval [1, 100] could be counted by a
fairly simple computer program. However, clarification is needed as to whether (1, 2) and (2, 1) should be counted as two pairs or just one.
 

skipjack

Forum Staff
Dec 2006
21,379
2,410
Each Integer greater than 1 is either composite or prime (not both). What do you mean?
 
  • Like
Reactions: idontknow
Aug 2012
2,482
776
composite-primes.
We don't know what you're asking, can you give an example?

Meanwhile the question you don't seem to have intended turns out to be interesting: counting the coprime pairs. I worked out the answer using the inclusion-exclusion principle and got 6231 coprime pairs. Then I wrote a Python program and got 6262 coprime pairs. So I'm close and have an error either in my combinatorics or my code. Getting late so I'll have to wait till tomorrow to resolve the discrepancy.

What I did was to count the number of noncoprime pairs and subtract that from 10,000.
For example if both members of a pair are divisible by 2 that's a noncoprime. For convenience I say "2 divides the pair."

There are 50 even numbers between 1 and 100, computed as 100/2 = 50. All divisions are integer divisions throughout. The number of such pairs is 50^2 = 2500.

Likewise there are 100/3 = 33^2 = 1089 pairs divisible by 3.

But now I've counted pairs like (6,6) twice. I have to subtract off (100/6)^2. Continuing like this I have to subtract off all the pairwise intersections. But if a pair is in a three-fold intersection I've overcounted the subtractions and have to add that one back. This can get confusing but the inclusion-exclusion principle lets you just crank it out using a formula. You take the sum of all the odd-fold intersections (including the original sets of pairs divisible by 2, 3, 5, and 7); minus the sum of all the even-fold pairs.

Gotta go find my 31 pair discrepancy.

(Edit) -- I've got it, small arithmetic mistake. 6262 coprime pairs, computed two different ways, by inclusion-exclusion and by program.
 
Last edited:
  • Like
Reactions: idontknow
Dec 2015
972
128
Earth
So how to get number of primes in that given interval ? Method required! (approximations , inequalities ,etc..)
 

skipjack

Forum Staff
Dec 2006
21,379
2,410
My program, which I have confidence in, gives 6087 coprime pairs.
 
Aug 2012
2,482
776
My program, which I have confidence in, gives 6087 coprime pairs.
Check your program. I got 6262 two different ways: by inclusion-exclusion and via a program.

Edit ... checking my program, doubting my sanity. Anything's possible.
 
Last edited: