Divide by 3 (equivalent to taking cube root). That's 1.43
Recall that log e is 0.43. So 1.43 is log (e * 10). Hopefully you remember e = 2.71, so the number you're looking for is 27.1. If you remember that you rounded up to start, you can round back down and guess that it's more like 27.0.
You can simplify this a little further by dividing out thousands and multiplying by 10s at the end, so you only need to find the cube root of 20 using the same process.
I did it similarly: log(19,683) is about 4.3, so ln(19,683) is about 4.3 * 2.3, which is about 9.9. That jumps out as close to 9ln(3).
So the natural log of the cube root is (presumably) 3 ln(3), making the cube root itself 27.
Alternatively, the digit sum of 19,683 is 27, so the cube is a multiple of 9. Given that it's a perfect cube, 19,683 must be a multiple of 3^3 = 27. Dividing by that gives 729, or 9^3, so the cube root is 3 * 9=27.
Lastly, it's possible to dredge up that e^3 is about 20, so (27.1828...)^3 is about 20,000, and it's plausible that 27 is the cube root we're after.
Yes! Knowing some basic logs is really handy for lots of quick calculations involving larger numbers, not just this one. Highly recommend. My first thought for how to handle this one was to use logs, which would work even if the original number isn't a perfect cube. Then, since it is, you can use the last-digit trick to zero in from that first approximate answer.
I was surprised by the chart showing that there is a bijection between last digit of a number and last digit of the number's cube.
In base 10, this works for every odd power but for no even power. (if you're given that a square ends in anything but 0 or 5, there are always two different possibilities for the last digit of the square root)
Here are the powers (less than 100) for which this works in different bases (up to 25). Now I'm quite confused: what is the pattern here and what is the number-theoretic explanation for it?
(Edit: It looks like the bases for which no power, except the trivial case of 1, has this property are exactly those bases that are divisible by a perfect square -- but I wouldn't have expected that and still don't know how to account for it.)
> what is the pattern here and what is the number-theoretic explanation for it?
We're working with numbers modulo 10, i.e. Z/10Z = {0,1,2,3,4,5,6,7,9}.
Its multiplicative subgroup consists of all the elements with a multiplicative inverse, which are {1,3,7,9}. Note that 1*1 = 1, 3*7 = 21 = 1 (mod 10), and 9*9 = 81 = 1 (mod 10). Its size is phi(10) = phi(2*5) = phi(2) * phi(5) = 1 * 4 = 4.
When computing powers, the exponent can be reduced modulo the size of the multiplicative subgroup: n^e mod m = n ^ {e mod phi(m) } mod m.
In this case of m=10, powers that are 1 or 3 mod 4 are bijections, others are not.
That's a solid explanation, but it's not quite complete -- consider Z/3Z = {0, 1, 2}, all of whom have multiplicative inverses.
An easy way to look at this is that the numbers are equivalent to {0, 1, -1} mod 3, and so the powers are {0^n, 1^n, and (-1)^n}, which is only a bijection for odd n (otherwise, 1^n = (-1)^n). Indeed, you can generalize this to the statement that even powers cannot be bijections for any base N > 2, as 1 != -1 mod N.
I believe you'll find that the powers that are bijections are those relatively prime with phi(N) (as a consequence of the Chinese remainder theorem [0]), outside of the special case GP asked about:
With (nontrivial) perfect square factors, there are nontrivial roots for n^2 = 0 mod N (namely: solutions other than 0 mod N).
For instance, in octal, consider 4 * 4 = 16 (0o20 which ends in zero). Any greater powers of 4 in octal will also end in zero.
[0] This is in fact critical to the decryptability of RSA, which requires that m^(e*d) = m mod N, or equivalently that for a given e, m^e is invertible for all choices of m, i.e. f(m) = m^e mod N is a bijection: https://crypto.stackexchange.com/questions/12255
Accurate. I'm not sure why I wrote they all have inverses, or the point I was trying to make -- phi(3) = 2, so your provided equation already demonstrates that for all even e, n^e = n^0 = 1 mod m (which is obviously not a bijection for n > 2).
It may have worked better with phi(7) = 6: it's not immediately obvious that f(n) = n^3 mod 7 is not a bijection for n in Z/7Z, but easy to demonstrate nonetheless: 2^3 = 1 mod 7 = 1^3.
(That said, I think you hinted at the requirement of coprimality with phi when you pointed to "1 or 3 mod 4" instead of just saying "odd numbers" for 10.)
I think my follow-on point re: bases with non-square powers mapping multiple elements to zero is still correct and not covered by your explanation, though.
Your method is good, but in my view overthinks it - I just looked at it, and let what seemed like the right solution just pop into my head - and it was. It felt like 27 would be the answer. I know that seems woolly as all hell, but that’s the nature of running stuff at a level that can’t be consciously interacted with or directly queried. A quick conscious mental multiplication verified it.
Intuition is incredibly underrated - I have learned to trust the first damned fool thing that pops into my head, before any conscious thought has had time to get moving and therefore interfere. It’s usually correct, regardless of context - and when it goes wrong, it’s because I accidentally allowed myself to think and reason.
It’s in the same category as “walking away from a problem”, in my view - you can’t solve it, you go grab a coffee, and while you’re looking for the sugar the answer is just suddenly there in your head, because you stopped running the CPU-intensive conscious process, and let the background workers catch up.
Conscious thought is great for producing outputs for other humans to then work with. Unconscious through this great for… everything else. We do incredibly complex things all the time - catching a ball, walking upright, looking in the direction of that sudden sound - but typically run all of the gnarly logic in an abstraction layer within a virtual machine, rather than on the hardware that was designed to run it natively.
No end of trouble at school where I wouldn’t just not show my working, but couldn’t - but the real world fortunately doesn’t particularly care about the means, just the ends.
Not particularly since school, no - but I do have a lot of experience with quieting my conscious mind and extracting answers from the silent mass. Maths, facts, connections and correspondences, engineering, debugging, directions, the time, you name it - there’s a whole suite of stuff in there that you just have to learn how to interact with, and nobody is taught. When it’s something important, it can be verified with good old fashioned cogitation.
One of my favourite tricks is just knowing, to +- 1 minute, what time it is. I don’t set an alarm, I just plan to wake at whatever time. If someone asks the time I give it without checking. It actually works better when I’m asleep, as I will wake +- 10 seconds from the intended time, which shows just how much consciousness interferes.
Honestly, it’s laziness - thinking takes far too much effort and is much too slow, and 80% right in 1% of the execution time is a “good enough” optimisation.
One correction: there are many numbers that end in 3 but are not multiples of 3. It is the fact that its digit sum is divisible by 3 that lets us conclude this number itself is so. Perhaps that is what you meant?
Yes, as stated: it ends in 3, so the cube root must be a multiple of 3.
The "cube root" part contains the implicit information that we have a product ending in 3, of three identical factors.
I guess the missing assumption is that given the context of solving the cube root in ones head, it would more likely be a trick that only works with integers, and as such the correct answer might be expected to be one.
37*3 also ends in 3 but is not divisible by 3. Thus, were the range not capped at 30 it may have been illegitimately discarded by the criteria.
I think the 3 combined with the 5 digits and 20-30 range, made my guess a bit lucky. It's also contrived for that cube, so not useful for others, other than perhaps as a direction to go in (and likely arrive at the article).
Right. The correct argument is that 19683 is a *multiple* of 3, because its digit sum 27 is a multiple of 3. So if it's a perfect cube, then the cube root must be a multiple of 3.
https://news.ycombinator.com/item?id=34652053
Also, if it's a perfect cube, since it ends in 3, the cube root must end in 7 (cubing integers is 1:1 on the units digit, and 7->3). So it must be 27, 57, 87, ...
Since it's too small for the cube root to be 57, 27 is the answer.
Don't mix up programming with math. They use a different approach altogether, to solve any word problem through a program chances are you'll use variables and convert it into a linear/quadratic/cubic system of equations, when in Mathematics you can solve it in an easier manner.
I solved it deductively pretty much the way you did, but I wouldn't have approached it that way at all if I couldn't assume that the cube root of 19,683 would be a whole number.
If we've guessed that the number will be in the mid to high 20s, then 27 is the only number one could logically arrive at. 24, 25, 26, and 28 are easy to eliminate because 19,863 is neither an even number nor a multiple of 5. That's all there is to it.
Another approach is to recognize that if you know a number is a perfect cube, and you can recognize any prime factors it contains, you can pull out the cube of those from the number.
Like, by inspection (sum of digits) this number has 3 as a factor. That means 3 has to also be a prime factor of its cube root which means 27 has to be a factor of the cube.
So we can divide out 27, leaving us with the smaller problem of finding 3(cbrt(729)), which you might recognize as being 3*9, or spot that you can repeat the trick to give you 9(cbrt(27))…
Or you might notice that if 19683 has to contain 27 as a factor, that doesn’t leave a lot of room for any other cubed prime factors to exist in the number, and do a trial multiplication to confirm that 27 just is the cube root.
Basically comes down to, if you have a comfortable relationship with how numbers relate to their factors, you can develop a number of instincts for how to recognize shapes within them.
First, note that, since the digit sum of 19683 is a multiple of 9, 19683 itself is a multiple of 9. Second, since 19683 is odd, its cube root will be odd as well. Therefore, the cube root of 19683 will be an odd multiple of 3.
To find 19683¹ᐟ³, will take the base 10 log of 19683, divide by 3, and raise the result to the 10th power, approximating where convenient.
To this end, it will be helpful to have approximate values for lg 2 and lg 5. Since 10³ ≈ 1024 = 2¹⁰ = 10^(lg[2]·10), we have 3 ≈ lg[2]·10. Solving, we find that lg 2 ≈ 0.3. Next, since 10 = 2·5, we have lg[10] = 1 = lg[2·5] = lg 2 + lg 5, so lg 5 = 1 − lg 2 ≈ 0.7.
Since 25 = 5·5, we have lg 25 = lg 5 + lg 5 ≈ 1.4. This means we're looking for an odd multiple of 3 near 25. The closest number that fits the bill is 27. Cubing, we find that 27·27·27 = 19683, so we are done.
Slightly related musing: I can quickly approximate 1/3 of any number. I suspect this is because that's an operation I've had to use often.
If I had needed cube roots equally often, would I have been just as good at mentally intuition roughly what number it has to be?
Or are humans somehow wired to deal with linearities more intuitively than powers? Or is it our mathematical notation (Arabic numbers are linear, as opposed to some log scale) that creates that impression?
There's some research indicating the opposite, that people intuitively think in logarithms. We perceive sound, light, and possibly even the passage of time logarithmicly[1]
I don't think there has been an explanation proposed for why it's easier to do linear math in our heads, I have to imagine this is just the effect of school.
Loads of chat about remembering logs etc, I was expecting to see more number theory here as it’s a really lovely and applicable part of maths.
(As far as doing the calc, I thought it has to end in 7 becaus3 it’s the only one with a cub3 residue of 3 mod 10, which is what they say in post. Then 20 and 30 cubed are 8000 and 27000 respectively and assuming we’re restricting to Z 27 is the only possible answer)
I think it only works if you know its a perfect cube from the get go. Which is useless for me in my day to day unless Im talking to my number theory brother in law.
But he only likes to talk about acting and scrabble.
As you can see, for decimal system, last digit of cubes is unique for all digits. As last digit of cube depends on last digit of cube root only (same for squares and so on), it is bound to be true for all numbers
The question is in which case(s) `f(x) = x^n mod m` is a bijection for `0 <= x < m`.
My intuition is to guess that `gcd(n,m) = 1` is at least a sufficient condition (correct math term? In german it's "hinreichende Bedingung"). Maybe it's the sole necessary condition. But I did only think about this for 5 to 10s and did not spend too much time on looking for a counter example, let alone a proof strategy (my number theory is a bit rusty -- ah, but on second thought, if the theory is correct, then I bet the Chinese remainder theorem is involved).
For those of us who have tried but failed to memorize our logs (obviously the best method to ballpark it) :
For the n-the square root just group the digits by n starting from the ones. That will tell you how many digits you're dealing with. Simplish math will give you the first digit off of the last grouping (simple since you only have to ^n the numbers from 1-10)
Simple counting and a bit of math and I have the order of mag and first digit.
2_
At this point I can either think of a decent trick to iterate the second digit (quick Taylor? [1]), or just guesstimate a linear fit and call it a 5.
25 is within 10%.
[1] instead of Taylor I would do Pascal's triangle on the cube with the next term to calculate (30-x)^3 (I use 30 - x and not 20+x since I want x as small as possible and I know the answer is closer to 30 than 20.
Pascal's triangle:
1(30)^3 + 3(30)^2x + 330x^2 + 1x^3
Drop the higher two terms.
3^3 + 33^2x = 19
19-27 = 27x
X = 8/27 = 1/3 (- 1/27)
30-3.3 = 26.66
I use the sign of the next term of pascal's triangle to see if Ive under or over estimated
33*(-0.3)^2 -> positive
So my x is too large
So my answer is an underestimate.
(Cube root of 19000) greater than but close to 26.6
I know this more of a party trick than a practical skill, but I found it's tricks like this that gets students I tutor a little more interested in math. Knowing these tricks doesn't make you better at math, but understanding the underlying principle of focusing on significant/meaningful digits absolutely will.
If accuracy is important, students would be allowed to use a calculator. There is no longer practical value of being able to do this without one. So there's no point in testing it in school. Any teacher asking this kind of arithmetic question is wasting the time and energy of their students. I have never come across it in my last 10 years of tutoring high school or college math.
If the abstract understanding of root properties is being asked, the question will be presented using variables. The cube root function is effectively equivalent to the square root function execpt the range includes negative values, when looking at it graphically.
Are we talking about the practical value of actively learning math, or the practical value for an average high school student who barely tolerates math? Sure, yes, maybe most people can’t be bothered in practice, but isn’t there a lot of practical value in learning number theoretic ideas and seeing relationships between digits, for example, for the person bound for a job or graduate degree in a STEM field? Seems practical for people interested in math history as well, no?
I’m a fan of some of the math problems on Project Euler. This isn’t high school math, of course, but many problems are carefully designed such that blindly using a computer to solve them just doesn’t work. This forces you to think about the problem more deeply and use that to come up with tricks that reduce the search space. This is very much along the same lines as this blog post, but generalized to bigger harder problems.
And FWIW, stuff like this - a deep interest in math and how there are often many different ways to solve a problem, and the study of digits and numbers and polynomials and roots and efficient ways to manipulate them - is quite core to my job and all the people I work with. I do mostly software at a company that makes hardware and software, and number-theoretic thinking and fun & “impractical” tricks put into practice are literally everywhere.
I guess I’m saying I think that there actually is a lot of practical value in this kind of play, for the engaged audience, and once someone goes beyond basic high school & college math, in addition to the benefits of increased motivation that you mentioned. I wouldn’t be so quick to write it off as pointless, and only teach to the test. Maybe if we had more of this in high school, we’d have a better math education system. I’d agree we need to teach all kids how to use calculators, but I also think we need to teach kids how to think deeply about numbers, and have the skills to build tricks and do mental estimation, and send more of them into science and tech jobs with exploration skills emphasized and prioritized over calculator skills.
We actually believe in a lot of the same things. I was speaking much more specifically to the case of learning the cubic function. The method posted here doesn't generalize to all cubes, only perfect cubes, which is not an assumption you can infer from looking at a number. On a similar thread about an article applying heron's formula to squares, I was arguing for the opposite of what I am arguing here.
I tutor so I get a lot more freedom compared to typical teachers. Instead of cubes, I think time is better spent teaching students logarithms. I personally love teaching how to estimate log_2 values and helping build an intuition about mapping non-linear relationships. Log_2 and logarithms in general allows tracing math from the the first origins of compution ( and how "back in the day" they used log tables for everything) to modern technology storing data in binary form. On my high school's PUMaC A team, I found properties of logarithms way more useful than roots.
I completely agree that teaching number sense is critical but I think excel/spreadsheets and Fermi questions is more useful approach at a high school level. The math education system is broken because using a calculator is still seen as "cheating", and so excel is very rarely a part of the math curriculum. In my opinion, the average student who doesn't puruse a hard math or related field will appreciate the value of math more with an intuition built on logarithms. And those who do pursue math will have an easier time with number theory after having learned how to abstract from the decimal system to numeral systems in general. Fermi questions force students to think deeply about numbers without needing to understand high level math concepts.
I value your perspective, and I have shown project euler to certain high school students in the past. My high school has a very strong CS department, they have been running a 12 hour hackathon since 2017, that also MLH sanctioned/affiliated [1]. We ultimately care about achieving the same goal. I am very intrested to know some keywords I can look up related to your work, how you use roots and polynomials, and how/when you use cubes specifically.
> I am very interested to know some keywords I can look up related to your work, how you use roots and polynomials, and how/when you use cubes specifically.
Sure, happy to geek out a little. (FWIW, I’m not suggesting that this specific cube root trick is super useful, but I think this trick is generalizable in an abstract way, and representative of a lot of different techniques including any exponent, and also has elements that you can use for multiplication and division).
I work in computer graphics, ray tracing specifically, currently using GPUs, and perfect cubes come often up in volume rendering, for example. One little expression that’s reminiscent of this cube root article is how to calculate the number of total nodes in an octree (A cube subdivided into 8 children, and each child subdivided into 8, and so on.) Counting the first cube, and the next 8, then 64, down to N subdivisions, the total has some interesting variations. In binary, it’s a 1 every third digit (the article mentioned how the cube root trick is repeatable every 3 digits). The formula for number of octree nodes is ((2^N)^3 - 1)/7. The 7 in there can be unintuitive at fist, and I think it’s really instructive to see what the divide by 7 does in binary.
Another couple of applications of cube roots I’ve used recently are solving for the distance between a point and a quadratic spline curve, and solving for ray intersections with trilinear surfaces. Obviously these are continuous cube roots, not perfect cubes, but there’s a useful variation of Viete’s formula that made a few rounds on demo scene web sites. The idea that cube roots can be thought of as equally spaced points on the circle blew my mind a little. https://en.wikipedia.org/wiki/Cubic_equation#Geometric_inter...
BTW, is it still common to disallow calculators? My kids are generally allowed to use calculators for math homework and tests. I just assumed that was true most places now.
Thank you for those topics, they are interesting. Graphics programming has been something I've avoided because it's always felt too intimidating, but this feels like a nice place to start. Dynamic detail rendering built on octrees feels like a good way to handle the demands VR. I am not sure what benefits of ordering it as (2^N)^3 rather than (2^3)^N or just thinking of it as 8 all the time. Intuitively the inverse function will use log_8. I haven't come across Viete's formula before, I love these kinds of graphical solutions.
The use of calculators depends on two things, the kind of test and how accelerated a curriculum is. Standardized tests like the SAT have specific calculator and non-calculator sections. As of this year AP Chemistry will allow them during both the MC and FRQ, but that wasn't always the case. Macro and Micro both only allow a four fucntion calculator.
Whether calculators are allowed in classes depends on the teacher, but generally advanced/honors/ap classes emphasize learning to solve problems without one. Advanced classes focus on encouraging a more bottom up approach to learning how to solve problems, but in a class like Calculus, the CAS system in mainstream calculators make assessments trivial. On the AP and SAT exam, the NumWorks calculator is allowed and that's capable of running MicroPython 1.12. For my finals in AP Physics C, AP Chem, multi-var calc (in high school), I wasn't allowed a calculator. Similarly for all of my college math and cs courses, I wasn't allowed anything more than a four function calculator, despite taking the Matlab section of linear algebra and numerical analysis.
I feel frustrated that most schools fail at teaching students how to use calculators effectively. I get genuinely annoyed when students tell me they prefer a Ti-84 over a Ti-89, because it's "less confusing". Some teachers in my school district even encourage a Ti-84 for 90% of Calc BC and only talk about the Ti-89 for those handful of topics that require it. Very few teachers, let alone students, use the CAS system. I tutor in those classes every year, it hasn't changed.
I remeber I was asked by a teacher I had a good rapport with to give a presentation/demo for a handful of the other teachers during lunch. Having students graduate not knowing the "solve( f(x) = 0, x)" or how the calculator can do both symbolic and numerical integration is a failure of the education system. The TI Nspire II CAS not only has python, it has a color screen and can display animations, like turtle. If you jailbreak the Nspire with Ndless, you can even get micropython and there's an sdk that supports c and assembly to make apps. The newest Nspire OS doesn't allow the jailbreak though, and there's no way to downgrade. The only thing we used excel for in HS was making a graph or chart. I make sure my students leave with some profiency in excel, function nesting, cross sheet references, conditionals, and sorting at a minimum.
There's a difference in knowing how to use a calculator and being able to use the calculator to do what ever you want. It's the same as students knowing the steps to solve a specific math problem but not knowing why.
Oh hey my oldest got the Nspire, and did jailbreak it with Ndless! ;) She is geeking out at me while I type this with all the games she installed on it (DooM at FULL SPEED, on a calculator!!), and says the games on the calculator are the only reason she passed her math class. She agrees with you, they didn’t teach her how to use the calculator, and feels they should have.
I highly recommend diving into some graphics programming. For me, graphics is opposite of intimidating, and easily one of the best ways ever to motivate math. I love love love writing code that makes pictures & interactive graphics. It helps so much develop a more complete and intuitive understanding compared to the abstract symbolic pedagogy we got in math class. ‘Ray Tracing in One Weekend’ is a really gentle/easy introduction to ray tracing that can lead you down interesting paths depending on your motivation and interest. https://raytracing.github.io/ (Full disclosure, the book was written by a professor of mine, and I helped draw the whiteboard illustrations for the book.) One of the fun bits about ray tracing is it only requires high school math at most to get started, and you can go a long way on that alone, but if you want, you can go super deep on harder stuff, it’s both open-ended with research problems and forgiving & beginner-friendly at the same time. Graphics programming is a fabulous way to motivate matrices too. ShaderToy.com is another pretty easy way to get started, and has endless examples of neat tricks.
Interesting to try 140.something is what I'm guessing.
Edit: Ah wait cube root. That is the square root I just tried.
26.something is what my mental calculations gave me. I thought it was going to be 27. Turns out it is. I made an error somewhere which is why you gotta do this on paper.
As for method I kind of brie brute forced it. started with 100 cubed which is hundred thousand then 20 cubed which is 8000 then 30 cubed which is 3 cubed times 10 cubed which is 27k. 25 cubed which I don't remember but was less then, then I knew it could not be 26 because the number is not even. I'd deal with fractions later. so I tried 27 cubed. 27 cubed is 3^3^3=2733^5=8133^4=24333^3= 72927=72920+7297
72920=72902=14400+180=14580
7297=4900+140+63=5103
Add them and 19683 comes out
Now try that in your head and it's a good recipe for frying one's brain.
My heuristic is to find a nearby square (here, 140^2 = 19600) and divide the discrepancy (83) by double the root of the nearby square (280). This is the number to adjust by. [^0]
[^0] The Maclaurin series expansion of (A^2 + x)^(1/2) starts A + x/(2A), which is where this comes from.
83/280 is close to 84/280, which is 12/40 or 0.3. If I was trying to show off [^1], I might adjust that -- 1/28 is a quarter of a seventh, about 0.0357, so I can take 0.004 off of my adjustment to get 0.296 or 0.297.
[^1] I mean, show off more.
(The actual answer is 140.29611 -- the "0.3" adjustment is right to one part in 36,000; "0.296" is right to one part in 1.2 million.)
If you know that the number is a perfect cube, you could also try Hensel's lemma or CRT, or Euler, all of which are aaaaalmost doable in your head for 2 digits, but maybe not quite.
Suppose you are trying to find cbrt(x), and you know the answer is a 2-digit integer.
===============
Hensel: first you have to remove any powers of 5 and 2. You know the cube root is even if the number is even, and a multiple of 5 if the number is a multiple of 5 (ends in a 0 or 5). So factor those out first. It now ends in 1,3,7 or 9.
Find the cube root w of x mod 10, and t = 1/3x mod 10, by trial and error. Eg, x=19683 ends in 3, so w ends in 7 (since 7^3 ends in 3); t = 1/3x ends in 9 since 39x ends in 1.
Calculate the tens digit of the error term e = x - w^3, which is always a multiple of 10. In this case it's ...683 - 343 === 40, and apply the adjustment w ==> w + wte. You only need to calculate the 10s digit of wte. In this case, it's the 10's digit of 7*9*40 = 63*40 is 20.
That's all, the answer is 27.
===============
CRT: Find the answer mod 10 and mod 11. As before, the answer here mod 10 is 7.
For mod 11, you can reduce it to a 2-digit problem by applying %99 first, i.e. shifting each digit over by 2 until it's a 10s or 1s digit, and adding. We have 19683 mod 11 = (1 + 96 + 83) mod 11 = 180 mod 11 = 81 mod 11 = 4.
Find the cube root mod 11 by exhaustion, or by memorization, or by taking the 7th power of the input (Fermat's theorem). In this case, it's 5, because 5^3 mod 11 = 125 mod 11 =(1+25) mod 11 = 4.
Solve using the CRT: if a number is y mod 10 and z mod 11, then it's y + 10(y-z mod 11). In this case, it's 7 + 10(7-5 mod 11) = 27.
================
Euler: the answer is always the same as the last 2 digits of x^7. Calculate eg x^2, x^3, x^6, x^7 with four multiplications. You only need the last two digits.
Probably this is the easiest approach by hand.
================
If you want to solve on a computer, then Hensel mod 2^n (continuing the pattern appropriately for more bits) is probably the fastest bet.
> all of which are aaaaalmost doable in your head for 2 digits, but maybe not quite.
You might be good at Mathematics, this is like a standard trick the average student can do. There are lots of other approaches but the easiest one to do mentally is this.
I got 27 in about 10 seconds by doing a quick binary search and noticing the number ended in 3 (so it’s gotta end in 7). It’s in between 20 (8000) and 30 (27000).
Applying the formula isn't that hard, but this one could be hard to write about because it depends upon the amount of time the sum is compounding or the exponent in the equation.
^2 and ^3 are quite easy but when it comes to ^7/^9 there's no easy way to calculate mentally.
First we observe x is between 20^3=8e3 and 30^3=27e3.
Then note that the least significant (singles) digit of x^3 is solely determined by the singles digit of x [only holds in the integers].
Luckily we had cached that the pattern for cubes is 123456789 -> 187456329
Finally x^3 = 19,683 ends in 3 therefore x = 27 we are done.
------
It turns out there is a unique mapping for the first digit of x^n, following one of four patterns:
n mod 4 = 1 123456789 -> 123456789
n mod 4 = 2 -> 149656941
n mod 4 = 3 -> 187456329
n mod 4 = 0 -> 161656161
So this trick would not always be as useful, where the mapping is not surjective for squares, fourth powers -- all the even powers. I imagine there is a nice visual geometric explanation why those mappings take their symmetric pattern.
You may ask yourself, is there also a rule for the larger place digits of x^3, x^n? Yes, we naturally observe that the 10s digit of x^n is similarly wholly determined by the 10s and 1s digits of x. So now we want n maps on [0,9]x[0,9] to [0,9].
The python snippet may help to explore this:
where the row 3, 25th digit shows that when x ends in 25, x cubed has 10s digit 2
Apologies for the wall of text but the output is included here to show the periodicity is 20 in the 10s digit for powers of n.
What do you think the periodicity in the 100s digit is?
Okay let's use our cache to just lookup the least two digits of say, 41679296 ^ 35 (without doing any real compute):
1s digit
35 mod 4 = 3
187456329 index 6 -> 6
10s digit
(35, '0060227434056527793900602274340565277939006022743405652779390060227434056527793900602274340565277939')
index ------96 -> 7
The last two digits of 41679296 ^ 35 = 497981393104388234083687472206165994017494365065741791800324926291638211001469403054062791593737655590988883756006534609416313532750908441977019034732014717649617778735038244085515193249673259731575280032440237649262981884959117005449913087392615145373869733708824576 are indeed 76, cool
Learn a handful of logs base 10 (not much more work than the cube digit laws). Maybe you know 2,3,5 and e.
19,683 is equal to 20,000
log 20,000 is log 2 + log 10 + log 10 + log 10 + log 10
That's 0.30 + 1 + 1 + 1 + 1 which is 4.30
Divide by 3 (equivalent to taking cube root). That's 1.43
Recall that log e is 0.43. So 1.43 is log (e * 10). Hopefully you remember e = 2.71, so the number you're looking for is 27.1. If you remember that you rounded up to start, you can round back down and guess that it's more like 27.0.
You can simplify this a little further by dividing out thousands and multiplying by 10s at the end, so you only need to find the cube root of 20 using the same process.