« first day (94 days earlier)   

1:15 AM
@trichoplax I think that the fact that 4 * 6 > 4 or 6 is the base case for the induction.
 
 
12 hours later…
1:27 PM
I'm getting really hype for my summer research gig. Still waiting on actual project info, but they finally got back to me regarding transportation and housing.
Also found out who the 9 other admitted students are, and am feeling intimidated.... they're from Berkeley, Rice, Brown, etc.
 
1:54 PM
I'm sure you'll have a great time nonetheless.
 
2:15 PM
question for you guys: Of the games you've played, which has had the best modding priority system?
Like, in Skyrim, its absolutely terrible: its based off of the order the player puts the mods
In Factorio, it's definitely better: you can define your dependencies, dependencies are ordered, and then 3 files are called: data.lua, then data-updates.lua, then data-final-fixes.lua. That said, the purpose of the last two files is to update data from mods that you didn't define a dependency on, which means that its basically a priority system, so everybody puts their stuff in data-final-fixes, which makes data-updates basically useless
but I'm struggling to come up with a better way
 
2:40 PM
I haven't played any games with modding systems (well, more accurately, I don't play with mods).
'cause on second thought, I've played Minecraft and Halo: Combat Evolved, and those definitely had mods galore.
 
3:02 PM
@NathanMerrill Bukkit's decent since every hook has a set priority, and there's set conventions for what priority to use for the most common situations
But it's more a programmer thing and less a user thing. I would like a system that let the user control that maybe
 
@NathanMerrill what's wrong with this, from a user standpoint?
 
3:30 PM
Does anyone know if there are more terms in oeis.org/A188284? Or is there a finite number?
I ran this program for 4 million values.
and I haven't found more.
 
@mbomb007 "Finite sequence" implies the latter, though I see there isn't a proof.
 
There appears to be a proof referenced from oeis.org/A173447
> Jean-Marie De Koninck, Armel Mercier, 1001 problemes en theorie classique des nombres - Entry 258, p.41. Ellipses, 2004.
 
I think I know why there's a finite number... there exists a number N such that for all n > N, sum of factorials of digits of n is always less than n.
for example... a long enough sequence of 9s will be greater than x * 9!
and so, any number greater than that cutoff point, cannot be part of a cycle
because the only way to get back to the original number, would be to have an even larger number, which you can't get, etc.
 
So what is the value of N, I wonder?
The minimum value, that is
 
10 ^ x - 1 = x * 9! for a sequence of all 9s. I think this gives x= 6.36... which corresponds to 999999 being a lower bound and 9999999 being an upper bound.
 
To be more mathematically rigorous, once we find the cutoff such that f(n) < n, this doesn't entirely give the cutoff value for the sequence, since there might be an m<n such that f(m) = n. Meaning that there's still ways for a cycle to include numbers above the cutoff if they manage to jump up there... but you would have already found those cycles by searching the numbers below the cutoff.
The main point is that no cycle exists which only uses numbers above the cutoff.
 
@PhiNotPi Don't feel intimidated, I bet none of them are as proficient in code-golf as you are.
 
@flawr should I golf all my code?
I think they use Matlab, so I guess they won't mind if I use MATL instead?
 
@trichoplax Composite means that you have more than one prime factor (including multiplicities), you could already say that 2^n are all composite for n>1. But this was actually not really a serious proof, it was just about the punchline "don't add one":)
@PhiNotPi sure:)
What kind of project is that?
 
@PhiNotPi What's the topic/field of research?
 
4:00 PM
The field is computational neuroscience.
 
Oooh, neat.
 
I actually do not have the impression that people from "top" universities are any better in their subject than others (well I can only speak for math) but it is rather the financial means an linked with that the reputation that distinguishes the universities.
So don't worry too much about these guys:)
 
4:46 PM
what's going on here?
 
@LeakyNun this chat is a bit higher content/noise ratio than the 19th byte
general math and intellectual interests are also ontopic here
 
sounds fun
 
security through obscurity
 
@LeakyNun a couple days ago we had an interesting problem
with a very interesting solution I found
before you scroll up and cheat, see if you can solve it
 
what is the problem?
 
4:47 PM
I give you a n-sided dice
and in this case we can have 1 or 3 or any amount of sides
and I tell you to throw k times
and everytime you throw you must use the result as your next size of dice
so if you start with 6
and you roll a 3
the next dice you throw has size 3
so we have f(n, k, x), which is the probability that if you start with a n-sided dice and you do k throws, what is the chance you end up at x?
 
:o
 
the challenge is of course, what is f?
 
so let's say n=6
 
infinite markov chain?
 
after 1 roll, the probabilities are 1,2,3,4,5,6
after 2 rolls, the probabilities are 1,(1,2)/2,(1,2,3)/3,(1,2,3,4)/4,(1,2,3,4,5)/5,(1,2,3,4,5,6)/6 [forgive my bad notation]
 
4:52 PM
@PhiNotPi nothing is infinite here
@LeakyNun something like that, ye
 
so f(6,2,1) = (1+1/2+1/3+1/4+1/5+1/6)/6
I don't think there's a nice formula for this
 
@LeakyNun why not? (and define nice)
 
well, it's the harmonic series
and we just denote H_6/6 as the above
 
@LeakyNun I believe this is correct, yes
@LeakyNun can you make a recursive formula?
as a start
 
I assume you've already worked this through?
 
4:55 PM
@PhiNotPi I have found a solution, yes
with some help of other chatters here
the original problem is by martin
 
@orlp well, f(n,k,x) = sum[r=x...n] f(n,k-1,r)/r
 
@LeakyNun eh the right idea but not the right parameters I believe
n should be reduced, not x
 
eh...
i have no intuition how n links to n-1
 
@LeakyNun no I mean
x is your target
your end result
it shouldn't change in the recursion
 
let me try
 
5:01 PM
@LeakyNun hint: in your current recursive solution you only ever throw n-sided dice
n never gets smaller
 
I really don't see how the case for n is related to the case for n-1
 
@LeakyNun I never said you had to reduce using n-1
what does r represent?
 
the number on the last step
wait
 
f(n,k,x) = 1/n * sum[i=x..n] f(i,k-1,x) right?
 
f(n,k,x) = sum[r=x...n] f(n,k-1,r)/r
f(n,k,x+1) = sum[r=x+1...n] f(n,k-1,r)/r
f(n,k,x) - f(n,k,x+1) = f(n,k-1,x)/x
@PhiNotPi I don't think so
 
5:05 PM
@LeakyNun yes
and the number of the last step has influence on the dice size, right?
so perhaps that should go where n is? wink wink
 
yes
 
because n is the dice size
 
I already included that influence in the /r
 
@LeakyNun no, that is the chance the dice hits x in that roll
f(n, k, x) = sum[r=x..n] f(r, k-1, x) / r
 
why /r there and not /n
the chance of each of the chosen intermediate values should be equal
 
5:08 PM
heh, it's out of my intuition
 
I have f(n,k,x) = sum[r=x..n] f(r,k-1,x) / n = sum[r=x..n] f(n,k-1,r) / r
and so now it's a question of which way is easier to tackle the recurrence
 
I'm a bit confused myself now
oh no
I get it again
@PhiNotPi @LeakyNun look at this diagram
let's say we're at k=4 for x = 2
then our previous throw could've been 2 or 3 (but not 1)
r is our previous throw
if r == 2 then we had a 1/2 chance of being chosen
if r == 3 then we had a chance of 1/3 being chosen
 
there's two ways to frame the recurrence: top-down or bottom-up... one method uses sum of f(n,1,r)*f(r,k-1,x) and the other uses f(n,k-1,r)*f(r,1,x)
although TBH I don't know what to do next once we have the sum
 
I mean I'm still a bit confused
why there is no 1/n
 
5:24 PM
there is a 1/n... if you use the first approach. There is a 1/r if you use the second.
 
yeah I mean in the second
oh yeah it's top down
ah yeah I'm no loger confused
 
@orlp you're confused as to whether you're confused
 
anyway
that wasn't the part that fascinated me
f(n, k, x) = sum[r=x..n] f(n,k-1,r) / r is the recurrence I used
@LeakyNun alright
now we can make a vector
where x goes from 1..n
[f(n, k, 1), f(n, k, 2), f(n, k, 3), ...]
ill call that vector f(n, k)
@LeakyNun @PhiNotPi got that?
 
go on
 
now we can write the recurrence
like this
A is an upper diagonal matrix where each row is the harmonic series
you can mentally do the matrix-vector multiplication to verify this
 
5:31 PM
I don't get it
 
do you know how vector-matrix multiplication works?
 
I do
oh never mind, continue
 
yeah?
ok
but now the interesting part is that we can simply write f(n, k) = A^k v
where v is a vector [0, 0, ..., 0, 1]
 
agreed
 
(multiplying a matrix by v is the same as choosing the last column)
(and if we choose the last column for k = 1 we see that it's correct 1/n everywhere)
so now we can already reasonably efficiently compute f(n, k)
just one n-by-n matrix exponentiation
but matrix exponentiation has an interesting optimization
if you can write your matrix A as A = P H P^-1 where H is a diagonal matrix
then A^k = (P H P^-1)^k = P H P^-1 P H P^-1 ... = P H^k P^-1
because all the P^-1 P in the middle cancel
agreed?
 
5:37 PM
I know what diagonalization is.
 
alright
and H^k is very easy to compute
@LeakyNun are you familiar with eigenvalues/eigenvectors?
 
@orlp to a certain extent.
 
using the eigenvalues and eigenvectors of a matrix you can find the P and H required
so that A = P H P^-1
it turns out that H is just the eigenvalues on the diagonal
and since A has distinct elements on the diagonal, the eigenvalues simply is the diagonal
 
I know what diagonalization is.
 
@LeakyNun any guess what the eigenvectors of A is?
 
5:39 PM
@orlp that's nice
@orlp [1;0;0;...;0]
 
@LeakyNun nope :P
 
how is it not?
 
@LeakyNun wait
I meant all eigenvectors
not just one
[1, 0, ..., 0] is indeed one eigenvector
but to make the diagonalization we need one eigenvector for each eigenvalue
 
I know
 
do you see a pattern?
 
5:43 PM
@orlp i do
the pascal triangle aka binomial coefficients
 
yes
with some negative some positive
@LeakyNun but those have a nice formula!
 
@orlp are you referring to the expansion of (x-1)^n?
 
@LeakyNun pascal's triangle is just n choose k
so we have this
eh if you click on it it's not blurry
 
alright
 
and that can be simplfied
@LeakyNun tbh when I found this I was just looking for an efficient computation method, and didn't really expect it to give a closed formula
but then suddenly pop pascal's triangle
 
5:47 PM
i see
 
there's something profoundly cool about 'the eigenvectors of the harmonic series form pascal's triangle'
I can't give an intuitive explanation for that or the final formula though
 
I'm back (kinda)
Yeah, the matrix approach was kinda what I was thinking of when I said markov chains, they're like the transition matrix.
 
 
1 hour later…
7:00 PM
@orlp Does this distribution have a name?
 
@flawr I dno
 
strange name for a probability distribution :)
 

« first day (94 days earlier)