Factors of N^2

Number Theory Level 5

Let $N=11 ^ 2 \times 13 ^ 4 \times 17 ^ 6$ . How many positive factors of $N^2$ are less than $N$ but not a factor of $N$ ?

Details and assumptions

You may choose to read divisors of an integer .

The answer is 188.

5 solutions

Mark Lao
May 20, 2014

Theorem: Let $M$ be a natural number. If $M^2$ has $n$ distinct positive factors, then exactly $\frac{n-1}{2}$ of them are strictly less than $M$ .

Proof: If $k\neq M$ is a factor of $M^2$ , then one of the numbers $k, \frac {M^2}{k}$ is strictly less than $M$ and the other is strictly greater than $M$ . This allows us to split the factors of $M^2$ , which are not $M$ , into 2 equal groups. Thus, there are exactly $\frac {n-1}{2}$ distinct positive factors of $M^2$ that are strictly less than $M$ .

Back to the original problem, we can compute for the number of factors of $N$ and $N^2$ (read the blog post). There are $(2+1)(4+1)(6+1) = 3*5*7=105$ factors of $N$ and $(4+1)(8+1)(12+1) = 5*9*13=585$ factors of $N^2$ . Using the above theorem, we know that $\frac{585-1}{2} = 292$ of the factors of $N^2$ are strictly less than $N.$ And among these, $105-1=104$ are factors of $N$ (we have to exclude $N$ itself). Hence, $292-104=188$ factors of $N^2$ are simultaneously less than N and are not factors of $N$ .

[Slight edits for clarity - Calvin]

The pairing used in the theorem is a great example of creating sets (bijections) to help us count the number of occurrences.

Calvin Lin Staff - 7 years ago

Calvin Lin Staff
May 13, 2014

We have that $N^2 = 11 ^ {4} \times 13 ^{8} \times 17 ^{12}$ , so $N^2$ has $(4+1)\times (8+1) \times (12+1)$ divisors. For every divisor $d < N$ there is another divisor of $N^2$ , $\frac{N^2}{d} > N$ . Only $N$ does not pair up with another divisor as $N\times N = N^2$ . Thus there are $\frac {5 \times 9 \times 13 -1 }{2} = 292$ pairs of divisors, with $292$ divisors of $N^2$ that are less than $N$ .

Clearly any divisor of $N$ is a divisor of $N^2$ , thus we subtract those that are divisors of $N$ , excluding $N$ . There are $(2+1) \times (4+1) \times (6+1) -1 =104$ divisors of $N$ less than $N$ . Hence, there are $292 - 104 = 188$ divisors of $N^2$ that are less than $N$ and are not divisors of $N$ .

Anvesh Muttavarapu
May 20, 2014

NUMBER OF DIVISORS FOR 'N' =3 5 7 =105; NUMBER OF DIVISORS FOR 'N^2'= 5 9 13 =585; NUMBER OF DIVISORS FOR 'N^2' LESS THAN OR EQUAL TO 'N'= [585/2] = 293; NUMBER OF DIVISORS FOR 'N^2' LESS THAN OR EQUAL TO 'N' AND NOT DIVISORS FOR 'N' = 293-105=188

Nikola Djuric
Dec 9, 2014

Let A=11^ x 13^b x 17^c be Such a number.We have 26 cases: 1)a=3,b<5,c<7 There is (4+1)*(6+1)-1=34 solutions 2)a=4,b<5,c<7 There is (4+1)(6+1)-3=32 solutions 3)b=5,a<3,c<7 (2+1)(6+1)-2=19 4)b=6,a<3,c<7 (2+1)(6+1)-4=17 5)b=7,a<3,c<7 (2+1)(6+1)-7=14 6)b=8,a<3,c<7 (2+1)(6+1)-9=12 7)c=7,a<3,b<5 (2+1)(4+1)-3=12 8)c=8,a<3,b<5 (2+1)(4+1)-6=9 9)c=9,a<3,b<5 (2+1)(4+1)-9=6 10)c=10,a<3,b<5 (2+1)(4+1)-22=3 11)c=11,a<3,b<5 (2+1)(4+1)-14 12)c=12 no solutions 13)a=3,b=5,c<7 7-2=5 14)a=3,b=6,c<7 7-3=4 15)a=3,b=7,c<7 7-4=3 16)a=3,b=8,c<7 7-5=2 17)a=4,b=5,c<7 7-3=4 18)a=4,b=6,c<7 7-4=3 19)a=4,b=7,c<7 7-5=2 20)a=4,b=8,c<7 7-6=1 21)a=3,c=7,b<5 5-3=2 22)a=3,c=8,b<5 5-4=1 23)a=3,c>8,b<5 no solutions 24)a=4,c=7,b<5 5-3=2 25)a=4,c>7,b<5 no solutions 26)all other cases no solutions There is 34+32+19+17+14+12+12+9+6+3+1+5+4+3+2+4+3+2+1+2+1+2=188 Such numbers...

Lu Chee Ket
Dec 1, 2015

1331
22627
384659
6539203
111166451
1889829667
32127104339
546160773763
9284733153971
17303
294151
5000567
85009639
1445163863
24567785671
417652356407
7100090058919
224939
3823963
65007371
1105125307
18787130219
319381213723
5429480633291
2924207
49711519
845095823
14366628991
244232692847
4151955778399
70583248232783
38014691
646249747
10986245699
186766176883
3175025007011
53975425119187
494190983
8401246711
142821194087
2427960299479
41275325091143
6424482779
109216207243
1856675523131
31563483893227
83518276127
1419810694159
24136781800703
1085737589651
18457539024067
14641
248897
4231249
71931233
1222830961
20788126337
353398147729
6007768511393
190333
3235661
55006237
935106029
15896802493
270245642381
4594175920477
78100990648109
2474329
42063593
715081081
12156378377
206658432409
3513193350953
59724286966201
32166277
546826709
9296054053
158032918901
2686559621317
45671513562389
418161601
7108747217
120848702689
2054427945713
34925275077121
5436100813
92413713821
1571033134957
26707563294269
70669310569
1201378279673
20423430754441
918701037397
15617917635749
11943113486161
371293
6311981
107303677
1824162509
31010762653
527182965101
8962110406717
4084223
69431791
1180340447
20065787599
341118389183
5799012616111
44926453
763749701
12983744917
220723663589
3752302281013
63789138777221
4826809
82055753
1394947801
23714112617
403139914489
6853378546313
53094899
902613283
15344425811
260855238787
4434539059379
75387164009443
584043889
9928746113
168788683921
2869407626657
48779929653169
62748517
1066724789
18134321413
308283464021
5240818888357
690233687
11733972679
199477535543
3391118104231
57649007771927
7592570557
129073699469
2194252890973
37302299146541
815730721
13867422257
235746178369
4007685032273
68130645548641
8973037931
152541644827
2593207962059
44084535355003
98703417241
1677958093097
28525287582649
410338673
5334402749
69347235737
901514064581
11719682839553
4513725403
58678430239
762819593107
9916654710391
49650979433
645462732629
8391015524177
6975757441
90684846733
1178903007529
15325739097877
76733331851
997533314063
12967933082819
844066650361
10972866454693
118587876497
1541642394461
20041351127993
1304466641467
16958066339071
14349133056137
2015993900449
26207920705837
22175932904939
34271896307633

PROGRAM Count_11p2_13p4_17p6; {188}

USES CRT;

CONST
     N11 = 62672100746.2727;
     N13 = 224665065.307692;
     N17 = 203287.117647059;

VAR
   i, j, k, count: BYTE;
   word_count, i_count: WORD;
   p: EXTENDED;
   s, collect, list: ARRAY[1..255] OF EXTENDED;
   ic: ARRAY[1..255] OF BYTE;
   f: TEXT;

   FUNCTION Product(i, j, k: BYTE): EXTENDED;

   VAR
      num: EXTENDED;
      c: BYTE;

   BEGIN
        num:=1.0;
        IF i>0 THEN
           FOR c:=1 TO i DO
               num:=num*11.0;
        IF j>0 THEN
           FOR c:=1 TO j DO
               num:=num*13.0;
        IF k>0 THEN
           FOR c:=1 TO k DO
               num:=num*17.0;
        Product:=num
   END;

BEGIN
     CLRSCR;
     count:=0;
     FOR i:=1 TO 255 DO
     BEGIN
         s[i]:=0.0;
         collect[i]:=0.0;
         list[i]:=0.0;
         ic[i]:=0
     END;

     FOR i:=0 TO 1 DO
      FOR j:=0 TO 8 DO
       FOR k:=0 TO 12 DO
       BEGIN
        p:=Product(i, j, k);
        IF p<=N11 THEN
        BEGIN
             INC(count);
             s[count]:=p*1331.0;
             WRITELN(p:1:0)
        END
      END;
     WRITE('Count = ', count);
     READLN;

     FOR j:=0 TO 3 DO
      FOR i:=0 TO 4 DO
       FOR k:=0 TO 12 DO
       BEGIN
        p:=Product(i, j, k);
        IF p<=N13 THEN
        BEGIN
             INC(count);
             s[count]:=p*371293.0;
             WRITELN(p:1:0)
        END
       END;
     WRITE('Count = ', count);
     READLN;

     FOR k:=0 TO 5 DO
      FOR i:=0 TO 4 DO
       FOR j:=0 TO 8 DO
       BEGIN
        p:=Product(i, j, k);
        IF p<=N17 THEN
        BEGIN
             INC(count);
             s[count]:=p*410338673.0;
             WRITELN(p:1:0)
        END
       END;
     WRITE('Count = ', count);
     READLN;

     word_count:=0;
     FOR i:=1 TO count DO
     BEGIN
      i_count:=0;
      FOR j:=1 TO count DO
       IF ABS(s[i]-s[j])<5E-4 THEN
       BEGIN
          INC(word_count);
          INC(i_count);
          ic[i]:=i_count;
          IF i_count=1 THEN
             collect[j]:=s[j]
       END;
      END;
     WRITE('Equals: ', word_count);
     READLN;

     j:=0;
     FOR i:=1 TO count DO
     BEGIN
          IF collect[i]<>0.0 THEN
          BEGIN
               INC(j);
               list[j]:=collect[i];
               WRITE(j, ' ', collect[i]:1:0);
               READLN
          END
     END;
     {
     ASSIGN(f, 'The_188.TXT');
     REWRITE(f);
     FOR i:=1 TO j DO
         WRITELN(f, list[i]:1:0);
     CLOSE(f);
     WRITELN('Saved file as The_188.TXT');
     }
     REPEAT UNTIL READKEY=#27
END.

Answer: $\boxed{188}$

Factors of N^2

The answer is 188.

5 solutions

0 pending reports