JEEOlympiad
How many integers n with 1 <= n <= 10000 are divisible by at least…
Question
How many integers n with 1 <= n <= 10000 are divisible by at least two of the four numbers 4, 9, 25, and 7?
✓ Verified answer: 856checked by our engine — not a guess
Step-by-step solution
The four divisors 4, 9, 25, 7 are pairwise coprime, so the lcm of any subset is just the product.
Let T_j be the sum over all j-subsets of floor(10000 / product).
Pairwise products and their floor counts (T_2): 4·9=36 ->277; 4·25=100 ->100; 4·7=28 ->357; 9·25=225 ->44; 9·7=63 ->158; 25·7=175 ->57.
Sum T_2 = 277+100+357+44+158+57 = 993.
Triple products (T_3): 4·9·25=900 ->11; 4·9·7=252 ->39; 4·25·7=700 ->14; 9·25·7=1575 ->6. Sum T_3 = 70.
Quadruple (T_4): 4·9·25·7=6300 ->1. So T_4 = 1.
The count of n divisible by at least two is obtained from the 'exactly k' sieve: E_k = sum_{j>=k} (-1)^{j-k} C(j,k) T_j.
Then answer = E_2 + E_3 + E_4.
Equivalently, number divisible by >=2 = T_2 - 2·T_3 + 3·T_4 = 993 - 2·70 + 3·1 = 993 - 140 + 3 = 856.
Final answer856
Stuck on a problem like this?
Paste any JEE or NEET question — verified working, a confidence %, and an honest “not sure” instead of a bluff.
Solve my doubt →More Combinatorics solutions
How many functions f from {1,2,3,4,5,6,7,8} onto {1,2,3,4} (i.e.…JEE · MathA token moves on the integer grid from (0,0) to (7,5) using only unit…JEE · MathFind the number of integer solutions (x1, x2, x3, x4) to x1 + x2 + x3…JEE · MathHow many permutations of the numbers 1,2,...,9 have exactly two fixed…JEE · MathConsider all distinguishable arrangements of the multiset of letters…JEE · MathTen distinct balls are distributed into four distinct boxes labelled…JEE · MathHow many subsets S of {1, 2, 3, ..., 15} contain no two consecutive…JEE · MathHow many permutations p of (1, 2, 3, 4, 5, 6, 7, 8) satisfy p(i) is…JEE · Math