Question

I don't get this proof : prove that number of divisors of any positive number \(\large n\) is \(\large \le 2\sqrt{n}\)

Answer 1

edited the question, please see again :)

Answer 2

Is there any way to derive this usign divisors formula :

number of divisors of \(n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} \) is \((k_1+1)(k_2+1)\cdots (k_r+1)\)

Answer 3

Divisors come like this... a*b = The number we seek, n. Without loss of generality, let's say \(a \le b\). This leaves a = b for n a perfect square.

Let's just think about the number 'a'. What are it's possibilities.

1) It is limited to \(a \le \sqrt{n}\)
2) It is limited by \(Count(a) \ge Prime\;Numbers\;less\;than\;(or\;equal\;to) \sqrt{n}\)

Your unique prime factorization is a great way to go. How may ways are there to shuffle those things?

Answer 4

\(\large a \le b\) gives half (more or less) of the divisors, right ?

Answer 5

@tkhunny I haven't seen the count function outside of Excel... Does it behave at all like the floor function?

Answer 6

\[\large n = d*\dfrac{n}{d}\]

Answer 7

do you have any proof ?
cuz im thinking of something like this
\(\sqrt n \le n! \)
its only a though >.<
i wanna see a proof

Answer 8

http://math.stackexchange.com/questions/905170/the-number-of-divisors-of-any-positive-number-n-is-le-2-sqrtn

Answer 9

so if we assumed n is composite , then we cheking the factors \(\le \sqrt n\)
The Sieve of Erathosthens >.<

Answer 10

how is it related to sieve of eratosthenes ?
we're checking for divisors, not primes right ?

Answer 11

well first we know that primes factors \(\le \sqrt n\)
right ?
and any other factor is a formed from the factors hmm but i still need how to onclude the 2 part

Answer 12

It seems the upper limit is not strong,
is there any number which has divisors = \( 2\sqrt{n}\) ?

Answer 13

im not convinced with the upper thingy ,
my point is how many combination of the primes factors we could get less than n

Answer 14

Oh i get what you're trying

Answer 15

did you understand the proof in MSE ?

Answer 16

if we have
\(p_1,p_2,p_3,.., p_i\) ( primes factors )
then the number of primes factors is d\(\le \sqrt n\)

now :-
\(p_i,2p_i,3p_i,.., kp_i \)
\(p_i,p_i^2,p_i^3,.., p_i^c \)

such that \(kp_i <n , p_i^c <n\)
are all factors hmmm

Answer 17

The exact number of divisors is expressed as:

If \(s = k_{1} + k_{2} + k_{3} + ... + k_{r}\)

Then \({s}\choose{0}\)+\({s}\choose{1}\)+\({s}\choose{2}\)+...+\({s}\choose{s}\)

Answer 18

exactly ! number of divisors is a combination - number of different ways of choosing exponent of a prime number in the prime factorization

Answer 19

rash , i did understand but i dont understand why http://prntscr.com/4f4k51

Answer 20

yeah :o

Answer 21

ikram : seive of eratosthenes gives you number of prime factors are \(\le \sqrt{n}\)
I don't get your statements after this, could you please elaborate ? :)

Answer 22

this is what i meant to do xD
number of divisors is a combination - number of different ways of choosing exponent of a prime number in the prime factorization

but im not neat to say that >.<

Answer 23

http://prntscr.com/4f4k51

i don't understand that either, they're claiming stuff without explaining

Answer 24

ok so the question would be like this
if u have a set of primes ( that are also factors of n )\(A\) of size \(\sqrt n\) , how many factors of n you could form from A .

(or something like this )

Answer 25

i think we need the floor function series here :o

Answer 26

:3 not good with permentation
let
A=(p_1,p_2,p_3 ,....,p_k)

factors set =\( ( p_1,p_2,p_3 ,....,p_k , p_1^2,p_2^2,p_3^2\\ ,....,p_k^2 ,....p_1^r,p_2^r,p_3^r ,....,p_k^r , p_1p_2,p_1p_3 ,....,p_1p_k.... ect )\)

Answer 27

but with condition that any element <n :3

Answer 28

see if below makes sense :

\[\large n = d*\dfrac{n}{d}\]

Clearly either \(d\) or \(\dfrac{n}{d}\) is \(\large \le n\),

1) \(\color{Red}{1\le d \le \sqrt{n}} \implies n \ge \dfrac{n}{d} \ge \sqrt{n}\)

2) \(\sqrt{n} \le d \le n \implies \color{red}{ \sqrt{n} \ge \dfrac{n}{d} \ge 1}\)

Answer 29

that gives :


1) there can be atmost \(\color{Red}{\sqrt{n}}\) values possible for \(d\) less than or equal to \(\color{Red}{\sqrt{n}}\)
2) there can be atmost \(\color{Red}{\sqrt{n}}\) values possible for\( \dfrac{n}{d}\) less than or equal to \(\color{Red}{\sqrt{n}}\)

Answer 30

it make sense now :o

Answer 31

So, the upper limit for total number of divisors would be : \(\large \color{red}{\sqrt{n} + \sqrt{n}}\)

Answer 32

="(

Answer 33

that was ... >.<

Answer 34

same here, makes some sense now :)
did u get how \(\large \tau (n) = \prod \limits_{1\le i \le r} (k_i+1)\) ?

Answer 35

this one i know why

Answer 36

but could u proof it , using this ?

Answer 37

http://prntscr.com/4f4xbf

Answer 38

no , i know this >,<
ok nvm that was not my question

Answer 39

what was your question?

Answer 40

do you have another proof for d<= 2 sqrt n ?

Answer 41

So also, \(1 + 2^{s}\). Quite a bit simpler than the previous expression. Of course, expressing this in terms of 'n' is the real matter at hand.

Answer 42

I think it equals \(\large 2^s\) when \(\large n \) is square free : \(\large p_1^1 p_2^1 \cdots p_s^1\)

Answer 43

?

Answer 44

thanks everyone ! you would never know how much you have helped me !!

Answer 45

u solve it by ur own -_-

Answer 46

if \(\large n\) is square free, \(\large n\) has no prime exponent greater than 1,
so in the prime factorization, each prime has \(\large 2\) choices

Answer 47

if \(n\) is a product of \(s\) distinct primes, then total number of divisors would be : \(\large 2\times 2\times \cdots \text{s times} = 2^s\)

Answer 48

yeah

Answer 49

lets work one more last question for the day
new thread

Answer 50

hope its simple >.<