Finding number of ordered pairs with a given property

Revision en8, by typedeftemplate, 2019-09-24 05:36:37

Given an integer 1 <= N <= 100, and 1 <= MIN, MAX <= 10^5, how can I compute the number of ordered pairs (a_1, a_2, ..., a_N) such that MIN <= a_i <= MAX for any i, and gcd(a_1, a_i) = 1 for any i not equal to 1?

For example, when N = 3, MIN = 2, and MAX = 4, the valid configurations are (2,3,3), (3, 2, 2), (3, 4, 2), (3, 4, 4), (4, 3, 3), and (3, 2, 4), so the output should be "6".

I am pretty sure (not 100%) this is a DP problem, but I can't manage to come up with the solution. Also, obviously, every configuration with the first number prime is valid, but this doesn't have to be the case. Does anyone have any ideas? I have been stuck on this problem for a few days now. Maybe I'm going about it wrong, and there is a really simple solution? Print the answer modulo 10^9 + 7.

Side-note: Is it possible to get TeX to work in these blogs?

Tags #dp, #combinatorics, #number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English typedeftemplate 2019-09-24 05:36:37 35 Tiny change: ' solution?\n\n\nSide' -> ' solution? Print the answer modulo 10^9 + 7. \n\n\nSide'
en7 English typedeftemplate 2019-09-24 05:35:10 50
en6 English typedeftemplate 2019-09-24 05:34:31 2 Tiny change: 'and MAX = 3, the vali' -> 'and MAX = 4, the vali'
en5 English typedeftemplate 2019-09-24 05:28:59 2 Tiny change: '2, ..., a_n) such tha' -> '2, ..., a_N) such tha'
en4 English typedeftemplate 2019-09-24 05:09:31 2 Tiny change: 'le to get LaTeX to wor' -> 'le to get TeX to wor'
en3 English typedeftemplate 2019-09-24 05:09:16 68
en2 English typedeftemplate 2019-09-24 05:08:31 116
en1 English typedeftemplate 2019-09-24 05:07:50 665 Initial revision (published)