Walt wrote: What is the smallest positive integer with exactly 768 divisors.
******************
To restate in this form: "What number (N) is divisible by 768 (unique) Divisors that have a remainder of zero (0)."
Thought its application is used in analytic number theory and is related to (NOT the same as) Euler's Totient, and Sigma functions. (Eurler's Totient is the number of co-primes contained in a number). Theorem 329 of Wright and Hardy delves into the relation of the sum of divisors to the totient. A. Olofsson also broaches this.
A simple, but incomplete, solution is to use the number of divisors as an exponent of 2 -- (2 768). Though true, it's not the smallest number -- not even close.
The primary algorithm for solving this is the prime number decomposition theorem. That is to decompose a number into primes then reassemble them into a composite number. This is relatively simple to do. The difficult part is reducing the number to the lowest value.
This is a simplified statement of the prime number decomposition theorem:
Every integer N is the product of powers of prime numbers: If N is a power of a prime, N = P x, then it has x + 1 factors. Note: Every value >1 has at least two factors (divisors) --itself and 1. This only happens if the number is prime.
A more advanced restatement of how the (total) number of divisors of a number correlates to the number itself:
IF a positive integer N has the prime factorization of N = (P 1) (X1)* (P 2) (X2) * ... * (P k (Xk) for distinct primes P i and exponent of X k. Then each factor of N equals (X 1 + 1)(X 2 + 1) ... (X k + 1), which is the product of the factors.
(OK. Enough with the formal BS).
Eurler's Totient for a prime (P) is simply P-1. If a number is composite then factor out the primes, subtract 1 from each, then multiply the result of each P-1 together to find the number of divisors.
Note that many numbers can have exactly the same number of divisors -- observable in the example. The desired value is the lowest value that satisfies this condition.
Starting with a simple example: What is the smallest positive integer with exactly 10 divisors?
First, prime factor 10: P(10)= 2*5. We have two factors. From each of these subtract (1): 2 - 1 = 1 and 5 - 1 = 4. These will become the exponents of 2 primes that are currently unknown. We want the smallest value of N so start with the lowest primes. 2 and 3. P 1 1 * P 2 2 = 2 1 * =3 4 = 162. Though this is true because 162 has 10 integers that divide into it, it is not the smallest. The smallest are 3 1 * 2 4 = 48. You have to "play" with them to find the smallest.
It becomes more difficult for larger numbers and particularly for for primes with large exponents. For the record the 10 divisors for 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. For 162 they are 1, 2, 3, 6, 9, 18, 27, 54, 81, 162. Note: This formula tells how many divisors there are, but not what they are. Wolframalpha will calculate for a given value, the number of divisors and list them. Search for "divisor function". -- Note it will not solve this problem; however, after you solve for a number, it will tell you the number of divisors for that number, but not if it is the lowest that meets the criterion. That being said it seems a trivial matter to to write a program to do so.
To the actual question: What is the smallest positive integer with exactly 768 divisors?
Factor 768 = (2 8)*3 : 256 and 3. Subtract 1 for 63 and 2.
768= 256 * 3 ---> (P 1 255 * P 2 2) = 2 255 * 3 2 = N --- A massive number
The best approach is to "upper bound" the number by factoring 256 ---> 2 8 so we have 8 powers of 2 and of course the 3.
(Remember to subtract 1 from each) so we have a 2 and eight 1's as the exponents. Set them as exponents for this sequence.
(Generally the largest exponent for the smallest prime)
2 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23. Note: Exponents of 1 are not shown).
Attempt to reduce again by eliminating the highest primes. As a general process "elevate the lowest primes such that it does not exceed the value of the highest primes.
One way to keep track is to make a list of factors and exponents.
768 = 256 * 3
-------------------------------Exponent list
Factor 768 = 3*2*2*2*2*2*2*2*2--->2,1,1,1,1,1,1,1,1
Factor 768 = 3*4*2*2*2*2*2*2 --->2,3,1,1,1,1,1,1
Factor 768 = 3*4*4*2*2*2*2 --->2,3,3,1,1,1,1
Factor 768 = 6*4*4*2*2*2 --->5,3,3,1,1,1
Factor 768 = 6*4*2*2*2*2*2 --->5,3,1,1,1,1,1 <----This "looks" optimal
2 5 * 3 3 * 5 * 7 * 11 * 13 * 17 = 73513440
Many have said you can't add apples and oranges, but apples and oranges are related.
~~D~~
Edited for clarity