web2.0calc
 

All Answers 358514 Answers

  Questions   
Sort: 
Jan 24, 2014
 #11
avatar+330 
0
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
Jan 24, 2014
 #3
avatar+118725 
0
Ayee!:
Melody:
Ayee!:

(s+4v)^5



To do this the long way would take forever. you need to use a binomial expansion. do you know what that is?

If this is a serious question then you are getting too old to put a question out like this.
In any adult forum you would be expected to demonstrate what you know, or why you are stuck, etc
I am happy to help you but i want it to be an interactive learning experience.

what is your problem, why can't you do this?

Melody.



I didnt know how to do it i think thats why i asked. You dont have to be SO mean.



[size=150]I am sorry Ayee, I didn't mean to sound so blunt. [/size]

If you want to expand ( a + b ) 5
this is you it would be done

5C0*a 0*b 5 + 5C1*a 1*b 4 + 5C2*a 2*b 3 + 5C3*a 3*b 2 + 5C4*a 4*b 1 + 5C5*a 5*b 0

Please notice that the power on the a plus the power on the b adds up to 5 for every term. Do you see what I mean?
Now, there is a nCr button on your calculator so is you want 5C3 you press 5 nCr 3 = and the answer is 10 - Make sure you can do that on your calculator.
Also, a 0 = 1, b 0=1, a 1=a and b 1=b so you can simplify all those bits, so now we have.
And, 5C0=1 and 5C5=1

So now we have
1*1*b 5 + 5*a 1*b 4 + 10*a 2*b 3 + 10*a 3*b 2 + 5*a 4*b 1 + 1*a 5*1

= b 5 + 5*a*b 4 + 10*a 2*b 3 + 10*a 3*b 2 + 5*a 4*b + a 5

Now, your question is not (a+b) 5 It is (s+4v) 5

So everywhere that there was an 'a', you can put 's'
and everywhere there was a 'b', you can put (4v).

=(4v) 5 + 5*s*(4v) 4 + 10*s 2*(4v) 3 + 10*s 3*(4v) 2 + 5*s 4*(4v) + s 5

= 4 5v 5 + 5*s*4 4v 4 + 10*s 2*4 3v 3 + 10*s 3*4 2v 2 + 5*s 4*4v + s 5

= 4 5v 5 + 5*s*256*v 4 + 10*s 2*64*v 3 + 10*s 3*16*v 2 + 5*s 4*4v + s 5

= 4 5v 5 + 1280*s*v 4 + 640*s 2*v 3 + 160*s 3*v 2 + 20*s 4*v + s 5

And, assuming that I didn't make any mistakes, that is your answer. It looks horrible but it is not too bad when you get used to it.
---------------------------------------------------------

Now, if this is all totally alian to you, you could do it this way.

(S+4v)(s+4v)=answer1
answer1*(s+4v) = answer2
answer2*(s+4v) = answer3
answer3*(s+4v) = answer4

and answer 4 IS (s+4v) 5
You CAN do it this way, it just takes a little longer

[size=150]Now Ayee, am I forgiven, I really am sorry that i upset you[/size].
Jan 24, 2014

1 Online Users

avatar

Top Users

avatar+130561 CPhill moderator
avatar+37193 ElectricPavlov
avatar+15147 asinus moderator
avatar+2451 Bosco
avatar+1837 blackpanther
avatar+1761 parmen
avatar+1572 kittykat
avatar+1317 AnswerscorrectIy
avatar+1011 gnistory
avatar+987 booboo44
avatar+869 cooIcooIcooI17

Sticky Topics