Last digit of power list

问题:

Outline of problem:

Please note I will abuse the life out of ^ and use it as a power symbol, despite the caret symbol being the bitwise XOR operator in JS.

Take a list of positive integers,

[ x_0, x_1, ..., x_n ]

and find the last digit of the equation given by

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

I'll call this function LD(...) for the rest of this question.

Example: For a list of integers a = [2, 2, 2, 2] and given that 2 ^ (2 ^ (2 ^ 2)) = 65536, it's easy to see that LD(a) = 6.

Note that 0 ^ 0 === 1 for this question, consistent with x ^ 0 === 1, but not with 0 ^ x === 0.

---

What I've achieved so far

It's easy to conclude that x ^ 0 === 1, no matter what.

It's also pretty easy to conclude that last digits of powers "loop" around if you do a few test cases:

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,
...

So if we know the count of numbers that are in the loop for a particular base (4 for the above example of the base 2), we can use the modulus of that count to work out the last digit.

E.g., LD(2 ^ 55) === LD(2 ^ (55 % 4)) === LD(2 ^ 3)

And so with a bit of maths, we can get ourselves a nice array-of-arrays for each last digit, where the index of the array-of-arrays is the base and the index of each array is the modulus of the loop length:

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 ]     
];

Example of usage: LD(3^7) === p[3][7-1 % 4] - note that we have to subtract one from the exponent as each array is 0-based.

So we arrive at the JavaScript:

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

The a % 10 should be obvious, it takes just the last digit of the base number as the index in our array-of-arrays, as any non-units do not affect the last digit.

For a list like [1,2,3] from the beginning of the question, this can be made recursive. We have an initial value of 1, in case of empty lists, as x^1 === x, and we reverse the list to make use of accumulation of the .reduce() method:

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

Following through so that makes sense would look like the following:

• First up, a = 1 (initial value), v = 3; then p[3 % 10] === p[3] === [ 3,9,7,1 ], and thus [ 3,9,7,1 ][ (1-1) % [ 3,9,7,1 ].length] === [ 3,9,7,1 ][ 0 % 4 ] === 3.
• Then, a = 3 (last iteration), v = 2; so p[2] === [ 2,4,8,6 ], and so [ 2,4,8,6 ][ 2 % 4 ] === 8.
• Finally, a = 8, v = 1; p[1] === [ 1 ], and [ 1 ][ 8 % 1 ] === 1.

So, we get LD([1, 2, 3 ]) === 1, which isn't hard to verify: 1 ^ (2 ^ 3) === 1 ^ 8 === 1.

---

The problem:

This works, so long as the exponent is not over 10 and there isn't another iteration after that. However, if there is things go awry. Let me explain:

Say we have the array, a = [ 2,2,2,2 ]. As 1 is our initial value, the list is initially a = [ 1,2,2,2,2 ]. Using the reduction above:

• First iteration a = 1, v = 2 (remembering that our .reduce has 1 as it's initial value):
  • p[2 % 10][(1-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][0 % 4]
  • = 2
  • Easily verified by 2 ^ 1 = 2, our list is now [ 2,2,2,2 ]
• Second iteration a = 2, v = 2:
  • p[2 % 10][(2-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][1 % 4]
  • = 4
  • Easily verified by 2 ^ 2 = 4, our list is now [ 4,2,2 ]
• Third iteration a = 4, v = 2:
  • p[2 % 10][(4-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][3 % 4]
  • = 6
  • Easily verified by 2 ^ 4 = 16, our list is now [ 16,2 ]
• Fourth iteration, where the issue becomes apparent. a = 6, v = 2:
  • p[2 % 10][(6-1) % p[2 % 10].length]
  • = [ 2,4,8,6 ][5 % 4]
  • = 4
  • Easily disproved by 2 ^ 16 = 65536.

And if you study that for a while it becomes obvious why. The third step in the final iteration,

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

should be

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

Therefore giving an incorrect result.

---

Question:

Is there a way, based on the previous exponent, to capture that "offset" created by only passing on the last digit of the previous iteration? Can I somehow pass on the 6 in that last iteration with another piece of information so that the modulus is correct?

So instead of just returning

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

maybe it could return

[ 
  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**
]

where fn(a[0], a[1]) uses both the accumulated value from before, as well as some other information to calculate the correct mod value. This doesn't necessarily have to be an array, maybe an object or tuple as @aec pointed out in the comments.

One (terrible) solution would be to keep track of the previous iteration in the accumulator (e.g., for that last step, instead of returning 6, I could return 16 and use that for the next iteration, which would give the correct index). However, it's very impractical if the numbers were very large! Say the previous step had the numbers 4142 and 623, it's not practical to calculate 4142^623 and pass that on.

Please note that I understand there are other solutions to this, but I am curious if I can change this code to solve this problem in the single .reduce statement I've written. So is it possible to solve this problem by modifying:

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

despite the discussed accumulator problem? It nearly works, and I think I'm one trick away from it working!

Please note the brackets! The list [3, 14, 16] is equivalent to 3 ^ (14 ^ 16) !== (3 ^ 14) ^ 16

A few tests to check against, which can be verified for function call LU(array), where array is the array of numbers:

// 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)  

Tested here: http://www.wolframalpha.com/widgets/view.jsp?id=56c82ccd658e09e829f16bb99457bcbc

Thank you for reading!

---

Further ideas:

Had a mini-breakthrough! So for any integer that is a base of an exponent (i.e., the x in x^y), LD(x) === LD(x % 10). This is because the digits past the first (right-to-left) do not affect the unit digit of the exponent result (e.g., LD(23 ^ 7) === LD(3 ^ 7))

Also, as in const p = [ ..., the array-of-arrays containing the cycles of unit values, all numbers have cycles of a length with a lowest common multiple of 4. i.e., all cycles are either 1, 2 or 4 numbers (e.g., the p[3] === [ 3,9,7,1 ] unit array has length four).

So, we can conclude LD((x % 10) ^ (y % 4)) === LD(x ^ y).

Note however if a number is a multiple of 4, it becomes zero. We don't want this most of the time! You don't want 20 to becomes 0 on the exponent side either - we want the range for x to be 1 through 10, and for y to be 1 through 4:

So, LD((x % 10 || 10) ^ (y % 4 || 4)) === LD(x ^ y). We can handle the special cases with

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 {
  ...
}

This is very interesting! It means it is now reasonable to calculate LD(x ^ y), but I'm not sure what to do with this information.

回答1:

Finally! after doing some digging about I realized I can modify the initial idea and get the answer I wanted:

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

Tests:

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

let LDTest = (array, expected) => 
  console.log((LD(array) === expected ? "Success" : "Failed"), 
    "for", array, "got", LD(array), "expected", expected);

LDTest([ 2, 2, 2 ],    6)
LDTest([ 2, 2, 2, 2 ], 6)
LDTest([ 3, 4, 5 ],    1)
LDTest([ 6, 8, 10 ],   6)
LDTest([ 2, 2, 0 ],    2)
LDTest([ 12, 30, 21 ], 6) 
LDTest([ 0, 0 ],       1) // x^0 === 1 
LDTest([ 0 ],          0)  

So why modulo 20? Because a modulus of 10 loses precision in the cases such as [ 2,2,2,2 ], when we hit the last step as from the question example:

Fourth iteration, where the issue becomes apparent. a = 6, v = 2:

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

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

= 4

Easily disproved by 2 ^ 16 = 65536.

By simply allowing a multiple up to 20, we have the LCM (lowest common multiple) for each count of the array, as well as for the length of p, which is 10. (LCM([ 1,2,4,10 ]) === 20).

However, as the exponential is now never higher than 40^8 (approximately 6 trillion), and as it is taken to the modulo of 4 in the next iteration, we can simply do the exponential and return the answer each time.

Of course to get the digit in the final case, we need to take modulo of 10 to just return that last digit.

---

There's still some stuff I'm not understanding here.

We allow any value under the modulo value to retain its value with the ternary operators. E.g., for the exponent, prev < 4 ? prev : (prev % 4 + 4). However I initially believed this to be prev === 0 ? 0 : (prev % 4 + 4).

This is because th exponent of zero does not have the same ending digit as the other multiples of the modulo, it always equals 1 (x ^ 0 === 1). So, by adding 4, we get a value that does have the same last digit, and by leaving zero alone we still get 1 for zero exponents.

Why is it that prev < 4 ? prev : (prev % 4 + 4) was required to make this answer correct? Why is e.g., prev = 3, need to be 3 instead of adding 4 like the others?

回答2:

I believe your top-down approach is somewhat flawed, because LD(b) is not the only determining factor in LD(a^b), unlike with a - i.e. all digits of b influence the value of LD(a^b). Therefore, with a top-down algorithm, it only makes sense to compute the LD at the end, which kind of defeats the point.

---

That's not to say the formula you derived is useless - quite the opposite.

Looking at the inner index, we see that (b - 1) % p[a % 10].length could potentially be computed recursively bottom-up. So what are the possible values of L = p[a % 10].length? 1, 2, and 4. The corresponding possible values for I = (b - 1) % L are:

• For L = 1, I = 0 trivially.
• For L = 2, I = 0 if b is odd. Let b = c ^ d, and note that b is odd if either c is odd or d = 0, otherwise even. Thus this case is also trivial if we peek at the next number in the array.

• For L = 4, I is simply the last digit of b - 1 in base 4 (call it LD4). We can compute an analogous digit table, and process the rest of the array as before:

  // base 4 table
  const q = [
     [0],  // 0^1=0 ...
     [1],  // 1^1=1 ...
     [2, 0, 0, 0, ..... ], // infinitely recurring
     [3, 1], // 3^1=3, 3^2=1, 3^3=3, 3^4=1 ...
  ];
  

Ah. Well, since there are so few cases, a few if-clauses won't hurt:

LD2(a) | LD2(a^b)
----------------------------
0      | 1 if b = 0, else 0
1      | 1 always

LD4(a) | LD4(a^b)
----------------------------------------
0      | 1 if b = 0, else 0
1      | 1 always
2      | 1 if b = 0, 2 if b = 1, else 0
3      | 3 if b odd, else 1

With the assumption that 0^0 = 1. Also, LD4(b - 1) = LD4(b + 3).

---

Code:

function isEnd(a, i)
{
   return (i > a.length - 1);
}

function isZero(a, i)
{
   if (!isEnd(a, i))
      if (a[i] == 0)
         return !isZero(a, i+1);
   return false;
}

function isUnity(a, i)
{
   if (isEnd(a, i) || a[i] == 1)
      return true;
   return isZero(a, i+1);
}

function isOdd(a, i)
{
   if (isEnd(a, i) || a[i] % 2 == 1)
      return true;
   return isZero(a, i+1);
}

function LD2(a, i)
{
   if (isEnd(a, i) || a[i] % 2 == 1)
      return 1;
   return isZero(a, i+1) ? 1 : 0;
}

function LD4(a, i)
{
   if (isEnd(a, i)) return 1;
   switch (a[i] % 4) {
      case 0: return isZero(a, i+1) ? 1 : 0;
      case 1: return 1;
      case 2: 
         if (isZero(a, i+1)) return 1;
         if (isUnity(a, i+1)) return 2;
         return 0;
      case 3: return isOdd(a, i+1) ? 3 : 1;
      default: return -1; // exception?
   }
}

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 ]
];

function LD10(a)
{
   let LDa = a[0] % 10;
   if (isZero(a, 1)) return 1; // corner case not present in tables
   const row = p[LDa];
   switch (row.length) {
      case 1: return row[0];
      case 2: return row[1 - LD2(a, 1)];
      case 4: return row[(LD4(a, 1) + 3) % 4];
      default: return -1; // exception?
   }
}

The above code now passes all test cases.

回答3:

lets keep in mind that (a^b)%c = (a%c)^b % c.

I want to know lastDigit.
lastDigit = x^y^z % 10 = (x%10 ^ y ^ z) % 10.

p[x % 10] has the pattern of repetition of powers of x. A pattern can have a length of 1, 2 or 4.

If the pattern had a length of 4, then lastDigit = p[x][(y^z % 4)] = p[x][(y%4)^z %4]

If our problem was not for x,y,z but for x0,x1,x2...xn:

lastDigit
 = p[x0][(x1 ^ x2 ... ^ xn-1 ^ xn) %4]
 = p[x0][((x1 ^ x2 ... ^ xn-1)%4 ^ xn) %4]

And I think teh recursive nature is apparent now:

I will use the number 4 for remainder because it is the smallest number that can divide 1, 2 and 4, for which patterns are also relatively easy to find.

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 ]	 
];

//returns x^y % 4
function powMod4(x, y) {
	switch (x % 4) {
		case 0:
			return 0;
		case 1:
			return 1;
		case 2:
			return y == 1 ? 2 : 0;
		case 3:
			return (y % 2) == 0 ? 1 : 3;
	}
}

function foo(arr) {
	arr = arr.map((it, i, list) => {
		if (i + 1 < list.length && list[i + 1] === 0) {
			return 1;
		} else {
			return it;
		}
	}).filter(x => x !== 0);

	let firstElem = arr[0] % 10;
	let l = p[firstElem].length

	let resp = arr.slice(1).reduce((acc, v) => {
		if (acc === undefined) {
			return v
		}
		let rem = powMod4(acc, v);
		//console.log(v, acc, " => ", rem);
		return rem;

	}, undefined);


	return p[firstElem][(resp + l - 1) % l];
}

function test(arr, expected) {
  let resp = foo(arr);
	console.log(arr.join("^"), resp, resp == expected ? "ok" : "FAIL")
}

test([3, 4, 5], 1)
test([2, 2, 2, 2], 6)
test([4, 13, 16], 4)
test([3,5,7,10], 3)
test([41,42,43], 1)
test([7,6,21], 1)
test([2,2,2,0], 4)

So all I did is, I dropped the LD function. Instead, I am trying to find x1^x2...^xn % p[x0].length. In contrast, you were trying to find x1^x2...^xn % 10