3
$\begingroup$

One can find on the forums a lot of exercise where the pupils call for help to solve their maths, once I came across an exercise similar to this one:

Determine with a simple (non-scientific) calculator the integer n such that

$3 ^ {n} <2 ^ {2017} <3 ^ {n + 1}$.

Can you do that ?

The fastest answer with the calculator will be the best.

$\endgroup$
  • $\begingroup$ take ln both side... the rest is piece of cake... $\endgroup$ – Oray Jul 13 '17 at 5:28
  • $\begingroup$ are you sûre you answer to the good question ? $\endgroup$ – Dattier Jul 13 '17 at 5:33
  • $\begingroup$ n should be 1344?? $\endgroup$ – Anurag Jul 13 '17 at 6:26
  • $\begingroup$ Happen to have some log tables handy? $\endgroup$ – micsthepick Jul 13 '17 at 7:30
  • $\begingroup$ @Anurag 8/9 isn't that close to 1 :-). $\endgroup$ – Gareth McCaughan Jul 13 '17 at 22:23
4
$\begingroup$

Some C# how I did it, and it calculated it correctly.

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 0, n = 0, max=2017, moves=0, someVar=0;
            bool a = true;
            double number = 1;
            double[,] calculations = new double[2048,2];//to remember calculations
            for (int i = 1; i < 2048; i++) calculations[i,0] = 0;
            number *= (2.0 * 2.0 / 3.0); n++; x++; x++; moves = 3;
            calculations[x,0] = number; //for move x=2 - remember number
            calculations[x, 1] = n;
            while ((x < max) && a)
            {
                if (number > 3) { number /= 3; n++; moves++; }
                else if (number < 1) { number *= 2; x++; calculations[x,0] = number; calculations[x, 1] = n; moves++; }
                else if (x * 2 > max) { x -= 16; number /= calculations[16,0]; n-=(int)calculations[16, 1]; a = false; calculations[x, 0] = number; calculations[x, 1] = n; moves++; } //only once
                else { number *= number; x *= 2; n *= 2; calculations[x,0] = number; calculations[x, 1] = n; moves++; }
            }
            while (x + 1 < max)
            {
                for (int i = 1; i < 2048; i++) //first i find number i will add
                { if ((i + x) < max) { if (calculations[i, 0] != 0) { someVar = i; } } } //highest possible comparsion
                number*=calculations[someVar, 0];
                n+=(int) calculations[someVar, 1];
                x += someVar;
                moves++;
            }
            if (x == max-1) { x++; number *= 2; moves++; } //correction for x=1
            while (number>3) { number /= 3;n++;moves++; } //to find number between 1 and 3.
            Console.WriteLine("Total moves: " + moves + "  and n=" + n); // 27 moves, n=1272
            Console.ReadKey();
        }
    }
}

How it works:

x is number of 2 powers. It changes value 13 times.
n is number of 3 powers. It changes value 16 times. (once at start)
number is (2^x / 3^n) and I'm trying to keep it between 1 and 3 = no big numbers. Every time it is above 3, I simply add n+1 = number/3 and continue.
Main cycle is: number ^ 2 is equal to n*2 and x*2 or better: number^2=(2^2x/3^2n)
When I reach x=2017, I continue dividing by 3, till I get number between 1 and 3, meaning next divide will be "too much" and 3^n would be greater than 2^x.

$\endgroup$
  • $\begingroup$ you use 3289 steps, there are more faster. $\endgroup$ – Dattier Jul 13 '17 at 5:50
  • $\begingroup$ @Dattier edited for lowest number of steps with my solution. $\endgroup$ – Jan Ivan Jul 13 '17 at 10:01
  • $\begingroup$ Now, how many steps do you use ? @JanIvan $\endgroup$ – Dattier Jul 13 '17 at 10:04
  • $\begingroup$ @Dattier I changed number 18 times that I need to calculate. But if you also count changing x+1 or x*2 (hardest operation with that number is multiply 2) to reach x=2017 and n+1 and when it reaches 1272 - it would be 18+13+16 steps total. $\endgroup$ – Jan Ivan Jul 13 '17 at 10:07
  • $\begingroup$ You use sqare and multiply, that is better but there are more faster. @Jan Ivan $\endgroup$ – Dattier Jul 13 '17 at 10:17
5
$\begingroup$

Managed to calculate that number with simple calculator and it took few minutes.
Here is how to do that.
First, let's breakdown the task to this:

n < log3(2^2017) < n + 1

Which is also equal to this:

n < 2017*log3(2) < n + 1

So to get the answer we simply have to calculate this number:

2017*log3(2)

We can break down that number to this:

2017*(log2/log3)
and use method described here to calculcate log2 and log3
We can do this either by hand or by using calculator, as approximation 10^(-3) is enough (see below)

Calculation should look something like this:

for log(2):
2/10^0 = 2 (0,...)
2^10=1024
1024/10^3=1.024 (0.3...)
1.024^10=1.267
1.267/10^0=1.267 (0.30...)
... (2 more steps) log2 = ~0.301
Calculating numbers with approximation 10^(-3) is enough as 2017 is 4-digit number. And this is possible with simple calculators.
So we stop calculation for log2 as soon as we get 0.301 (301*(10^(-3)))
and do the same for log3

And we'll get:

log2 = 0.301 and log3 = 0.477
2017*0.301/0.477=~1272.78
And as n < 1272.78 < n + 1

The answer will be:

1272

$\endgroup$
  • 2
    $\begingroup$ I haven't used it. I've breakdown it to simpler calculation $\endgroup$ – Just Shadow Jul 13 '17 at 10:37
  • 2
    $\begingroup$ Question was this: "Determine with a simple (non-scientific) calculator the integer n such that 3n<22017<3n+1". Which IMHO means that we have to calculate it using simple-non scirentific calculator which has no logarithm function. And doesn't it prevent us to partially simulate/calculate logarithm function with simpler operations allowed in calculator if it's possible. "The fastest answer with the calculator will be the best." So we have to just calculate that number using simple calculator and find the fastest solution. $\endgroup$ – Just Shadow Jul 13 '17 at 10:50
  • 1
    $\begingroup$ Probably we'd better to edit the question to remove inconsistency between title and the text as in many other answers logarithm is used without calculator. But in case of editing body of the question it may become another question (and changing question is not a good thing in Stackexchange, so probably it would be better to create new question with mentioning that log is not allowed at all even without calculator) $\endgroup$ – Just Shadow Jul 13 '17 at 11:10
  • 1
    $\begingroup$ The title says "without logarithms", but the actual post says "determine with a simple calculator", which doesn't forbid logarithms. If you're going to be that much a stickler for the title and not the post, then fine; I'll just plug the numbers into Wolfram|Alpha (and not use logarithms myself), which isn't against the rules in the title, even though it's against the rules in the post. $\endgroup$ – edderiofer Jul 13 '17 at 13:50
  • 3
    $\begingroup$ What we're trying to calculate is floor (2017 * log2 (3)) , seems to me like the only thing you can do to avoid logarithms is avoiding writing the word "logarithm" in your answer. But in the end you're still calculating a log. $\endgroup$ – ffao Jul 13 '17 at 16:34
4
$\begingroup$

Fun way :

Total : 34 calculations
First, you find the value of the 2 without using exponent because it is not available on a standard calculator.
(exponent values)
2(multiply itself)
4(multiply itself)
8(multiply itself)
16(multiply itself)
32(multiply itself)
64(multiply itself)
128(multiply itself)
256(multiply itself)
512(multiply itself)
1024(multiply itself)
1008(divided by the result gotten for 16)
2016(multiply itself)
2017(double)
13 calculation

Then you find the value for 3 immediately before and after the value of the 2 using a quicksort logic when you go over to find the good value optimally fast.(log base 2 of n) 2(multiply itself)
4(multiply itself)
8(multiply itself)
16(multiply itself)
32(multiply itself)
64(multiply itself)
128(multiply itself)
256(multiply itself)
512(multiply itself)
1024(multiply itself)
2048(multiply itself)
1536(divided by the result gotten for 512)
1280(divided by the result gotten for 256)
1152(multiplied by the result gotten for 128)
1216(multiplied by the result gotten for 64)
1248(multiplied by the result gotten for 32)
1264(multiplied by the result gotten for 16)
1272(multiplied by the result gotten for 8)(value of n)
1276(multiplied by the result gotten for 4)(over n)
1274(multiplied by the result gotten for 2)(over n)
1273(divided by 3)(over n)(confirmed that 1272 was the value of n)
21 calculations

$\endgroup$
  • $\begingroup$ This is seems to me to be just about the only practical way - +1 $\endgroup$ – micsthepick Jul 13 '17 at 7:33
  • 8
    $\begingroup$ This won't work on any cheap calculator, because 2^2017 is FAR too large for that. $\endgroup$ – Zizy Archer Jul 13 '17 at 8:00
  • 2
    $\begingroup$ The calculator has no power operator. $\endgroup$ – ffao Jul 13 '17 at 9:30
  • $\begingroup$ @ffao copy the result and multiply it by itself. $\endgroup$ – Olivier Grégoire Jul 13 '17 at 9:32
  • $\begingroup$ @Olivier doesn't work if you're trying to raise a number to the power of 0.63. $\endgroup$ – ffao Jul 13 '17 at 9:36
3
$\begingroup$

Well, what we need is floor of 2017 * ln(2)/ln(3), which will be 1272. Now the challenge is essentially getting ln(2)/ln(3). For that, we can use integral. ln(2) = integral from 1 to 2 of (1/x dx). ln(3) has upper bound 3.

Now, let's start with simplest integration. We calculate N equidistant points of 1/x and sum them together, dividing by N. For ln(3) we calculate additional N/2 points from 2 to 3 and divide by N/2 - there will be less of a change in values. We could do even better scheme by have finer division of these points as we know how the 1/x goes.

For N=1 we would have ln(2) = 1/1.5, ln(3) = ln(2) + 1/2.5 => ln(3)/ln(2) = 1.6. 2017 / 1.6 = 1260. Not correct, but not that far off, for just the first step. With this, you need N=24 to get the correct answer.

24 inversions (pressings of 1/x button) and 23 additions to get ln2 + 1 division, 12 inversions and 12 additions for ln3 + 1 division. One multiplication and one division for final result. Pretty fast, though not optimal - poor integration scheme. 73 operations in total, give or take a few if I made a mistake somewhere :D

This is NOT the fastest approach, better integration scheme could save some operations and have it converge with smaller N. But this is definitely doable even on a cheap calculator - number will not be too big and inaccuracies shouldn't influence the result all that much. It even isn't that slow everything considered.

But, interestingly, taking N points for ln3 as well makes this much slower, N=43.

$\endgroup$
  • $\begingroup$ you can't use logarithme $\endgroup$ – Dattier Jul 13 '17 at 9:49
  • $\begingroup$ @Dattier Uh I didn't use it on a calculator. I used + * and / there. These were indeed used to calculate logarithm, but all are valid calculator operations. In the third paragraph you see ln(2) approximation of 1/1.5 and ln(3) approximation of 1/1.5 + 1/2.5, giving (wrong) final result of n=1260. With 24 terms for ln(2) and additional 12 for ln(3) you end up with accurate enough logarithm approximations to get the correct final result n=1272. $\endgroup$ – Zizy Archer Jul 13 '17 at 11:14
3
$\begingroup$

Here is an approach that's reasonably effective without needing to use the concept of logarithms, or requiring clever insights that would likely confuse the sort of audience that doesn't understand logs or have a calculator that computes them.

We begin with the familiar observation that 2^3 is just a little smaller than 3^2. Compute 8^k/9^k (by repeated multiplication since we've been told our calculator doesn't know how to compute powers) for smallish k until we find that 2^18/3^12 is about 0.493, just slightly less than 1/2. So 2^19/3^12 ~= 0.986. It's actually nearer 0.9865.

(Remark: this is why there are 12 semitones in an octave: the "circle of fifths", with ideal frequency ratios 3:2, almost closes up after 12 steps.)

Now 2017 is a little more than 106x19. So the next thing we do is to say that 2^2014 / 3^1272 ~= 0.9865^106.

We could compute this last thing without too much pain even on a nasty 4-function calculator by repeated squaring and find that it's somewhere around 0.23. More precisely: First square once: we want 0.9732^53. That's about 3% more than 0.9732^54. 54 is a nice number. Cube, cube, cube, square. (Our calculator probably doesn't have a button for that, but anyone can remember four digits for long enough to do it by multiplying.) That gives us about 3% less than 0.23. It will soon become apparent that neither that 3% nor the other accumulated rounding errors are big enough to matter.

So then we know that 2^2017 / 3^1274 ~= 8/9 x 0.23, so 2^2017 = 3^1274 x 0.2ish, so 2^2017 is comfortably between 3^1272 and 3^1273.

So, how many operations do we need to do on our nasty little 4-function calculator? Well, it depends on how much we can do in our head. Something like this:

  • Enter 8/9 * 8/9 = * 8/9 = ... (counting by hand) until we see something very close to a nice number, which in this case is 1/2. We'll end up with six lots of 8/9, so 28 keystrokes.
  • Enter * 2 = to get our estimate of 2^19/3^12. 31 keystrokes so far. Remember the number 0.9865 mentally.
  • Divide 2017 by 19 to get 106-and-a-bit: 8 keystrokes. 39 keystrokes so far.
  • Now let's figure out 0.9865^106 using the procedure above. I'll assume we don't have a "square" or "cube" button; I'll work to four figures, or 3 when the error is obviously going to be small; and I'll assume I have enough brain to be able to square e.g. 9865 instead of 0.9865 and figure out what the result means. So I do 9865 * 9865 = (10 keystrokes); then 973 * 973 * 973 = (12 keystrokes); then 921 * 921 * 921 = (12 keystrokes); then 781 * 781 * 781 = (12 keystrokes); then 476 * 476 = (8 keystrokes). That's 54 keystrokes, so 93 keystrokes so far.
  • Now what we know is that 2^2017 = 3^1274 * 0.22ish * 8/9. We can see without needing any actual calculation that 0.22 * 8/9 is bigger than 1/9 but smaller than 1/3, and that there's way more slack in there than could be eroded by rounding errors, so we know the answer we need is 1272.

Some 4-function calculators behave in ways that would substantially reduce the number of keystrokes needed. For instance, on some I think entering *== computes the cube of a number. For these we could do the work of those last 54 keystrokes faster and more accurately by typing .9865*=*==*==*==*= for 18 keystrokes, saving 36 keystrokes. Similarly, the first step would take not 28 keystrokes but 9 keystrokes. I assume we are still too stupid to work out 2017/19 mentally, though, so we still need that calculation and it still means that we no longer have .9865... available without rekeying it. Still, this ends up taking 9+3+8+18=38 keystrokes instead of 93.

OP is keen to know how many times I have to press "=" with this approach. The number appears to be 5 when finding that 2^18/3^12 is a good waypoint, plus 1 when doubling, plus 1 when finding out how many 19s go into 2017, plus 5 when taking a 108th (~= 106th) power. Total is 12. I'm not entirely convinced that the number of "="s is a great metric; for instance, I could reduce that last 5 to 1 by doing a whole lot more multiplication operations, but that would not in any useful sense be an improvement.

OP also wishes to know how many operator keys I have to press. I'm not sure whether he wants the = key counted there; I will include it. Then there are 10+2+2+13=27 operator key presses, if I have done my arithmetic correctly.

$\endgroup$
  • $\begingroup$ How many step, are you using ? @GarethMcCaughan $\endgroup$ – Dattier Jul 13 '17 at 15:49
  • $\begingroup$ Depends on what you count as a step, exactly how the calculator behaves, and how much we can do in our heads. See the last paragraph I've added to my answer. (Once I've edited it to stop multiplication signs being interpreted as formatting.) $\endgroup$ – Gareth McCaughan Jul 13 '17 at 16:38
  • $\begingroup$ The number of steps is the number of times you press the operator key (=,+,*,/) of the calculator @Gareth $\endgroup$ – Dattier Jul 13 '17 at 18:48
  • $\begingroup$ operator keys is a better metric, and how many operator keys have you, @Gareth ? $\endgroup$ – Dattier Jul 13 '17 at 18:58
  • $\begingroup$ I have to say I'm getting rather bored of counting one metric after another. $\endgroup$ – Gareth McCaughan Jul 13 '17 at 19:05
3
$\begingroup$

It isn't terribly clear how clever we are allowed to be. Here is what I would actually do, on a good day, if handed a 4-function calculator and told to answer this question.

  1. Hmm, I know that 3^12 is close to a power of 2 because of the circle of fifths in music. I forget what power of 2, but let's see. 3^6=729 so I need to square that; it'll be about 50 x 10000 so half a million, so 2^19.

  2. How many 19s go into 2017? Obviously 100 + 117/19. 105? No, that would be 95 which is too small, so 106. Remainder is 22-19=3.

  3. So 2^2017 = (2^19)^106 times 8, and is about (3^12)^106 times 8. 12x106 = 1200+72 = 1272.

(I have not turned the calculator on yet.)

  1. OK, now I need to estimate the remaining factor and I'm too lazy to calculate 3^12 exactly. Calculator: 524288/729/729= [Calculator says 0.9865...]

  2. I need the 106th power of that. If it were 0.99 this would be about 1/e; as it is it's about 1/e^1.5. So I need 3^1272 times 8 times 1/e^1.5. Since e is pretty close to 3, that last factor will turn the 8 into something smaller than 3 but bigger than 1. So the answer we need is 1272.

So the calculator was needed only for doing a couple of divisions.

My guess is that this is not permitted, even though I never said the word "logarithm" or asked the calculator to do anything fancy. So what is permitted? I used three superpowers above: first, I can do easy mental arithmetic (is that allowed, or do we have to use the calculator for it?); second, I know some facts about how large powers of things near 1 behave (is that allowed, or do I have to use the calculator to find that out?); third, I know some trivia that helped guide me to a good way of organizing the calculation (is that allowed, or do I have to assume that I have no idea what to do and need to find everything out using the calculator?).

Those last two questions are critical here. Because there are probably a bunch of efficient ways of doing this calculation that no one would think of if they didn't already know a lot about the answer. The answers already posted are mostly "straightforward" ones, in that you could do more or less the same thing given different values for the magic numbers 2, 3, and 2017. Are we looking for this sort of "straightforward" answer, or for something ingenious that involves a highly nontrivial property of the particular question we're addressing?

And, if the latter, why is that allowed if my two-arithmetic-ops solution above isn't?

$\endgroup$
  • $\begingroup$ The better method is that can use for another numbers than 2, 3, and 2017. $\endgroup$ – Dattier Jul 13 '17 at 22:32
2
$\begingroup$

If you happen to already know a good approximation of log base 2 of 3: (1.585):

2017 divide by 1.585 gives 1272.6... so n = 1272

because:

log2(3^n) < log2(2017)   < log2(3^(n+1)
n*log2(3) <    2017      < (n+1)*log2(3)
    n     < 2017/log2(3) <     n+1
$\endgroup$
  • 2
    $\begingroup$ And if you happen to already know 2^2017 and all powers of 3, you don't have to calculate anything :) $\endgroup$ – Jan Ivan Jul 13 '17 at 7:42
  • $\begingroup$ It seems reasonable to me for at least someone to know what log2(3) is from memory $\endgroup$ – micsthepick Jul 13 '17 at 7:45
  • 1
    $\begingroup$ Well I remember 2^20 and 35 digits of PI, but never encountered this $\endgroup$ – Jan Ivan Jul 13 '17 at 7:51
  • $\begingroup$ you can't use logarithme $\endgroup$ – Dattier Jul 13 '17 at 10:27
  • $\begingroup$ @Dattier this answer is dependant upon the memorisation of log2(3), It is not found as a calculation (seeing as there is no logarithm function on the calculator) $\endgroup$ – micsthepick Jul 13 '17 at 22:54
2
$\begingroup$

As every recreational math nerd knows, $3^{53}$ is virtually indistinguishable from $2^{84}$. So we calculate 2017 times 53 divided by 84 which gives us 1272.585 in three keystrokes. We conclude that $n = 1272$.

$\endgroup$
  • $\begingroup$ "but it's not clear to me what's permissible and what isn't." It's true, so all the solution are good, (I give a up) but I will choose the one, I think, it answer to the question that I have posed. $\endgroup$ – Dattier Jul 14 '17 at 10:56

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.