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