All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Factor distribution in a school (Posted on 2019-11-13) Difficulty: 3 of 5
In a school, each student is assigned a positive factor of 6060, but no student's number is the greatest common divisor of any two student numbers (one of which may be their own).

What is the maximum number of students in this school?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
maybe a soln..... | Comment 1 of 4

I get 8,388,608 students.  

I took the term "factor" to mean "divisor with no remainder" as opposed to "prime factor").

With 60=2^2 x 3 x 5, a possible factor a student "i" might have (all else aside) is:
(2^j_i) x (3^k_i)  x (5^l_i), 

where, for n students, i goes from 1 to n. Each j_i, k_i, and l_i value can range from 0-120, 0-60, 0-60, respectively. 

For a pair of students, i1, i2, to neither have the GCD of the pair, they must have 2 of the i,j,k exponents such that one student has a greater exponent and also a lesser exponent than the other. This is true because their GCD is the number formed using the "floor" of their exponents, when considered pairwise). E.g.: j_i1 > j_i2 and k_i1<k_i2. For a pair of students, this could happen in any of six ways, since each has their own set of three exponents. 

So, the problem becomes one of finding the number of pairs of triplets, denoted {}, with this property, from set:
 [{(0,0,0), (0,0,0)}, {(0,0,0), (0,0,1)}, ..., {(0,0,0), (120,60,60), {(0,0,1),(0,0,0)}, {(0,0,1),(0,0,1)}, ..., {(120,60,60) , (120,60,60)}] 

and dividing the count by 2, since each satisfactory pair will be counted twice.

Being lazy, I wrote a program to count these:

        program i60


        do 1 i=0,120

         do 1 j=0,60

          do 1 k=0,60

           do 1 i1=0,120

            do 1 j1=0,60

             do 1 k1=0,60


        1       (

        2       (

1       continue

        print*,'tot = ',cnt,cnt/2.


rabbit-3:~ lord$ g77 -o i6 i6.f

rabbit-3:~ lord$ i6

 tot =    16777216.0       8388608.00    

Edited on November 13, 2019, 6:20 pm
  Posted by Steven Lord on 2019-11-13 11:35:51

Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (2)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information