12:00 PM
Reminds me of action painting

in The Nineteenth Byte, 35 secs ago, by orlp
CMC: what are the last 100 decimal digits of 2017^2018^2019^...? (keep in mind exponentiation is right associative, 2^3^4 = 2^(3^4))

My guess (with no hint of a proof) would be a string of zeroes after long enough

@trichoplax if you're talking in the last decimal digits, nope

I guessed not shortly after, when you posted in TNB that it took 3 hours...
Is it something with interesting structure, or just a string of 100 digits that you find after 3 hours?

@trichoplax sorry, writing the program that finds thsoe 100 digits took 3 hours
the program runs in 0.1 sec

12:11 PM
Did you also prove that it converges?

yes

So it's something that when raised to an arbitrary power mod 10^100, remains the same

the interesting part is that ANY infinite power tower of nonnegative integers converges modulo ANY modulus
@trichoplax no! not an arbitrary power :)

Getting more interesting...

Does it converge because iterated totient function approaches 1?

12:13 PM
@feersum it's a bit more complicated than that (Euler's identity requires coprime base and modulus), but yes that's the idea

12:23 PM
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

@trichoplax I remember that

I looked back through our discussion of it fairly recently because I stumbled upon it - your help was much appreciated :)

12:48 PM
@trichoplax Pollock is jealous=)

@orlp Do you get 70504607010711873915994785970752486126204254460931487727416442742447054942623488‌​90662073691100835297?

@El'endiaStarman Could you also add a feature to plot the velocities instead of the positions? :)

@orlp wait, what? f(x) mod 5 converges, no matter what f(x) is?

@NathanMerrill I'm guessing that was a paraphrasing of the earlier
> ANY infinite power tower of nonnegative integers converges modulo ANY modulus
Otherwise f(x)=x is a counterexample

ah :)

12:56 PM
@El'endiaStarman btw: What method do you use to solve the differential equation?

@trichoplax right, I was really confused

Start from the CMC and read down, otherwise it will make no sense :)
(and it's still pretty unexpected...)

Wait I screwed up
Extended GCD is my least favorite algorithm.

@feersum why? It is the pinnacle of elegance!

@flawr How would you code it?
Can you write it without consulting any references?

1:12 PM
@feersum no

Yeah I know it's wrong now.
@flawr See how ugly this shit is
gcd2=lambda a,b,c=1,d=0,e=0,f=1,g=0,h=0:b and gcd2(b,a%b,d,c-d*g,f,e-f*g,h,a/b)or(c-d*g,e-f*g)
Disgusting.

1:31 PM
That's beautiful. You should make it your desktop background :P

def egcd(a, b):
if a == 0: return (b, 0, 1)
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

Probably screwed up this EGCD stuff again though.

@feersum incorrect
@feersum I could give you some smaller testcases if you want

OK

just tell me what sequence and modulus you want

1:38 PM
How about start at 5, modulo 12345

so 5^6^7^... mod 12345 = 3280

Yes

2^2^2^... mod [1..50] = [0, 0, 1, 0, 1, 4, 2, 0, 7, 6, 9, 4, 3, 2, 1, 0, 1, 16, 5, 16, 16, 20, 6, 16, 11, 16, 7, 16, 25, 16, 2, 0, 31, 18, 16, 16, 9, 24, 16, 16, 18, 16, 4, 20, 16, 6, 17, 16, 23, 36]
@feersum Considering that other people aren't really competing anyway, instead of just throwing me guesses of answers, what's your algorithm so far?

2:34 PM
@orlp All right I've got it passing the test cases now. 84652016759516802078720137732389242391207495585695563324973694981457122091451889‌​77345043177395978241?

@feersum correct!
3

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

def f0(base, mod, succ=1 .__add__):
if mod == 1: return 0
cp = ncp = 1
for b,x in factorint(mod).iteritems():
if gcd(b, base) == 1:
cp *= b**x
else:
ncp *= b**x
p, q = gcd2(cp, ncp)
assert p*cp + q*ncp == 1
return pow(base, f0(succ(base), totient(cp), succ), cp) * q*ncp % mod
I was thinking it must be wrong when it only takes 4 iterations, lol
Somehow I was convinced it should be an epic calculation recursing hundreds of times, haha

nope, it works really fast ^^
can you explain your algorithm though, it's a bit different than mine

So my Chinese remainder thing has only 2 parts.

cp is all coprime prime factors and bcp all common factors

2:41 PM
It finds what the value should be modulo the part of the modulus that is coprime to base is (cp).
And modulo ncp it should be 0.

eh that's an assumption only correct in this particular instance, but I guess
you could have a 1 or a 0 somewhere, terminating the power tower

@flawr Technically, that's sorta what the colors do. I could try though.

@orlp I wasn't trying to make it work for the general case but I also don't see why it fails. Example?

@flawr Euler integration.

@feersum see point 3 in my algorithm
anyway I gotta go now, we'll talk more later if you want to

2:45 PM
That point is pretty big, what part do you mean?

consider p as base with p^3 as mod
if the tower above it is bigger than 3
yes, that's always 0

Oh right.

but you could have a tower above it that quickly ends in an 0 or 1

I assume that the number is always infinitely large, yes.

my answer is for arbitrary a
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?

2:49 PM
I guess 0 or 1 are not allowed now?

eh right, let's not include 0 or 1 (or we just add 2 to each element of each sequence)

4 hours later…
6:44 PM
@feersum let me try=)

7:13 PM
egcd a b
| a < b = let (g,r,s) = egcd b a in (g,r,s)
| b == 0 = (a, 1, 0)
| otherwise = let (g,r,s) = egcd (a-b) b in (g,r,s-r)
assuming nonnegative input

Isn't the let binding pointless in let (g,r,s) = egcd b a in (g,r,s)?

@flawr no modulos, this is really inefficient

@feersum ah sorry, copied the wrong version

Lol I didn't even notice that
Yeah, that's cheating if you do it by subtraction :P

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)

7:17 PM
0

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... @feersum you did not tell me =P but it is way more elegant that way anyway flawr is the subtraction snek: - musssssst sssssubtract @orlp But modulo itself is also quite an expensive operation, isn't it? @flawr not more expensive than division repeated subtraction is O(n) division is O(log n) ish that is for arbitrarily large n Really only log n-ish? 7:21 PM on your computer division for integers is like 30 ish subtractions? Why 30? Doesn't that dependon the size of the integers? when I said 'on your computer' I meant for the processor the processor only has 64-bit words 4 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

division is of complexity O(M(n)), where M is your multiplication algorithm

@orlp interesting
do todays processor have modulo as a built in?

7:24 PM
they have division builtin
which also usually generates the remainder

It's usually a divmod.

but even if it didn't you could easily get the remainder from the division with one multiply
(multiplies are only like 2 subtractions in complexity)
integer division is a bit of an oddball in processorland
the fastest multiplication algorithm (asymptotically) for large w-bit integers is w log (w) 2^log*(w)
where log* is the repeated logarithm
that's better than w log(w) log(log(w))
so for integer n it's O(log(n) log(log(n)) log(log(log(n))))
which is really close to what I said, O(log n) ish

O(forest(n))
@orlp it would actually be quite easy to modify tis function, I just noticed!
Does any of you have experience with Prolog?

@flawr I've done very minor things with it
I won a code golf contest with it :D
43

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

@orlp cool=)
Well I've used it also just a few times
(I actually programmed "quicksort" using it :D)
But I want to explore it further at some point.