I was actually pretty surprised myself that any infinite series converges modulo any modulus, I would've guessed that there are worst case infinite sequences, but there really aren't any
@orlp All right I've got it passing the test cases now. 8465201675951680207872013773238924239120749558569556332497369498145712209145188977345043177395978241?
I will show how to generally evaluate $a_1^{\,a_2^{\,\cdots}} \bmod m$, recursively.
If $(a_1 \bmod m) \leq 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.
Otherwise, if $\gcd(a_1, m) = 1$, we have $a_1^{\,a_2^{\,\cdots}} \equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(m)}\mod m$. Recursively e...
this is my writeup/algorithm
@feersum I wonder if you did some parts differently perhaps
even sequences that have infinite zeroes or ones (finite power towers)
anyway, ill be back in like 2 hours
@feersum question to think about in the meantime, given an (infinite) sequence a, does the sequence of residues of the power tower modulo 1, 2, ..., inf uniquely determine a?
egcd:: Int -> Int -> (Int, Int, Int)
egcd a b
| a < b = let (g,r,s) = egcd b a in (g,s,r)
| b == 0 = (a, 1, 0)
| otherwise = let (g,r,s) = egcd (a-b) b in (g,r,s-r)
Given an infinite sequence $a_1, a_2, \dots$ where all $a_i > 1$ we study $a_1^{\,a_2^{\,\cdots}} \bmod m$. While this is an infinite power tower that grows without bound, I argue that it can be assigned a value. If $f(n)$ is the power tower with the first $n$ terms of $a$, there is a constant $c...
The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".
But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that th...
@feersum I actually doubted whether I would be able to do it at all, so I gave my self a shoulderpad for actually coming up with a function that actually works :D
SWI-Prolog, 62 47 41 bytes
X*Y:-X+Y;Y+X;X==Y.
X?Y:-not(X*Y),X*Z,Y*Z.
Prolog isn't too often useful, but when it is it's just beautiful. We'll use a+b to notate that a is friends with b, a*b that a knows b and a?b that b should be suggested to a or not. The first line simply says that X*Y is tr...