@trichoplax I think that the fact that 4 * 6 > 4 or 6 is the base case for the induction.

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.

I'm sure you'll have a great time nonetheless.

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

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.

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

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?

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

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?

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]

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

@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

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

@PhiNotPi I don't think so

@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

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

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

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?

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?

@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

I know

@LeakyNun m.wolframalpha.com/input/…

do you see a pattern?

@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

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.

@orlp Does this distribution have a name?

@flawr I dno

strange name for a probability distribution :)