Some things I've found about the problem:

E(0)=0
E(1)=1
E(2)=3
E(3)=9
E(4)=33

I've done it. Trust me, it sucks.

Why would you watch anything in a weird order?

>>3730119
Because it's an excuse to do "real-world" math, which I support entirely.

>>3730121
No. If you read the posts, you'll see why this doesn't work. I didn't ask for the number of permutations. E(n) =/= n!, because 3!=6 not 9 and 4!= 24 not 33.

>>3730119
The anime, The Melancholy of Haruhi Suzumiya first aired as a nonlinear narrative in 2006. The dvd release had a different order, and neither of those orders were in chronological order. So it's common practice to watch it in a non chronological order. But that's hardly the point of this problem

Pretty sure the answer is sum(k=0->n, (n-k)!)-1.

OH FUCK YEAH YOU AGAIN.
I'm still working on computer homework though, good luck man.

The slope is n! so the answer is obviously the integral

>>3730157
hmm. Well that does work for n=0 -->4
were did you get that from?

>>3730074 (OP)
14! is the correct answer

anyother questions?

\thread

OP I think I got it.

sum 0 --> n n!

>>3730210
for fucks sake read the thread. 3!=/=9
it's impossible to cover 6 permutations of a 3 episode series in 6 episodes. I didn't ask for the number of permutations, but the most efficient way to watch all of them. The answer isn't 14*14! either.

>>3730216
0! = 0
1! = 1
2! + 1! = 3
3! + 2! + 1! = 9
4! + 3! + 2! +1! = 33

is overlapping allowed?

to use fewer numbers...
would 123451 include 12345 and 23451?

if we're looking for the most efficient system this seems like it would be a great way to reduce the numbers

>>3730216
No. 3!+2!+1!+0!=6+2+1+1=10
However, the sum of the factorials from 1 to n seems to work as this >>3730157 wizard stated

>>3730220
0!=1

>>3730234

Why would you include 0!? That doesn't make sense. Just start from 1.

>>3730229
Yes overlap all you would like. Just as I said: 1,2,3,1,2,1,3,2,1 covers

1,2,3
2,3,1
3,1,2
2,1,3
1,3,2
3,2,1
in that order

>>3730219
>I didn't ask for the number of permutations, but the most efficient way to watch all of them.

WTF are you high? WTF are you talking about?
what do you mean by "most efficient way"?

There are 14! possible ways to watch the entire series (all episodes back to back in various orders). What else is it that you are looking for?

>>3730231
you didn't even get your own problem.
the answer is not 14!, but rather 14*14!, because you are asking for the number of episodes you would need to watch.

sage

>>3730234
You're right so its
sum -1-->n n!

>>3730190
Brute force and SWAG. Currently working on the algorithm of solving to get a definite answer.

>>3730243
yes congratulations, there are 14! possible ways. Now tell the best way to watch all those permutations. Overlapping is allowed.

>>3730245
That's only true if you don't allow overlapping. for fucks sake read the damn thread. You were the slow kid in math class weren't you? several anon's understand it and possibly have even solved it for all n.

>>3730256
>>3730246
This is a definite answer, I'm 99% positive.

>>3730243
>14! unique ways to watch the entire series

I don't have any idea what OP is looking for either.

And the endless 8 counts as a single episode, right?

>>3730256
You sir are a wizard. I'm trying to solve it for n=5, but there are 24 permutations to consider, so it takes awhile.

>>3730264
14 original episodes

>>3730157
>>3730266

Different Anon here. I got the same answer. A lot of people seriously don't get the question, though.

>>3730262
www.rif.org

>>3730264
I was thinking about doing this problem with E8, but it would have just turned into trolling about how every episode is the same

>>3730266
if I'm right the answer should be 154

>>3730275

E8 pissed me off. Mostly because I didn't know what I was getting into, and after two episodes you could see what the problem was.

It was only afterwards that I realised you're supposed to watch them inbetween episodes of the original series.

>>3730276
to see the 87 billion permutations?
that's pretty efficient

http://www.wolframalpha.com/input/?i=14!+*+20+minutes

>>3730258
>"best" way to watch all those permutations

Define "best way". It doesn't appear that you define that here anywhere.

>>3730285
He was referring to n=5 which has only 24 permutations. Read the thread

>>3730286
Holy fuck, my little anon can't be this retarded.

>>3730281
No you aren't. http://en.wikipedia.org/wiki/List_of_The_Melancholy_of_Haruhi_Suzumiya_episodes#2009_version

>>3730301
>>3730256
How's the brute forcing going?

(1,2,3,4,5)
(1,2,3,5,4)
(1,2,4,5,3)
(1,2,4,3,5)
(1,2,5,3,4)
(1,2,5,4,3)
(1,3,2,4,5)
(1,3,4,5,2)
(1,3,5,2,4)
(1,3,5,4,2)
(1,3,2,5,4)
(1,3,4,2,5)
(1,4,2,3,5)
(1,4,5,2,3)
(1,4,3,5,2)
(1,4,5,3,2)
(1,4,2,5,3)
(1,4,3,2,5)
(1,5,2,3,4)
(1,5,4,2,3)
(1,5,3,4,2)
(1,5,4,3,2)
(1,5,2,4,3)
(1,5,3,2,4)
Ok I'm going to follow this list of permutations. starting at the top. This is the most autistic thing I've done all summer.

how does 5 only have 24 permutations? shouldn't it be 120?

>>3730258
what do you expect when you use a common troll image

anyway, I found an upper bound of (n-1)!(2n - 1), which gives 10 for n=3 and 42 for n=4

also, it think theres a lower bound of (n-1)!(2n-1) - (n-1)!*(n-2)

may I ask what technique you used to find the n=4 order?

>>3730326
I think hes been doing them all manually

what is it for 4? I'm looking for patterns and I need more than the answers for 2 and 3 to do it

>>3730336
read >>3730089

>>3730317
oh shit your right.
I meant the number of cycle groups.

>>3730326
cycle groups
for n=4 there are 6 groups:
(1,2,3,4)
(1,4,2,3)
(1,3,4,2)
(1,4,3,2)
(1,2,4,3)
(1,3,2,4)

These groups determine ordering. i.e. for the group (1,3,2,4), after 1 you go to 3, then 2, etc. until 4 sends you back to 1. Each of these 6 groups cover 4 permutations. That way, you can keep track of 24 permutations in 6 groups.

So after I wrote these down, I started with that first group, and exhausted all of its permutations. then chose the group that best overlapped.

>>3730301
assuming you start with esp. 1.. lawl how can you now esp. is really the start? stick the problem in OP's pic. it's not retarded.

if you start with one there is 105 ways
http://www.wolframalpha.com/input/?i=sum+of++1%2C+2%2C+3%2C+4%2C+5%2C+6%2C+7%2C+8%2C+9%2C+10%2C+11%2
C+12%2C+13%2C+14

if I'm retarded then explain why.. you buttmad?

>>3730339
ok, i think you haven't really proven the answer though - its possible that by making what seems like a suboptimal choice, it ends up better later on, so you'd have to prove that isn't the case

14 * 14!

according to the problem posted by OP -- don't know why he's bitching about this not being the correct answer

Each sequence is a palindrome also:
For n=4 the order is
1,2,3,4,1,2,3,1,4,2,3,1,2,4,3,1, 2 , 1,3,4,2,1,3,2,4,1,3,2,1,4,3,2,1 which is 33 entries.

God damn it is taking a while to get the one for n=5

>>3730422
The answer is the LEAST number of episodes.
The correct method involves over lapping the permutations.

For example, if n=3, there are 6 permutations right?
well you can overlap those so that your sequence is only 9 episodes long, not 3*3!=18.

1,2,3,1,2,1,3,2,1 contains all 6 permutations.

>>3730220
You are mistaken!
0!=1

My guess:
(14!)!

Captcha: Biophys yAccou

>>3730366
Yeah I know that's the bitch of the problem. I have by no means proved it or anywhere close to a proof. Clearly the best solution will contain the most amount of overlap. in the case of n=4, different groups can overlap by 2 entries at most. i.e. (1,2,3,4) and (1,3,4,2) overlap at (3,4)
So you want to play this up as much as possible.
But understanding completely how it works is hard.

That said, anon's answer of Sum (n-k)!, k=0 to n seems correct, because it works for the first 4 entries.

>>3730459
read
>>3730246

my guess:

(14!)! (without overlapping)

The function (n!)! grows way too fucking fast.

>>3730496
I'm telling you its
Pni=À1n! 

>>3730461
>>3730469
(14!)! Can't be right. The maximum answer would be to explicitly watch each order possible. If you did that, there are 14! permutations that the 14 episodes could be arranged in, and 14 episodes per permutation. Therefore 14(14!) is the largest solution that successfully watches every order possible. I don't really know how to go about finding the minimum, though.

>>3730514
That isn't (n!)!

And yes, you're correct. This sum has been stated many times ITT. But that isn't a proof. It's just a function that works with the currently found solutions for n=0,1,2,3,4. Right now, I'm looking to see why that works.

bumping because I got an idea

>>3730597
I think he was explaining that (n!)! wasn't relevant.
And how did you pull n! out in the second step?

>>3730514
>>3730597
Where did this i starts at -1 come from?
You do realize that negative factorials are generalized with the gamma function, and -1 is a pole (infinity) of the factorial taken this way...

>>3730611
Umm, because it doesn't depend on the index of the summation.
He probably meant something like this:
Pni=À1i! 
Even though (À1)!  is not really defined...

And that's not even (n!)! , soooo I really have no idea what he was getting at.

I'd do it. Specially if its something depressing. Like Elfen Lied.

>>3730651
But (-1)!=undefined.
But I figured out what I got hung up on... I was thinking

Xni=À1i! 

lol. But the index isn't called by the factorial sum. Which is also why he can pull it out and it all makes sense now.

for n=1,
you have 1, so 1 occurs once
E= 1=1, 1! = 1

for n=2, you have 1-2-1
1 occurs twice and 2 occurs once
E=2+1=3 or 2!+1! = 3

for n=3,
you have 1,2,3,1,2,1,3,2,1
1 occurs 4 times
2 occurs 3 times
3 occurs 2 times
E=4+3+2=9 or 3! + 2! + 1! =9

For n=4
1-2-3-4-1-2-3-1-4-2-3-1-2-4-3-1-2-1-3-4-2-1-3-2-4-1-3-2-1-4-3-2-1 (sooo fun to do, ty OP)
1 occurs 10 times
2 occurs 9 times
3 occurs 8 times
4 occurs 6 times
E=10+9+8+6=33 or 4! + 3! + 2! +1! = 33
Factorials seems to be the answer.
So, E = 14! + 13! +12! + 11! + 10! + 9! + 8! + 7! + 6! + 5! + 4! +3! +2! +1!
= 9.3928268313 x 10^10 episodes

So this function we're using:

Xni=À1n!=n!(n+2) 

(shown by >>3730597)
It can't be right... There are 14! permutations that the 14 episodes could be arranged in, and 14 episodes per permutation. So the maximum answer is 14(14!).
This supposed function for the minimum gives 16(14!) for the *minimum*--but that's larger than the demonstrated maximum bound.

>>3730675
Another way of looking at it is:
(14P14) + (13P13) + (12P12) + (11P11) + (10P10) + (9P9) + (8P8) + (7P7) + (6P6) + (5P5) + (4P4) + (3P3) + (2P2) + (1P1)

>>3730675
I believe this gentleman wins. How do we know that those are the most efficient watching orders, though?

>>3730675
Yeah, it does seem to be the sum of factorials.

Note the way OP was doing n=4 with cycles. If you look at it, the cycles were, in order...
(1234) (1423) (1243)
then
(1342) (1324) (1432)

Basically, the important thing to notice is that in each "section" of three, the 4 moves forwards by one spot with wraparounds.

Now, if you take out the four, you can see that there is a larger iteration of (123) -> (132)

Now, say we had n=6.
The first 5 cycles you go through would be
(123456) (162345) (126345) (123645) (123465)

then you would do a larger, iteration in (12345) (15234) (12534) (12354)

then, after those four larger iterations, you do even bigger iterations through (1234) -> (1423) -> (1243), and finally iterate through (123)->(132)

>>3730671
If you leave it as \sum_{i=1}^{n} n! that works too as long as n=/=0

>>3730675
yeah, it does seem to involve the sum of factorials. But the the thing I can't figure out is why. Also as someone else brought up, how do we prove this is the most efficient method? I had a lot of fun too with n=3 and n=4, but n=5 is a real bastard. Figuring out which cycle group to pick becomes difficult. And don't get me started on how to write a legit algorithm. This problem doesn't look solvable in polynomial time, with the current methods, and furthermore, how the hell do we verify the solution?

Another thing is, why are the solutions all palindromes?

>>3730697
He took n! out of a sum. You can't do that.

>>3730706
because nPn=n!

>>3730719
We don't. This sum has been around since post >>3730157
But that was just a brute force.
Nobody has produced the sequence for n=5 or shown why or what the we are actually doing.

I'm thinking about an actual proof, but its hard.

>>3730721
That is a very good observation!

>>3730727
The palindromes make sense. If you can get half of it in the most efficient way, then the other half will be that same method backwards.

>>3730721
This is a completely non-rigourous proof of why it should be approximately sum(i!)

my lower bound from earlier (revised slightly) is (n-1)!(2n-1) - ((n-1)!-1)*(n-2) or, more simply, (n+1)(n-1)! - n + 2

The upper bound, (n-1)!(2n-1) was gotten from noting that there are (n-1) possible orders (with wraparounds) and that you can get every order by doing one group of (2n-1) numbers for each order.
For example, the group for the order (1234) would be 1234123, which gets every possible starting point in that cyclic group.

Then, noting that each group after the first can use at most (n-2) of the previous group while still being unique, you can subtract (number combinations that can use stuff from before) * (n-2) from the upper bound to get the lower bound (using this method)

>>3730719
As I was doing n=4,
I noticed that when I went through all 24 permutations, The greater the batch of successive permutations, the better the result. I got 4, 4, 4, 4, 4, 4 as the number of permutations before I had to go an extra number deep. Thats 5 changes. If you can reduce the number of changes, it would reduce your episodes watched. At one point I had to go 3 numbers deep. You can test it out with n=3 in an exhaustive approach. I dont think anyone would ever want to do 4.

>>3730721
Ok I've been working through n=5. You sir are a wizard, think I understand how the algorithm works:
You start with 1.
Follow
(1,2,3,4,5) 8 times
(1,5,2,3,4) 6 times
(1,2,5,3,4) 6 times
(1,2,3,5,4) 6 times
the 5 is moving forward, within the subset (2,3,4,5)

But I don't know which one to go to next. Since we've set up the rule of greatest overlap, now we need a permutation that has (2,3).

(1,4,2,3,5)
(1,4,5,2,3)
(1,5,4,2,3)
which is 3 choices. 2 of those cycle groups will make us fuckup

>>3730750
Now, I'm basically taking that lower bound and adding approximately what would be necessary to make it the actual value needed.

Note that with n=4, when you do the bigger iteration (123)->(132), you can only use ONE digit from the previous group (and then, of course, you can go back to using two again during the small iterations)

More generally, you can only use (n-3) numbers from the previous group when you do the second level iteration.
Now, for the super-non-rigourous part:
I assume that, for the third level iterations, you can only use (n-4), for the fourth level you can only use (n-5), etc.

It is clear that there is 1 largest iteration, 2 next level iterations in each largest iteration 3 next level iterations in each of THOSE iterations, etc

what this means is that, total, there are (n-2)!-1 total iterations (each adding 1 to the lower bound), (n-3)!-1 level 2 iterations (each of which was counted in the previous (n-2)!-1 iterations, but each adds a FURTHER 1 to the lower bound.
(n-4)!-1 iterations which add yet another 1, all the way to 2!-1 highest level iterations.

Sorry that this part is so weird to explain, but hopefully it gives enough of an idea that people can verify it themself

>>3730764
What is your sequence for n=4?
If I understand correctly, you're saying its more effecient to stay within cycle groups. i.e. 1,2,3,4,1,2,3 would be considered staying within the group (1,2,3,4) for 6 steps.

Then yes, every time you change cycle groups there is a penalty associated with it. Some switches are better than others, because some switches have more overlap. So the goal is to figure out which group to switch to. In our system, the 1 is always written first to avoid confusion. So for n=4 for example, you follow (1,2,3,4) for six steps. Then you follow (1,4,2,3) for 5 steps and (1,2,4,3) for 5 steps. The important thing here is the order of the groups
(1,2,3,4)
(1,4,2,3)
(1,2,4,3)

notice how the 4 is moving forward

>>3730811
anyway, adding that to the lower bound I get (slightly off unfortunately):
(n+1)(n-1)! - n + 2 + (n-2)!-1 + (n-3)!-1 + (n-4)!-1 ... + (2)!-1
= (n+1)(n-1)! - n + 2 - (n-3) + (n-2)! + (n-3)! + (n-4)!... +2!
= n! + (n-1)! +(n-2)! + (n-3)! ... + 2! ... -2n + 5

Ok, so I made some mistakes somewhere, but give me a break, I don't even have paper on me.

http://pastebin.com/MpLgf2Rt

Okay, I've written some code that can find an appropriate order, and it agrees with the sum-of-factorials formula as far as I've been able to test, which is up to n=8 so far. Still no proof that it always agrees with the formula, or that it's optimal, though.

>>3730829
ohhhh ok,
its supposed to be(n+1)(n-1)! + n - 2 instead of (n+1)(n-1)! - n + 2 for the lower bound, so the two n terms cancel out and I get the correct sum.
COMPLETE MOTHERFUCKER
and goddam I stayed up too late trying this

>>3730878
Great work mate. I can't read python, can you try to explain how the algorithm works?

>>3730914
nice. thanks though. I've been trying to work on this problem for a few days now.

>>3730928
It just goes down the list, and at each point tries to make a new permutation starting from where it's at. If it can't, it advances, and tries to make a permutation there.

e.g.

start at the start
*
we can make the new permutation 123
* 1 2 3
advance
1 * 2 3
we can make 231
1 * 2 3 1
advance
1 2 * 3 1
we can make 312
1 2 * 3 1 2
advance
1 2 3 * 1 2
cannot make a new permutation, advance
1 2 3 1 * 2
we can now make 213
1 2 3 1 * 2 1 3
and so on...

>>3730914
wait why would you add the lower bound to the upper bound. I've tried reading through your posts, but I think I'm too tired. I'll make a thread mark II tomorrow around midnight. Holy fuck this is not simple

>>3730944
Ok I see. But how do you make sure it doesn't fuck up?

By that I mean, in the first half of n=4, as explained
>>3730721
it is obvious which permutations to pick.
but at the midpoint, there is a place where you have the option of making two different permutations. If you choose the wrong one, it becomes incredibly inefficient later on:
The first half is
1,2,3,4,1,2,3,1,4, 2,3,1,2,4,3,1,2
by using the method described in the post
however, you MUST use (1342) for the next one.
If you don't, you'll encounter problems:

if you use (1432) for six steps, you get
1,4,3,2,1,4
and then there is no way to over lap the 1,4 with the remaining 2 groups.

but if you use (1342) for 6 steps, you get
1,3,4,2,1,3
and that 1,3 overlaps well with (1324)

To provide some explanation for sum(k=1:n,k!), for the rotation method that's been used, taking the nth previous number allows for n permutations, the n-1th allows n-1 of those n-length permutations, the n-2nd number allows n-2 sets of those [however long that is] permutations, etc. So in order to cover all n! permutations you need n! sets of nth previous numbers, n!/(n-1)-1 (don't need for the first set) sets of n-1th previous numbers, n!/(n-1)/(n-2)-1 sets of n-2nd numbers, etc plus n-1 numbers to start with before you get any sequences. This gives you n-1 + n! + sum(k=0:n-1, n!-1) = sum(k=0:n, n!) +n-1-n = sum(k=0:n,n!)-1 = sum(k=1:n,n!).

this entire thread looks like a giant troll attempt ...

http://math.stackexchange.com/questions/15510/what-is-the-shortest-string-that-contains-all-permutat
ions-of-an-alphabet

Concoct a proof and submit it to the arXiv. Otherwise fuck off with this because it's about as useful as discussing the Goldbach Conjecture.

Ok i had a good explanation but forgot the fucking captcha, google factorial calculator then type in 14!

basically it's just 14x13x12x11x10x9x8x7x6x5x4x3x2x1 = all possible permutaions.

>>3731602
so much worse than atheist-trolling, evolution debate, 1=.999... trolling, and singularity bullshit amirite?

>>3730979
I got lucky. And worse, the way the program behaves at those features was determined by the way my Python implementation iterated over a set. So I've rewritten the code so it doesn't depend on implementation details:

http://pastebin.com/DNTWxwR1

The program still appears to work. And now what it does in the situation you describe is well-specified; it always picks the first permutation in dictionary order. That is, at the point

12341231423124312

it has the options

2134
2413
2143

In dictionary order these options are:

2134
2143
2413

so it will choose 2134. This way of making the choice seems to work, but I don't know why.

>>3731602
From that link:
>I thought of this problem while reading a open problem on shortest supersequence of all permutations.
The supersequence problem that's been worked on by several mathematicians already is a different problem. Under those rules, for example, 1231231 contains all permutations because they don't have to be embedded consecutively:
123****
*231***
**312**
**3*2*1
*2*1*3*
1*3*2**
So there's no reason to think OP's problem won't be solvable by someone here. And in fact, I think we're pretty close already.