如何以最简单的方式找到某个幂的单位位数 [英] How to find the units digit of a certain power in a simplest way

问题描述

如何找出某个数字的单位数字(例如3 power 2011).我应该使用什么逻辑来找到这个问题的答案?

How to find out the units digit of a certain number (e.g. 3 power 2011). What logic should I use to find the answer to this problem?

推荐答案

对于基础3:

3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
...

即单位数字只有4种可能性，然后以相同的周期重复.

That is the units digit has only 4 possibilities and then it repeats in ever the same cycle.

借助欧拉定理，我们可以证明这适用于任何整数n ，这表示它们的单位位数将在最多4个连续的指数之后重复.仅查看任意乘积的单位数字等效于采用乘模10的余数，例如:

With the help of Euler's theorem we can show that this holds for any integer n, meaning their units digit will repeat after at most 4 consecutive exponents. Looking only at the units digit of an arbitrary product is equivalent to taking the remainder of the multiplication modulo 10, for example:

2^7 % 10 = 128 % 10 = 8 

还可以显示(并且非常直观)，对于任意基数，任何幂的单位数字将仅取决于基数本身的单位数字-即2013 ^ 2013具有与3相同的单位数字^ 2013.

It can also be shown (and is quite intuitive) that for an arbitrary base, the units digit of any power will only depend on the units digit of the base itself - that is 2013^2013 has the same units digit as 3^2013.

我们可以利用这两个事实提出一种非常快速的算法(感谢

We can exploit both facts to come up with an extremely fast algorithm (thanks for the help - with kind permission I may present a much faster version).

这个想法是这样的:众所周知，对于任何0-9的数字，最多会有4种不同的结果，我们也可以将它们存储在查找表中:

The idea is this: As we know that for any number 0-9 there will be at most 4 different outcomes, we can as well store them in a lookup table:

{ 0,0,0,0, 1,1,1,1, 6,2,4,8, 1,3,9,7, 6,4,6,4, 
  5,5,5,5, 6,6,6,6, 1,7,9,3, 6,8,4,2, 1,9,1,9 }

这是0-9可能的结果，以四个为一组.现在的想法是将n ^ a乘以

That's the possible outcomes for 0-9 in that order, grouped in fours. The idea is now for an exponentiation n^a to

• 首先获取基本mod 10 =>:= i
• 转到表中的索引4*i(这是该特定数字的起始偏移量)
• 取指数模4 =>:= off(如欧拉定理所述，我们只有四个可能的结果！)
• 将off添加到4*i以获取结果

• first take the base mod 10 => := i
• go to index 4*i in our table (it's the starting offset of that particular digit)
• take the exponent mod 4 => := off (as stated by Euler's theorem we only have four possible outcomes!)
• add off to 4*i to get the result

现在，为了尽可能提高效率，对基本算术运算进行了一些调整:

Now to make this as efficient as possible, some tweaks are applied to the basic arithmetic operations:

• 乘以4等于向左移两个('<< 2')
• 取数字a % 4等同于说出a&3(屏蔽1位和2位，构成余数％4)

• Multiplying by 4 is equivalent to shifting two to the left ('<< 2')
• Taking a number a % 4 is equivalent to saying a&3 (masking the 1 and 2 bit, which form the remainder % 4)

C语言中的算法:

static int table[] = {
    0, 0, 0, 0, 1, 1, 1, 1, 6, 2, 4, 8, 1, 3, 9, 7, 6, 4, 6, 4, 
    5, 5, 5, 5, 6, 6, 6, 6, 1, 7, 9, 3, 6, 8, 4, 2, 1, 9, 1, 9
};

int /* assume n>=0, a>0 */ 
unit_digit(int n, int a)
{
    return table[((n%10)<<2)+(a&3)];
}

---

初始索赔的证明

通过观察，我们注意到3 ^ x的单位数字每四次幂重复一次.声称这适用于任何整数.但是，如何证明这一点呢?事实证明，使用模块化算法非常容易.如果我们只对单位数字感兴趣，则可以以10为模执行计算.这等于说4个指数后的单位数字循环，或者说

From observing we noticed that the units digit for 3^x repeats every fourth power. The claim was that this holds for any integer. But how is this actually proven? As it turns out that it's quite easy using modular arithmetic. If we are only interested in the units digit, we can perform our calculations modulo 10. It's equivalent to say the units digit cycles after 4 exponents or to say

a^4 congruent 1 mod 10

如果这成立，那么例如

a^5 mod 10 = a^4 * a^1 mod 10 = a^4 mod 10 * a^1 mod 10 = a^1 mod 10

也就是说，a ^ 5产生的单位位数与a ^ 1相同，依此类推.

that is, a^5 yields the same units digit as a^1 and so on.

根据欧拉定理，我们知道

a^phi(10) mod 10 = 1 mod 10

其中phi(10)是1到10之间的数字，它们互质为10(即，其gcd等于1).数字< 10到10的互质数分别是1,3,7和9.因此phi(10)= 4，这证明了a^4 mod 10 = 1 mod 10的确.

where phi(10) is the numbers between 1 and 10 that are co-prime to 10 (i.e. their gcd is equal to 1). The numbers < 10 co-prime to 10 are 1,3,7 and 9. So phi(10) = 4 and this proves that really a^4 mod 10 = 1 mod 10.

最后要证明的是，对于基数> = 10的幂运算，仅查看基数的单位数字就足够了.假设我们的基数是x> = 10，那么我们可以说x = x_0 + 10 * x_1 + 100 * x_2 + ...(以10为基数表示)

The last claim to prove is that for exponentiations where the base is >= 10 it suffices to just look at the base's units digit. Lets say our base is x >= 10, so we can say that x = x_0 + 10*x_1 + 100*x_2 + ... (base 10 representation)

使用模块化表示，很容易看到确实如此

Using modular representation it's easy to see that indeed

x ^ y mod 10
= (x_0 + 10*x_1 + 100*x_2 + ...) ^ y mod 10
= x_0^y + a_1 * (10*x_1)^y-1 + a_2 * (100*x_2)^y-2 + ... + a_n * (10^n) mod 10
= x_0^y mod 10  

其中a_i是包括x_0的幂但最终不相关的系数，因为整个乘积a_i *(10 * x_i)^ y-i将被10整除.

where a_i are coefficients that include powers of x_0 but finally not relevant since the whole product a_i * (10 * x_i)^y-i will be divisible by 10.

这篇关于如何以最简单的方式找到某个幂的单位位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！