Primes and Squares

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

trichoplax

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

orlp

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

trichoplax

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?

orlp

@trichoplax sorry, writing the program that finds thsoe 100 digits took 3 hours

the program runs in 0.1 sec

feersum

12:11 PM

Did you also prove that it converges?

orlp

yes

trichoplax

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

orlp

the interesting part is that ANY infinite power tower of nonnegative integers converges modulo ANY modulus

@trichoplax no! not an arbitrary power :)

trichoplax

Getting more interesting...

feersum

Does it converge because iterated totient function approaches 1?

orlp

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

orlp

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

PhiNotPi

@trichoplax I remember that

trichoplax

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

flawr

12:48 PM

@trichoplax Pollock is jealous=)

feersum

@orlp Do you get 70504607010711873915994785970752486126204254460931487727416442742447054942623488‌90662073691100835297?

flawr

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

Nathan Merrill

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

trichoplax

@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

Nathan Merrill

ah :)

flawr

12:56 PM

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

Nathan Merrill

@trichoplax right, I was really confused

trichoplax

Start from the CMC and read down, otherwise it will make no sense :)

(and it's still pretty unexpected...)

feersum

Wait I screwed up

Extended GCD is my least favorite algorithm.

flawr

@feersum why? It is the pinnacle of elegance!

feersum

@flawr How would you code it?

Can you write it without consulting any references?

orlp

1:12 PM

@feersum no

feersum

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.

trichoplax

1:31 PM

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

orlp

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)

feersum

@orlp How about 94211747148730366324835490255294514631382640605479164562415390543278812756363402‌80515149766028926721

Probably screwed up this EGCD stuff again though.

The thing that sucks about this problem is you can't test against brute forced examples.

orlp

@feersum incorrect

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

feersum

OK

orlp

just tell me what sequence and modulus you want

feersum

1:38 PM

How about start at 5, modulo 12345

orlp

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

feersum

Yes

orlp

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?

feersum

2:34 PM

@orlp All right I've got it passing the test cases now. 84652016759516802078720137732389242391207495585695563324973694981457122091451889‌77345043177395978241?

orlp

@feersum correct!

3

A: Finding the last two digits of a number

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

feersum

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

orlp

nope, it works really fast ^^

can you explain your algorithm though, it's a bit different than mine

feersum

So my Chinese remainder thing has only 2 parts.

orlp

cp is all coprime prime factors and bcp all common factors

feersum

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.

orlp

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

El'endia Starman

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

feersum

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

El'endia Starman

@flawr Euler integration.

orlp

@feersum see point 3 in my algorithm

anyway I gotta go now, we'll talk more later if you want to

feersum

2:45 PM

That point is pretty big, what part do you mean?

orlp

consider p as base with p^3 as mod

if the tower above it is bigger than 3

yes, that's always 0

feersum

Oh right.

orlp

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

feersum

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

orlp

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?

feersum

2:49 PM

I guess 0 or 1 are not allowed now?

orlp

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

flawr

6:44 PM

@feersum let me try=)

flawr

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

(assuming you use haskell=)

feersum

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

orlp

@flawr no modulos, this is really inefficient

flawr

@feersum ah sorry, copied the wrong version

feersum

Lol I didn't even notice that

Yeah, that's cheating if you do it by subtraction :P

flawr

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)

orlp

7:17 PM

0

Q: Modular power tower mapping, is it injective?

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

flawr

@feersum you did not tell me =P

but it is way more elegant that way anyway

orlp

flawr is the subtraction snek: -

flawr

musssssst sssssubtract

@orlp But modulo itself is also quite an expensive operation, isn't it?

orlp

@flawr not more expensive than division

repeated subtraction is O(n)

division is O(log n) ish

that is for arbitrarily large n

flawr

Really only log n-ish?

orlp

7:21 PM

on your computer division for integers is like 30 ish subtractions?

flawr

Why 30? Doesn't that dependon the size of the integers?

orlp

when I said 'on your computer' I meant for the processor

the processor only has 64-bit words

4

Q: Complexity of division

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

algorithms complexity-theory asymptotics arithmetic

flawr

@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

orlp

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

flawr

@orlp interesting

do todays processor have modulo as a built in?

orlp

7:24 PM

they have division builtin

which also usually generates the remainder

feersum

It's usually a divmod.

orlp

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

flawr

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?

orlp

@flawr I've done very minor things with it

I won a code golf contest with it :D

43

A: Should we be friends?

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

flawr

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

Transcript for