Help - mathematicians work it out in logs

New Topic
This topic has been archived, and won't accept reply postings.
Andy Gamisou 22 Mar 2021

My brain seems to have turned to mush these days, so I'm struggling how to work out how to approach the problem below other than by trial and error or writing a simple program (which is what I did in the end):

How to find the smallest integer n such that:

n > log(n)*C

where the log is to base 2, and C is a constant.

I'm thinking there must be some mathematical approach to solving this (and have something on the tip of my brain), but buggered if I can find it (my google skills are clearly pants too).

TIA

 john arran 22 Mar 2021
In reply to Andy Gamisou:

The opposite of a logarithm is an exponential.

See https://www.purplemath.com/modules/logs.htm for a clear explanation and for how to easily rewrite your equation. 

 Robert Durran 22 Mar 2021
In reply to Andy Gamisou:

I don't think it can be solved analytically. You will need to stick with a numerical method.

1
In reply to Andy Gamisou:

I promise you the quickest way to solve this is just to try all the integers, starting from 1

 Robert Durran 22 Mar 2021
In reply to Robert Durran:

If my disliker knows an analytical method, I would love to see it!

1
 Robert Durran 22 Mar 2021
In reply to Robert Durran:

Oh well, maybe the dislikes are just expressing disappointment at the lack of an analytical method. Any enlightenment?

Andy Gamisou 22 Mar 2021
In reply to john arran:

> The opposite of a logarithm is an exponential.

> See https://www.purplemath.com/modules/logs.htm for a clear explanation and for how to easily rewrite your equation. 

I know what a logarithm (and exponential) is!   Rewriting it as an exponent is the first thing I thought of, but I don't think it solves the problem.  Happy to be proved wrong if you can demonstrate!

Andy Gamisou 22 Mar 2021
In reply to Robert Durran:

> I don't think it can be solved analytically. You will need to stick with a numerical method.


Ah - I did wonder, but assumed I was just being stupid.  I gave you a like to balance the (strange) dislikes.

Post edited at 07:42
 Robert Durran 22 Mar 2021
In reply to Andy Gamisou:

> I know what a logarithm (and exponential) is!   Rewriting it as an exponent is the first thing I thought of, but I don't think it solves the problem.

There seems no advantage on wring it as n<10^(n/C)

Probably best write it as n/log n>C and use simple trial and improvement.

 john arran 22 Mar 2021
In reply to Andy Gamisou:

In which case I stand corrected. I don't have time to look at it in detail as I'm busy, but at first glance it looked straightforward. Sorry.

 Maggot 22 Mar 2021
In reply to john arran:

a^n + b^n = c^n looks easy at first!

 Jamie Wakeham 22 Mar 2021
In reply to Maggot:

I regret that this text box is too small to contain my proof.

 wintertree 22 Mar 2021
In reply to Andy Gamisou:

There's a mathematical approach which is to use something like Newton's methods to solve the equality and then round in the appropriate direction.

There's not an analytical method I can think of.  You might exponent both sides and apply Taylor series expansions for some mirth however.  

Post edited at 08:53
 tlouth7 22 Mar 2021
In reply to Robert Durran:

Minor correction, this is a base 2 log.

I would write it out as an equation and solve, then pick one of the adjacent integers and check whether that satisfied the inequality. But then I am hopeless at keeping the sign the right way round when rearranging inequalities.

 Philip 22 Mar 2021
In reply to Andy Gamisou:

You need the Lamber W function.

https://en.wikipedia.org/wiki/Lambert_W_function#Applications

If you solve this precisely you can round to the next integer. Assuming you know C, then switch to natural logs by replacing C with "C / ln(2)",  invert (ln(2)/C) and raise that to exponential and call it K

K = 2 - e^C

n^1/n = K

Solve for n.

Edit : Use Wolfram Alpha to do the last step:

https://www.wolframalpha.com/input/?i=solve+n%5E%281%2Fn%29%3D1.1

Post edited at 12:27
 James Malloch 22 Mar 2021
In reply to Andy Gamisou:

I did a maths degree but I feel like I’ve forgotten about most of it now! I know this doesn’t work, but if anyone could explain why then it would save me banging my head against the wall...

I guess you’re essentially looking for where y=C*log(x) crosses the y=x line, then taking the next integer.

What don’t simultaneous equations work for this?

Edit - I guess the post above, by Phillip, explains this due to there being something to solve both in and outside a log, or in a multiplier and exponent. 

Post edited at 14:32
 Robert Durran 22 Mar 2021
In reply to James Malloch:

> I guess you’re essentially looking for where y=C*log(x) crosses the y=x line, then taking the next integer.

> What don’t simultaneous equations work for this?

Because she you try to solve them you just get back to the original equation!

 Robert Durran 22 Mar 2021
In reply to Philip:

This has got me wondering what counts as an analytic solution. This Lamber W function effectively just tabulates solutions (presumably arrived at numerically) to a set of equations with a varying constant in them and which a class of equations can be transformed to. So can sinx=0.3 or x^2=2 be solved analytically when you are really just using a calculator to access numerically arrived at approximate solutions. Which approximately tabulated functions are allowed (if any)?

 wintertree 22 Mar 2021
In reply to Robert Durran:

I was considering a similar post.  I'm not convinced the Lambert W is any more analytic than applying a few rounds of Newton's method or some similar which, given enough pen and ink, could be used to produce a similarly horrific looking formulaic answer.  Calling it a "function" is a bit of an affront IMO.

 Philip 22 Mar 2021
In reply to Robert Durran:

I'm just a humble scientist using numbers, but aren't many of our functions just sums of infinite series that we either approximate or calculate to arbitrary precision.

It seems fine that we give trigonometric functions names and named inverse functions and derivatives, but in the case of logarithms we get a one sided situation where the function is algebraically simple and the inverse not.

 Richard J 22 Mar 2021
In reply to Robert Durran:

Pretty much my last mathematical memory from my degree, before our friends in DAMTP finally killed any self-confidence I had in my mathematical ability, was of the "confluent hypergeometric function", which contains as special cases pretty much every function one's ever heard of, and many that one hasn't - sins & cos's, erfs, Bessel functions, Airy functions, Chebyshev polynomials, Legendre polynomials, etc, etc.  It can be bent into being a solution for pretty much any differential equation in physics, and somewhere there is a vast book tabulating it for all known combinations of parameters.  Or nowadays you can call it from Mathematica or Python.  But then I was rescued by the friendly people in the Cavendish, with their refreshing view that 95% of the work is done by the time you've put your equation into dimensionless variables, and in any case the value of any remaining definite integrals is almost certainly pi.  

 Chubbs 22 Mar 2021
In reply to Andy Gamisou:

Ignore the naysayers. It can be solved using calculus.

set f(x):=x-C.log(x)

=x-C.ln(x)/ln(2)

Change to base ‘e’ so we can do calculus.

f’(x):=1-C/x.ln(2)

set this=0, as it’s a turning point.

This is easy to solve. So our solution for n is the least n such that n>this x.

 Robert Durran 22 Mar 2021
In reply to Chubbs:

But we're not trying so solve f'(x)=0. We are trying to solve f(x)=0.

 Chubbs 22 Mar 2021
In reply to Robert Durran:

You’re quite right. I probably shouldn’t have joined in so late in the evening. I might have to retract my previous statement and give it some more though. 

 Philip 22 Mar 2021
In reply to Chubbs:

> You’re quite right. I probably shouldn’t have joined in so late in the evening. I might have to retract my previous statement and give it some more though. 

Another 10 years perhaps?

 Chubbs 22 Mar 2021
In reply to Philip:

Not that much more 

 Philip 22 Mar 2021
In reply to Chubbs:

I was joking, according to UKC you've been here 10 years and 3 out of 7 posts are on this thread.

 Chubbs 22 Mar 2021
In reply to Philip:

What can I say. I like Maths

Andy Gamisou 23 Mar 2021
In reply to Various:

Hey - thanks for the responses.  More than I expected.  I'll look into the Newton method (which a quick google suggests it might have been the thing on the tip of my brain) and into doing the Lambeth walk (was that the other thing?) - more than as a matter of interest than with any expectation.

It's around 35 years since I had to think about things in such a way, so if I don't reappear on UKC it's probably because I'm lying on the floor with an exploded bonce.

Post edited at 06:03
 DixyM 23 Mar 2021
In reply to Andy Gamisou:

The problem is that you're trying to solve e^x=x or equivalently x=log(x) essentially. Funnily enough i ran into this problem whilst teaching yesterday. 

Anyway, this might help, https://math.stackexchange.com/questions/909301/how-to-solve-ex-x .

 AdJS 23 Mar 2021
In reply to James Malloch:

> I guess you’re essentially looking for where y=C*log(x) crosses the y=x line, then taking the next integer.

For y=C*logx and y=x solutions depend on the value of C and the base of the log.

For C=1 there is no solution, i.e the lines do not cross.

For log to the base 2 and C=2, the solutions are x=2 and x=4.

Not sure if this is helpful in solving the original problem. My maths isn’t good enough to actually understand it!

Andy Gamisou 24 Mar 2021
In reply to john arran:

> The opposite of a logarithm is an exponential.

> See https://www.purplemath.com/modules/logs.htm for a clear explanation and for how to easily rewrite your equation. 

Thanks for the website link though - looks nice.  Think I'll be visiting it a fair bit over the coming months

In reply to Andy Gamisou:

2?

In reply to Andy Gamisou:

Presumably C is also meant to be a positive integer, otherwise the question is pretty meaningless, is it not? Then surely the answer is n = 0, or it's too late at night!

Post edited at 00:46
 jk25002 25 Mar 2021
In reply to Andy Gamisou:

Does this work?

Express your inequality as

(1) 2^n > n^c

We're looking for the smallest integer n satisfying (1) so we can also write

(2) 2^(n-1) < (n-1)^c

Multiply (2) by 2 and get

(3) 2^n < 2(n-1)^c

Combine the inequalities (1) and (3) to get

(4) 2(n-1)^c - n^c > 0

So you need to find the smallest integer n for which (4) holds. (4) is just polynomial, so it's much simpler to solve.

Jack

 Robert Durran 25 Mar 2021
In reply to jk25002:

Unfortunately, although (1) and (3) together imply (4), (4) does not imply both (1) and (3). This is easily seen with a simple example: 2<8 does not imply that 2<10 and 10<8

 jk25002 25 Mar 2021
In reply to Robert Durran:

damn...

In reply to AdJS:

> For y=C*logx and y=x solutions depend on the value of C and the base of the log.

> For C=1 there is no solution, i.e the lines do not cross.

> For log to the base 2 and C=2, the solutions are x=2 and x=4.

> Not sure if this is helpful in solving the original problem. My maths isn’t good enough to actually understand it!

Surely, we are permitted to put C = 1, in which case the inequality becomes n > log(n) or 2^n > n, for which the smallest integer that works is n = 0, i.e., 2^0 (=1) > 0

 Philip 25 Mar 2021
In reply to John Stainforth:

> Surely, we are permitted to put C = 1, in which case the inequality becomes n > log(n) or 2^n > n, for which the smallest integer that works is n = 0, i.e., 2^0 (=1) > 0

You think log_2(0) is zero? It isn't.

I'm surprised this thread is still going.

As Long Suffering Rope Holder pointed out at the start, the most trivial answer is n=1 and 1 > log(1)*C for all C. And that is the answer to the original question about the smallest integer for which that is true.

What then follows is actually a discussion about finding the second integer, so in fact the second smallest n. The way to solve this is in my post above.

Take the situation of C = 3. Remember it's log base 2.

n=1: 1 > 0 * 3
n=2: 2< 1* 3
n=4 4 < 2 * 3
n=8 8 < 3 * 3
n=16 16 >4 * 3

So the smallest is, and always will be n = 1, then for C = 3 the smallest lies between 8 and 16. It is in fact n=10.

So n > log_2(n)*C for n=1,>9 C=3

In reply to Philip:

You're right! I know full well that log_baseanything(0) isn't defined. That's why I translated it into 2^(n/C) > n, which was a mistake. I should have just left it as n > log_2(n) * C and substituted some values, like you did.


New Topic
This topic has been archived, and won't accept reply postings.
Loading Notifications...