Find the smallest positive integer that has precisely 240 positive divisors.
240 = 2^4 * 3 * 5
That could be 2 * 2 * 2 * 2 * 3 * 5 which could imply the number sought was
2^4 * 3^2 * 5 * 7 * 11 * 13 = 720,720
(Each factor of 2 in 240 implies a prime factor to the 1st power; a factor of 3 in 240 implies a prime factor squared; the factor of 5 in 240 implies a prime factor to the 4th power.)
There could be alternate factorings of 240, such as 2 * 2 * 3 * 4 * 5, which would correspond to the number's being
2^4 * 3^3 * 5^2 * 7 * 11 = 831,600
Clearly the 720,720 is the lower of the two and in fact this program verifies it's the lowest of such reworkings:
DefDbl A-Z
Dim crlf$, fct(20, 1)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For n = 1 To 1000000
f = factor(n)
divisors = 1
For i = 1 To f
divisors = divisors * (fct(i, 1) + 1)
Next
If divisors = 240 Then
Text1.Text = Text1.Text & n & crlf
For i = 1 To f
Text1.Text = Text1.Text & " " & fct(i, 0) & Str(fct(i, 1)) & crlf
Next
End If
DoEvents
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Function factor(num)
diffCt = 0: good = 1
n = Abs(num): If n > 0 Then limit = Sqr(n) Else limit = 0
If limit <> Int(limit) Then limit = Int(limit + 1)
dv = 2: GoSub DivideIt
dv = 3: GoSub DivideIt
dv = 5: GoSub DivideIt
dv = 7
Do Until dv > limit
GoSub DivideIt: dv = dv + 4 '11
GoSub DivideIt: dv = dv + 2 '13
GoSub DivideIt: dv = dv + 4 '17
GoSub DivideIt: dv = dv + 2 '19
GoSub DivideIt: dv = dv + 4 '23
GoSub DivideIt: dv = dv + 6 '29
GoSub DivideIt: dv = dv + 2 '31
GoSub DivideIt: dv = dv + 6 '37
If INKEY$ = Chr$(27) Then s$ = Chr$(27): Exit Function
Loop
If n > 1 Then diffCt = diffCt + 1: fct(diffCt, 0) = n: fct(diffCt, 1) = 1
factor = diffCt
Exit Function
DivideIt:
cnt = 0
Do
q = Int(n / dv)
If q * dv = n And n > 0 Then
n = q: cnt = cnt + 1: If n > 0 Then limit = Sqr(n) Else limit = 0
If limit <> Int(limit) Then limit = Int(limit + 1)
Else
Exit Do
End If
Loop
If cnt > 0 Then
diffCt = diffCt + 1
fct(diffCt, 0) = dv
fct(diffCt, 1) = cnt
End If
Return
End Function
The output being the following, where the valid number with 240 divisors is on the first line of each group followed by a list of its prime factors, with the power to which that factor is raised.
Second place is indeed the
831,600 = 2^4 * 3^3 * 5^2 * 7 * 11
we found above, resulting from a factoring of 240 = 5 * 4 * 3 * 2 * 2
720720
2 4
3 2
5 1
7 1
11 1
13 1
831600
2 4
3 3
5 2
7 1
11 1
942480
2 4
3 2
5 1
7 1
11 1
17 1
982800
2 4
3 3
5 2
7 1
13 1
997920
2 5
3 4
5 1
7 1
11 1
|
Posted by Charlie
on 2016-08-15 10:27:39 |