0
$\begingroup$

Problem:

Solve $$\log(n)\cdot\log(n+1) = 1$$ for natural numbers less than $100$

Source: The actual problem was a multiple choice question, and it goes something like this,

Find the maximum* value of $n$ such that both $(n+1)^n$ and $n^{(n+1)}$ divide $100!$

Then there were a few options that I don't remember (one was 24, and one 25 as I remember, but they were two digit natural numbers for sure)

As I sat down to solve it, I applied the following approach:

My attempt:

Let, $$100! = K(n+1)^n$$ where $K$ is an arbitrary integer And let, $$100! = C(n)^{(n+1)}$$ where $C$ is an arbitrary integer

To get rid of the 100! and solve for n exclusively, I did $$\frac{100!}{K} = (n+1)^n$$ Taking natural logarithm (yes, $ln$ or $log_e$ NOT $log_{10}$) on both sides $$ \log(\frac{100!}{K}) = (n)\log(n+1) $$ Upon differentiating** w.r.t $n$ we get, $$ 0 = \frac{n}{n+1} + \log(n+1)$$ Upon solving the second equation as above we get $$\log(n)\cdot\log(n+1) = 1$$ Now, how do I find $n$, I know plug and chug would work but I won't have a calculator on exam. All help appreciated!

  • maximum maybe the maximum number from the given options. I'm utterly sorry for not having the options

** is this approach trivial?

Edit: Answer is $15$ and the differentiating approach is faulty

$\endgroup$
  • 1
    $\begingroup$ I know that when you have a hammer everything looks like a nail, but using calculus like this to solve number theory problems about the divisibility of integers just doesn't work. Calculus is for questions about continuity and change over a continuum. Discrete math and integer divisibility is the polar opposite of that.... But I've got to give you credit for creativity. This and math.stackexchange.com/questions/2453219/… are ... atonishing ... and I mean that as a compliment. But, please, try to learn a little number theory. $\endgroup$ – fleablood Oct 4 '17 at 16:32
  • $\begingroup$ With all due to respect @fleablood I'm learning number theory for the test, but, please stop chasing me down on my approach; I'm learning. As you can see in my question description (the last line in bold), I do question my approach. It is faulty, and I knew this as soon as I did it, because the equation, after differentiating holds no 'memory' for 100!, you see it doesn't 'differentiate' between $100!$ or any other arbitrary constant from the ocean of real numbers :p $\endgroup$ – YourAverageEuler Oct 4 '17 at 17:13
  • 2
    $\begingroup$ I'm not chasing you down. But try to realize that calculus and any approach involving continuity are the wrong approach for discreet divisibility questions. And realize that the first approach you should try are prime factorizations and/or remainders. You calculus approaches are very clever and creative and show a keen curiosity and desire to approach and figure things out. I admire that. But it's almost ... tragic... that they are the wrong tools. Perhaps one thing to realize is solving for divisibility is not a quantitative question of approaching a measurable value. $\endgroup$ – fleablood Oct 4 '17 at 18:21
1
$\begingroup$

There are two problems with your approach.

You define $K$ and $C$ as "arbitrary constants". But their values are determined by the values of $n$. If you are considering $n$ to be variable, then $K$ and $C$ must be functions dependent upon $n$.

So when you differentiate you can't treat them as a constant.

Second as $n$ an integer, these are not differential functions. We can "eyeball" it by assuming $dn \approx 1$ but that is simply way too inaccurate to get any useful results about that precise divisibility of numbers.

===

Consider that there are $50$ even numbers $\le 100$. There are $25$ numbers divisible by $4$. $12$ numbers by $8$, $6$ by $16$, $3$ by $32$ and $1$ by $64$.

So $2^{50+25 + 12 + 6+3+1}=2^{97}|100!$ but $2^{98}\not \mid 100!$. So $n+1 \le 97$.

Likewise $3^{33+11+3+1}=3^{48}$ divides $100!$ but $3^{49}\not \mid 100!$.

And so on...

So the prime factorization of $100! = 2^{97}3^{48}5^{20+4=24}7^{14+2=16}11^{9}13^717^519^523^429^331^337^241^243^247^253*57*59*61*67*71*73*79*83*89*97$

We can see that for $n=16$ (one of the exponents; All lower exponents seem fairly obvious) that $16^{17}=2^{24}$ works but $17^{16}$ does not. But $n+1=16$ yields $n=15$ and $15^{16} = 3^{16}5^{16}$ and $16^{15} = 2^{60}$ both divide $100!$.

Now consider that $n > 16$ so $n^{n+1}|100!$ and $n+1>17$ so the only possible prime factors of $n$ are $2,3$ and $5$ and the as $(n+1)^n|100!$ while $n > 16$ so the only prime factors of $n+1$ are $2,3,5$. But $n, n+1$ are have not factors (other than $1$ in common).

So either: $n=2^a3^b5^c$ for some $a,b,c$ and $n+1 = 1$. (or vice versa). That's impossible as $n, n+1 > 1$.

or $n=2^a3^b$ and $n+1 = 5^c$. As $17\le n+1 \le 97$ so $n+1 = 25$ and $n=24$. And $24^{25} = 2^{75}*3^{25}$ divides $100!$ but $25^{24}= 5^{48}$ does not. Vice versa if $n = 5^c$ and $n+1=2^a3^b$ we'd have $n=15$ and $n+1 = 26\ne 2^a3^b$.

or $n$ and $n+1$ are $2^a5^b$ and $3^c$. $16 < 3^c < 97$ so $3^c = 27,81$. $81^{82} > 81^{80} = 3^{240}$ does not work. ANd $27 - 1 = 26=2*13$ does not work. And $27+1 = 28=4*7$ does not work.

or $n$ and $n+1$ are $3^b5^c$ and $2^a$. As $16 < 2^a< 97$ then $2^a = 32,64$ and $2^a \pm 1$ are $31,33,63,65$ none of which work.

The answer is $n=15$.

Of course it would be easier with multiple choice.

$\endgroup$
  • $\begingroup$ @fleabood thorough and easy to understand..thanks..but what if I was given 15 as an option, how do I make things quicker and smaller? $\endgroup$ – YourAverageEuler Oct 5 '17 at 4:16
  • 1
    $\begingroup$ If you were given 15 you'd have to check 15^16 = 3^16x5^16 divides 100!. It does because there are more than 16 multiples of 3 and more than 16 multiples of 5 in 1...100. Then you'd have to ceck if 16^15 divides 100!. 16^15=2^60. There are 50 even numbers and 25 miltiples of 4 so 2^75 does divide into 100!. So that worksm $\endgroup$ – fleablood Oct 5 '17 at 5:11
3
$\begingroup$

Suppose I asked you you find x such that $x^2= 5$. You take the derivative of both sides, and get $2x = 0$. Does that look right to you? When you have $100!=K(n+1)^n$, $n$ is a constant unknown quantity, not a variable. Taking the derivative doesn't make sense, as there is no function to take the derivative of.

You need to analyze this with number theory tools, not calculus. For instance, when deciding whether $(n+1)^n$ divides $100!$ when $n =24$, you need to look at the prime factorization of $n+1$: $25=5^2$. So $(n+1)^n= 5^{2*24}= 5^{48}$. There are $20$ numbers $\alpha\leq 100$ that are divisible by $5$, and $1$ number $\alpha\leq 100$ divisible by $25$, so you have $20+1=21$ factors of $5$ in $100!$, which is less than the $48$ that you need. So $n$ can't be $24$. Since it's a multiple choice question, you can just test each option.

$\endgroup$
  • $\begingroup$ exactly what I needed! A verification on the approach $\endgroup$ – YourAverageEuler Oct 4 '17 at 15:26
1
$\begingroup$

If you mean $\log{x}=\ln{x}=\log_ex$ then the reasoning is the same:

$f(x)=\ln{x}\ln(x+1)-1$ is an increasing function for $x>1$.

Since $f(1)<0$ and $f(10)>0$ our equation has an unique root: $2.307...$.

Thus, in natural numbers our equation has no roots.

$\endgroup$
  • $\begingroup$ @YourAverageEuler I added something. See now. $\endgroup$ – Michael Rozenberg Oct 4 '17 at 15:17
  • $\begingroup$ so does it mean that my approach is wrong? $\endgroup$ – YourAverageEuler Oct 4 '17 at 15:18
  • $\begingroup$ i have got $n \approx 2.30722247976713400502$$ $\endgroup$ – Dr. Sonnhard Graubner Oct 4 '17 at 15:22
  • $\begingroup$ Where do we go from here? $\endgroup$ – YourAverageEuler Oct 4 '17 at 15:28
  • 1
    $\begingroup$ @Isham I fixed. Thank you! $\endgroup$ – Michael Rozenberg Oct 4 '17 at 16:18
0
$\begingroup$

$A)$ $\log (x)$ is a strictly increasing function.

$(B)$ $n= 3 \gt e$.

$z(n):=\log(n)\log(n+1)$.

1) $z(n=1) = 0.$

2)$ z(n=3) = \log(3)\log(4) \gt 1$, using $A,B$.

3)$z(n+1) \gt z(n) \gt 1,$ for $n \ge 3$, using A,B.

No positive integer solution for n=1,3,4,5,6....100.

Remains: $n=2$.

$z(n=2) = \log(2)\log(3) \gt 0$.

Cannot rule out $n=2$ as solution of

$z(n=2)=1$, without using more info.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.