Finding Non-Divisible Integers under n: A Combinatorics Problem

In summary, the conversation discusses a problem of finding the number of positive integers less than n that are not divisible by a set of given prime numbers. The solution for a smaller set of primes is described using the principle of inclusion and exclusion, but it is noted that this method would be difficult for a larger set of primes. Another approach using the Chinese Remainder Theorem is suggested, which involves finding a unique number x that is not divisible by any of the given primes. This number can then be used to calculate the number of integers less than the given value of n that are not divisible by any of the given primes.
  • #1
physicsmath94
2
0
I am trying to find a way to calculate the number of positive integers less than n such that these numbers are not divisible by the prime numbers 2,3,5,7,11,13.

If the problem were instead for prime numbers 2,3,5, then the solution is fairly simple. I used principle of inclusion and exclusion to solve the problem.

for example if n=50

[49/2] + [49/3] + [49/5] - [49/6] - [49/10] - [49/15] + [49/30] = 35

49-35 = 14 integers under 50 that are not divisible by 2,3, or 5.

At first i thought this method might be applicable if the question included primes: 2,3,5,7,11,13. But doing principle inclusion exclusion would take a Lot of calculator bashing. is there a smarter way to solve this problem for n= 60000
 
Physics news on Phys.org
  • #2
? One approach is to use the Chinese Remainder Theorem. With this approach, we can determine the number of integers less than 60000 which are not divisible by any of the given primes. The Chinese Remainder Theorem states that if n1, n2, n3,..., nk are pairwise relatively prime positive integers, then for any set of integers a1, a2, a3, ..., ak there exists a unique integer x such that:x ≡ a1 mod n1x ≡ a2 mod n2...x ≡ ak mod nkFor our problem, we can let n1 = 2, n2 = 3, n3 = 5, n4 = 7, n5 = 11, and n6 = 13. Then we can let a1 = 1, a2 = 2, a3 = 3, a4 = 4, a5 = 5, and a6 = 6. This will give us a unique number x such that x is not divisible by any of the given primes. The number of integers less than 60000 which are not divisible by any of the given primes is then 60000 - x.
 

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arranging objects or elements in a systematic way.

2. What is a combinatorics problem?

A combinatorics problem is a mathematical problem that involves counting or arranging objects or elements in a specific way, often using techniques such as permutations, combinations, and the binomial theorem.

3. What are some real-life applications of combinatorics?

Combinatorics has many real-life applications, including in computer science, genetics, cryptography, and data analysis. For example, it can be used to determine the number of possible passwords of a given length, or to analyze genetic sequences.

4. How do you approach solving a combinatorics problem?

The approach to solving a combinatorics problem may vary, but generally it involves identifying the type of problem (e.g. permutation, combination) and then using the appropriate formulas and techniques to arrive at the solution.

5. Can combinatorics be used to solve real-world problems?

Yes, combinatorics has many practical applications and can be used to solve various real-world problems, from optimizing schedules to analyzing data sets. It is a useful tool for problem-solving in many fields.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
738
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
829
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
912
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
Back
Top