 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Factor distribution in a school (Posted on 2019-11-13) 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

cnt=0

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

if((i.gt.i1.and.j.lt.j1).or.(i.lt.i1.and.j.gt.j1).or.

1       (i.gt.i1.and.k.lt.k1).or.(i.lt.i1.and.k.gt.k1).or.

2       (j.gt.j1.and.k.lt.k1).or.(j.lt.j1.and.k.gt.k1))cnt=cnt+1

1       continue

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

end

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:

 Search: Search body:
Forums (2)