Peter
Peter Campbell Smith

Divisors and digits

Weekly challenge 141 — 29 November 2021

Week 141: 29 Nov 2021

Task 1

Task — Number divisors

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

Examples


Example 1:
24 is the first such number having exactly 8 divisors.
1, 2, 3, 4, 6, 8, 12 and 24.

Analysis

The solution to this is easy enough, even without using any external modules, in that all 10 numbers are less than 100.

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

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 $k divisors is a reasonably small number. But for primes, the smallest such integer appears always to be 2 ** ($k - 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 $k divisors is 3 ** ($k - 1) and the third lowest is 5 ** ($k - 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.

Try it 

Try running the script with any input:



example: 20



example: 10

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2021-11-29
# PWC 141 task 1

use v5.20;
use warnings;
use strict;

my ($test, @tests, $try, $divisor, $dividend, $key, $count, $string, $num, $how_many, $num_divisors,
    $max_try, $z);

# inputs - pairs of number of results to show and number of divisors required
@tests = ([10, 8]);
$max_try = 10000;

# loop over tests
for $test (@tests) {
    ($how_many, $num_divisors) = @$test;
    say qq[\nSmallest $how_many numbers having $num_divisors divisors:];

    # initialise
    $num_divisors --;
    $how_many -= 1;
    $num = 0;

    # loop over integers
    TRY: for $try (2 .. $max_try) {
        $count = 0;     # number of divisors found
        $string = '';   # list of divisors

        # loop over potential divisors
        for $divisor (1 .. int($try/2)) {
            $dividend = $try/$divisor;

            # if it is a divisor
            if ($dividend eq int($dividend)) {
                $count ++;
                $string .= qq[$divisor, ];
                next TRY if $count > $num_divisors;   # give up if there are too many
            }
        }

        # if there were exactly the number of divisors requested we have an answer
        if ($count == $num_divisors) {
            say qq[$try has divisors $string$try];    # add the number itself to the list
            last if $num ++ >= $how_many;               # stop if we have enough answers
        }
    }
}

Output


Smallest 10 numbers having 8 divisors:
24 has divisors 1, 2, 3, 4, 6, 8, 12, 24
30 has divisors 1, 2, 3, 5, 6, 10, 15, 30
40 has divisors 1, 2, 4, 5, 8, 10, 20, 40
42 has divisors 1, 2, 3, 6, 7, 14, 21, 42
54 has divisors 1, 2, 3, 6, 9, 18, 27, 54
56 has divisors 1, 2, 4, 7, 8, 14, 28, 56
66 has divisors 1, 2, 3, 6, 11, 22, 33, 66
70 has divisors 1, 2, 5, 7, 10, 14, 35, 70
78 has divisors 1, 2, 3, 6, 13, 26, 39, 78
88 has divisors 1, 2, 4, 8, 11, 22, 44, 88

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain