01 December 2021

Some prime thoughts on divisors

Perl Weekly Challenge 141, task 1, reads:

Write a script to find lowest 10 positive integers having exactly 8 divisors.

The solution to this is easy enough in that all 10 numbers are less than 100.

But what happens if we vary the number of divisors: find the lowest integer (k) having exactly n divisors?  The answers are as follows:

  • n=>k
  • 2 => 2 (1, 2)
  • 3 => 4   (1, 2, 4)
  • 4 => 6  (1, 2, 3, 6)
  • 5 => 16  (1, 2, 4, 8, 16)
  • 6 => 12  (1, 2, 3, 4, 6, 12)
  • 7 => 64  (1, 2, 4, 8, 16, 32, 64)
  • 8 => 24  (1, 2, 3, 4, 6, 8, 12, 24)
  • 9 => 36  ( 1, 2, 3, 4, 6, 9, 12, 18, 36)
  • 10 => 48  (1, 2, 3, 4, 6, 8, 12, 16, 24, 48)
  • 11 => 1024  (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024)
  • 12 => 60  (1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60)
  • 13 => 4096  (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096)
  • 14 => 192  (1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192)
  • 15 => 144 (1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144)
  • 16 => 120 (1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120)
    17 => 65536  (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536)
  • 18 => 180 (1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180)
  • 19 => 262144  (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144)
  • 20 => 240 (1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240)


So it appears that for non-prime n, the smallest integer having n divisors is a reasonably small number.  But for primes, the smallest such integer appears always to be 2**(n-1), which is usually a much larger number than the surrounding non-primes.

So:
3 => 4 = 2**2
5 => 16 = 2**4
7 => 64 = 2**6
11 => 1024 = 2**10
13 => 4096 = 2**12
17 => 65536 = 2**16
19 => 262144 = 2**18

It is also the case that the second-smallest prime integer having n divisors is 3**(n-1) and the third lowest is 5**(n-1) and so on.

It is clear that a power of 2 will always be divisible by any other power of 2 up to and including itself, and that it will have no other divisors. So it's understandable, for example, that 262144 = 2**18 has 19 divisors - 2**0 up to 2**18. 

But why does no smaller number also have 19 divisors? I have not been able to come up with a convincing explanation.



No comments:

Post a Comment