电源列表的最后一位数字

Question

问题大纲:

请注意^,尽管插入符号是JS中的按位XOR运算符,但我会滥用生命并将其用作幂符号.

列出正整数,

[ x_0, x_1, ..., x_n ]

并找到由下式给出的等式的最后一位数

x_0 ^ ( x_1 ^ (... ^ x_n ) ... )

我会LD(...)在这个问题的其余部分调用此函数.

示例:对于整数列表,a = [2, 2, 2, 2]并给出它2 ^ (2 ^ (2 ^ 2)) = 65536,很容易看到LD(a) = 6.

请注意,0 ^ 0 === 1对于这个问题,与...一致x ^ 0 === 1,但不一致0 ^ x === 0.

---

到目前为止我取得的成就

x ^ 0 === 1无论如何,很容易得出结论.

如果你做了一些测试用例,那么很容易得出结论:权力的最后数字"循环":

LD(2 ^ 1) = 2,
LD(2 ^ 2) = 4,
LD(2 ^ 3) = 8,
LD(2 ^ 4) = 6,
LD(2 ^ 5) = 2, // Notice we've looped from hereon
LD(2 ^ 6) = 4,
LD(2 ^ 7) = 8,
...

因此,如果我们知道特定基数的循环中的数字计数(对于基础2的上述示例为4),我们可以使用该计数的模数来计算最后一位数.

例如, LD(2 ^ 55) === LD(2 ^ (55 % 4)) === LD(2 ^ 3)

因此,通过一些数学运算,我们可以为每个最后一个数字获得一个很好的数组数组,其中数组数组的索引是基数,每个数组的索引是循环长度的模数:

const p = [
  [ 0 ],      // 0^1=0, 0^2=0 ...
  [ 1 ],      // 1^1=1, 1^2=1 ...
  [ 2,4,8,6 ] // 2^1=2, 2^2=4 ...
  [ 3,9,7,1 ] // 3^1=3, 3^2=9 ...
  [ 4,6 ]     
  [ 5 ]       
  [ 6 ]       
  [ 7,9,3,1 ] 
  [ 8,4,2,6 ] 
  [ 9,1 ]     
];

用法示例:LD(3^7) === p[3][7-1 % 4]- 请注意,我们必须从指数中减去一个,因为每个数组都是从0开始的.

所以我们到达了JavaScript:

LD(Math.pow(a,b)) === p[a % 10][(b-1) % p[a % 10].length]

本a % 10应该是显而易见的,它只需基数在我们的阵列阵列,该指数的最后一位数字,因为任何非单位不影响最后一位.

对于类似于[1,2,3]问题开头的列表,可以使其递归.在空列表的情况下,我们的初始值为1,x^1 === x并且我们反转列表以使用该.reduce()方法的累积:

[1,2,3].reduceRight( (a,v) => 
  p[v % 10][(a-1) % p[v % 10].length], 1)

通过这样有意义将如下所示:

• 首先,a = 1 (initial value), v = 3; 然后p[3 % 10] === p[3] === [ 3,9,7,1 ],因此[ 3,9,7,1 ][ (1-1) % [ 3,9,7,1 ].length] === [ 3,9,7,1 ][ 0 % 4 ] === 3.
• 然后,a = 3 (last iteration), v = 2; 所以p[2] === [ 2,4,8,6 ],等等[ 2,4,8,6 ][ 2 % 4 ] === 8.
• 最后,a = 8, v = 1; p[1] === [ 1 ],和[ 1 ][ 8 % 1 ] === 1.

所以,我们得到了LD([1, 2, 3 ]) === 1,这不难确认:1 ^ (2 ^ 3) === 1 ^ 8 === 1.

---

问题:

这是有效的,只要指数不超过10并且之后没有另一次迭代.但是,如果有事情出错.让我解释:

假设我们有阵列,a = [ 2,2,2,2 ].作为1我们的初始值,该列表最初是a = [ 1,2,2,2,2 ].使用上面的减少:

• 第一次迭代a = 1, v = 2(记住,我们.reduce已经1为它的初始值):
  • p[2 % 10][(1-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][0 % 4]
  • = 2
  • 很容易验证2 ^ 1 = 2,我们的列表现在是[2,2,2,2]
• 第二次迭代a = 2, v = 2:
  • p[2 % 10][(2-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][1 % 4]
  • = 4
  • 很容易验证2 ^ 2 = 4,我们的列表现在是[4,2,2]
• 第三次迭代a = 4, v = 2:
  • p[2 % 10][(4-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][3 % 4]
  • = 6
  • 轻松验证2 ^ 4 = 16,我们的列表现在[16,2]
• 第四次迭代,问题变得明显.a = 6, v = 2:
  • p[2 % 10][(6-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][5 % 4]
  • = 4
  • 很容易被反驳2 ^ 16 = 65536.

如果你研究了一段时间,它就变得很明显了.最后一次迭代的第三步,

= [ 2,4,8,6 ][5 % 4] = p[ 2,4,8,6 ][1]

应该

= [ 2,4,8,6 ][15 % 4] = p[ 2,4,8,6 ][3]

因此给出了错误的结果.

---

题:

有没有办法,基于前面的指数,捕获仅通过前一次迭代的最后一位数创建的"偏移量"？我能以某种方式6在最后一次迭代中传递另一条信息,以便模数正确吗？

所以而不仅仅是返回

p[v % 10][(a-1) % p[v % 10].length)

也许它可以回来

[ 
  p[v % 10][fn(a[0], a[1]) % p[v % 10].length],
  **some other clever information here to use in the calculation to make the modulus correct**
]

其中fn(a[0], a[1])既使用了之前的累计值,也使用了其他一些信息来计算正确的mod值.这不一定是一个数组,可能是@aec在注释中指出的对象或元组.

一个(可怕的)解决方案是跟踪累加器中的先前迭代(例如,对于最后一步,而不是返回6,我可以返回16并将其用于下一次迭代,这将给出正确的索引).但是,如果数字非常大,这是非常不切实际的!说前面的步骤有编号4142和623,这是不实际的计算4142^623和传递上.

请注意,我知道还有其他解决方案,但我很好奇是否可以在.reduce我编写的单个语句中更改此代码以解决此问题.那么可以通过修改来解决这个问题:

array.reduceRight( (a,v) => 
  p[v % 10][(a-1) % p[v % 10].length], 1)

尽管讨论过累加器问题？它几乎可以工作,我认为我是一个远离它工作的技巧!

请注意括号!该列表[3, 14, 16]相当于3 ^ (14 ^ 16) !== (3 ^ 14) ^ 16

一些要检查的测试,可以验证函数调用LU(array),其中array是数字数组:

// Current attempt
const p = [
  [ 0 ],      // 0^1=0, 0^2=0 ...
  [ 1 ],      // 1^1=1, 1^2=1 ...
  [ 2,4,8,6 ], // 2^1=2, 2^2=4 ...
  [ 3,9,7,1 ], // 3^1=3, 3^2=9 ...
  [ 4,6 ],     
  [ 5 ],       
  [ 6 ],       
  [ 7,9,3,1 ], 
  [ 8,4,2,6 ], 
  [ 9,1 ]     
];

// CURRENT ATTEMPT
let LU = array => 
  array.reduceRight( (a,v) => 
    a === 0 ? 1 : p[v % 10][(a-1) % p[v % 10].length]
  , 1);

let LUTest = (array, expected) => 
  console.log(
    (LU(array) === expected ? "Success" : "Failed"), 
    "for", array, "got", LU(array), "expected", expected);
    
LUTest([ 2, 2, 2 ],    6)
LUTest([ 2, 2, 2, 2 ], 6)
LUTest([ 3, 4, 5 ],    1)
LUTest([ 6, 8, 10 ],   6)
LUTest([ 2, 2, 0 ],    2)
LUTest([ 12, 30, 21 ], 6) 
LUTest([ 0, 0 ],       1) // x^0 === 1 
LUTest([ 0 ],          0)  

在这里测试:http://www.wolframalpha.com/widgets/view.jsp？id = 56c82ccd658e09e829f16bb99457bcbc

谢谢你的阅读!

---

更多想法:

有一个小突破!因此,对于任何整数,它是一个指数(即,的基座x中x^y), LD(x) === LD(x % 10).这是因为经过第一个(从右到左)的数字不会影响指数结果的单位数(例如LD(23 ^ 7) === LD(3 ^ 7))

此外,如同const p = [ ...包含单位值周期的数组阵列一样,所有数字都具有长度为4的最小公倍数的周期.即,所有周期都是1,2或4个数字(例如,p[3] === [ 3,9,7,1 ]单位)数组长度为4).

所以,我们可以得出结论LD((x % 10) ^ (y % 4)) === LD(x ^ y).

但请注意,如果数字是4的倍数,则它变为零.我们大多数时候都不想要这个!你也不想20成为0指数方面 - 我们希望范围为x1到10,y为1到4:

所以,LD((x % 10 || 10) ^ (y % 4 || 4)) === LD(x ^ y).我们可以处理特殊情况

if (x === 0) { 
  return 0 // 0^anything = 0, including 0^0 for argument's sake.
} else if (y === 0) {
  return 1 // anything ^ 0 = 1, excluding 0^0
} else {
  ...
}

这很有意思!这意味着现在计算合理LD(x ^ y),但我不知道如何处理这些信息.

Answer 1

最后！经过一番挖掘后，我意识到我可以修改最初的想法并得到我想要的答案：

let LD = (as) =>
  as.reduceRight((acc, val) =>
    Math.pow(val < 20 ? val : (val % 20 + 20), acc < 4 ? acc : (acc % 4 + 4)) 
  , 1) % 10

测试：

let LD = (as) =>
  as.reduceRight((acc, val) =>
    Math.pow(val < 20 ? val : (val % 20 + 20), acc < 4 ? acc : (acc % 4 + 4)) 
  , 1) % 10

所以为什么modulo 20？因为在 等情况下，模数 10 会失去精度[ 2,2,2,2 ]，当我们达到问题示例中的最后一步时：

第四次迭代，问题变得明显。a = 6, v = 2:

p[2 % 10][(6-1) % p[2 % 10].length]

= [ 2,4,8,6 ][5 % 4]

= 4

很容易被反驳2 ^ 16 = 65536。

通过简单地允许最大 20 的倍数，我们就得到了数组每个计数的 LCM（最小公倍数），以及 的长度p，即 10。 (LCM([ 1,2,4,10 ]) === 20）。

然而，由于指数现在永远不会高于40^8（大约 6 万亿），并且在下一次迭代中以 4 为模，我们可以简单地执行指数并每次返回答案。

当然，为了获得最终情况下的数字，我们需要对 10 取模以返回最后一位数字。

这里还有一些我不明白的东西。

我们允许模值以下的任何值通过三元运算符保留其值。例如，对于指数，prev < 4 ? prev : (prev % 4 + 4). 但我最初相信这是prev === 0 ? 0 : (prev % 4 + 4)。

这是因为零的指数与模数的其他倍数没有相同的结束数字，它始终等于 1 ( x ^ 0 === 1)。因此，通过加 4，我们得到一个具有相同最后一位数字的值，并且通过保留零，我们仍然得到零指数的 1。

为什么需要prev < 4 ? prev : (prev % 4 + 4)使这个答案正确？为什么需要eg, prev = 3, 而不是3像其他的那样加4？