/sci/ - Science & Math

>>10089701
Don't drag my girl Christina into this

>>10089701
>93,924,230,411 episodes

14*13*12*11*10*9*8*7*6*5*4*3*2=87,178,291,200 episodes

Why am I so retarded?

>>10089745
That’s the number of orderings, not the number of episodes you’d have to watch.

>>10089701
If I end my first viewing with the 14th episode and then watch the 1st to 13th episode, does that count as a different order?

>>10089795

That actually counts as 14 different orders! Because the runs of different orderings can overlap.

So if you watch 27 episodes in this order: 1, 2, …, 14, 1, 2, …, 13 that counts as all these:

1, 2, …, 14

2, 3, …, 14, 1

3, 4, …, 14, 1, 2

…

14, 1, 2, …, 13

>>10089813
Oh yeah, didn't really consider that. Now I'm embarrassed.
Thanks mate!

>>10089701
196, but I can't be arsed to verify.

>>10089701
Assuming you never repeat any permutation, the answer's 13+ the number of permutations. Problem's showing you can never repeat any permutation.

-1/12, but can't be arsed to verify.

>>10089701

2755?

As a corollary, what if you have two monitors and can therefore watch two episodes simultaneously (so 1 + 2 counts as both a 1-2 element and a 2-1 element)?

Does that just straight up halve the number of episodes you need to watch?

>>10092285
Uhh. Depends on whether or not you split on overlapping runs, I guess. Should be close enough to half, though.

>>10089701
/a/fag here. what do "bounds" mean? Why isn't it just one number?

I figure since for every 14 episode combination as you can place the first episode in the list at the end 13 times until you end up with the original again then instead of n! Combinations it becomes ((2n-1)/n)((n-1)!) for number of elements n?

>>10092479
Bounds begin likes estimations, in several algortihms or combinatorics problems begin too hard calcule perfect solution then research calcule worst/best posible case,perfect solution get between upper bound and low bound like ham in one sandwiches and bounds act like bread or bounds.

upper bounds worst estimation
lower bounds best estimation.

Anon /sci/ make proof for best lower bound for superpermutation problem.

>>10092502
>Anon /sci/ make proof for best knowledge today lower bound for superpermutation problem.

>>10092479
We don't know the exact number, cause that' hard to figure out.
We do know that the answer has to be bigger than some numbers (lower bounds) and smaller than other numbers (upper bounds) though.
If you want some absolutely retarded bounds, here's how you might come up with a few:
Lower bound: In order to watch a new order, you have to watch another episode. Since there are 14! orders you need to watch at least 14! episodes (if we start with 13 and then add an episode to get the first permutation, we actually have a lower bound of 14!+13)
So for n episodes we have the lower bound n! + (n-1)

Upper bound: This is going to be absolutely awful. One way we could watch all the permutations is to literally just watch all of them without worrying about overlaps. There are 14! permutations and each has length 14, so this is 14!*14 episodes.
So for n episodes we have the upper bound n! * n.

You can make both of these better, as anon does in the link for the lower bound.

>>10092490
Yeah but you are forgetting if you place a new episode at the end of a set of 14.

>>10092136
>It's real

>>10092505
Oh, if you wanna see a better upper bound, note that we could take all the "cycles" where we list an order and then list it again (without the very last episode in the order) and this gives us n different permutations. There are (n-1)! such cycles, so a new upper bound would be (n-1)! * (2n-1)
Before we had (n-1)! * n^2, so this new upper bound is better by a factor of about n/2. In our case it's 13! * 27, which is better than 14! * 14 = 13! * 196 by a factor of about 7.

>>10092505
but if you establish a lower bound, doesn't that mean you've demonstrated at least one answer at that lower bound? how could some exact answer end up being larger than a lower bound?

>>10092136
>not a weeb board
>/mg/, /sqt/ and /engi/ threads full of anime
>booette shitposter

>>10089701
The citation will go to those mathematicians in the google group that finessed this proof/or Egan, who will in turn cite the anon /sci/ shitposter. It's not unusual to have proofs come from random blogs or other irreputable sources.

>>10092545
I'd still love to see a >>3751197

>>10089701
Better yet, why don't we try upping the ante?

>>10092835
Problems must be redacted as anime/manga relate.

>>10092842
Chickening out already? Surely you don't want to disappoint sensei...

>>10092842
>on the news today: man solves the Riemann hypothesis. Claims that a picture he saw on an online forum of a "smug anime girl" daring him to do it angered him into getting fired, breaking up with his girlfriend and throwing two years of his life as a NEET into the great mathematical problem.

If you enrolled any random dude into a discrete mathematics class he would be able to come up with that proof by the end of it tbqh
Props to the guy who did it though

>>10092906
https://scholar.google.ca/citations?user=RyV5H_MAAAAJ&hl=en

This guys is N Jonston

>2011
>anime girls and hard math problems on /sci/
>2018
>wojak/pepe mutations posts and crackpot pseudoscience phenotype IQ posting

what went wrong?

ez
>>10092835
I will use the Todd function T(s) to prove RH. The proof will be by
contradiction : assume there is a zero b inside the critical strip but off the critical line. To
prove RH, it is then sufficient to show that the existence of b leads to a contradiction.
Given b, take a = b in 2.1 then, on the rectangle K[a], T is a polynomial of degree k{a}.
Consider the composite function of s, given by
(3.1) F(s) = T{1 + ζ(s + b)} − 1
From its construction, and the hypothesis that ζ(b) = 0, it follows that
3.2 F is analytic at s = 0 and F(0) = 0.
Now take f = g = F in 2.6 and we deduce the identity
3.3 F(s) = 2F(s).
Since C is not of characteristic 2, it follows that F(s) is identically zero. 2.3 ensures that
T is not the zero polynomial and so it is invertible in the field of meromorphic functions of
s. The identity F(s) = 0 then implies the identity ζ(s) = 0. This is clearly not the case and
gives the required contradiction.
This completes the proof of RH

>>10092924
>posting on reddit with your actual name
>posting on reddit at all
>this other twat not understanding what the fuck is a lower bound

>>10092975
> inside the critical strip but off the critical line.
What sort of nigger speak is this?

>>10092975
>t.

>>10092530
no, you only know that the exact answer cannot possibly be lower than the lower bound

>>10089701
https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery

Now math books will talk about haruhi problem and meme "you should be able to solve this"

OP from the original 2011 thread. Is the poster !MnRMOBEIRw from the original thread here? Probably not, but just checking

>>10093054
>and meme "you should be able to solve this"
Please don't let this happen

>>10093435
Fuck your mother!

>>10089701

I haven't read the paper or results or anything, just the problem in the image. But the lower and upper bounds I was able to deduce are the following:

Lower Bound:
((n - 1) * n / 2) + n! - n
Using that, it'll take at least 87,178,291,277 episodes for n = 14.

Upper Bound:
((n - 1) * n / 2) + (n - 1) * (n! - n)
Which guarantees you can do it in under 1,133,317,785,509 episodes for n = 14.

>>10092835
>>10092885
Kek

>>10092970
>phenotype
Don't make me post it

>>10092975
>F(s) = 2F(s)
>1 = 2

>>10093976
just read the paper. Damn, his lowerbound is better lol.

>>10089723
... Isn't that what she's for? The only alternatives are Daru, because goodness knows Okabe ain't gonna do it.

>>10089701
https://gigazine.net/news/20181025-suzumiya-haruhi-superpermutation/?utm_source=dlvr.it&utm_medium=twitter

Japaneses Media Report >>> West media

>>10093988
That's actually a typo, the talk he gave had F(2s) = 2F(s)

>>10089701
>Plus for some reason not everyone thinks /sci/ is a reputable source.
Computer-verifiable version here:
https://github.com/ccd0/superpermutations

>>10092970
Trump and the 2016 election. 4chan got too popular.

>>10093984
do it faggot

>>10089701
about tree fiddy

>>10094329
No, not everything bad is Trump and /pol/'s fault

>>10092970
zoomers

>>10094489
It is in this case.

>>10092988
How else would you phrase it?

>>10092532
/sci/ is the original weeb board.

>>10089701

I'd like to see a custom of people publishing important results anonymously be so that they may be evaluated purely on merit, and so we can stop naming theorems after people. If their work is appreciated maybe they can post Bitcoin addresses for compensation.

>>10094530
all of 4chan is weeb
anyone who says otherwise is a redditor that needs to go back

>>10094661
fame is a good incentive, always has been. it's the reason why awards are a thing in the first place.
i agree with your sentiment though.

>>10094661
people do things because they want to be appreciated and commended for them
also so they can be paid for them and not starve to death

>>10094665
>reddit is bed guys i swear

>>10094685
>>10094680
>>10094661
If your name doesn't get published, there's less chance of you being turned into an anime or manga character in Japan.

Some famous mathematicians have become cute 2D girls in Japanese manga or anime.

>>10092970
Gamergate, anonymous and some other stuff caused flood of new anons that expected 4ch to be like some secret organization

>>10094665
>all of 4chan is weeb
On /v/ you have the odd gookaboo thread, and they hate Japan.

>redditor
I was on digg, and thus never touched that shithole, because I knew what it would become.

>>10094729
I hate Japan, too. But I'm a hopeless anime addict.

>>10094729

You can love parts of Japan and hate others. For example, it's easy to hate certain Japanese video game makers for their navel gazing and inability to function outside of Japan.

>>10094761
>>10094778
Weeb is but another term for Japanophile.
>I hate Japan
Well, then we have established that not "all of 4chan is weeb", which is all I was trying to say.

>>10094781
Can we get back to the problem?

>>10095016
no

>>10089745
14! * 14 would be the absolute worst case without overlap.

>>10095349
Whats the current lower bound? Also equation

>>10095360
The wikia-proof it seems.

>>10095383
And the upper bound is the l(n)=1!+2!+3!...n!
n=14
l(n)=93,928,268,314? Or is it something else?

>>10092530
There's more than one possible ordering that contains all the permutations. The lower-bound just establishes the length of the shortest possible combination.

>>10095671
no it doesn't, see >>10093037

>>10095684
Read the section on minimal length:
www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html

There is no "exact answer," superpermutations can happen in multiple orders, like the L(6) example where they found multiple combinations with a length of 873, but soon discovered there were shorter solutions with a length of 872.

This is why the standard recursive algorithm produces a valid combination, but it's longer than the length given by the new lower-bound algorithm. You can get longer combinations, but the lower-bound is the shortest possible combination.

>>10094489
pol is /v/´s fault as we.
Haruhi theorem would also raise the atention, the best option right now is to remain calma, and avoid doing anything that would get atention.
Also keep /pol/ as a contaiment board.

>>10095773
as well*

>>10095393
There's a better upper bound, 93,924,230,411

>>10089701
This feels really bad. The anon that proved that is probably long gone (archived proof is from 2011) so it's just a matter of time before somebody puts it together that lower and upper bounds are the same. On the other hand it would be a waste for that proof to not become known. I've went through the proof and it feels pretty solid even though i'm compsci, not maths and don't have real mathematic intuition.

>>10094329
It was exactly the opposite. /sci/ developed persistent low-effort trolls who knew just what buttons to push to shit up the board. These were oldfags, not newfags. This was combined with moderation that discouraged creativity and encouraged spamming, and an attitude among many users that 4chan was a place to shitpost, while serious discussion could be had on reddit.

>>10089701
The downside of claiming credit is associating one's real life identity publicly with 4chan. Plus it couldn't be verified, anyway.

>>10096096
They could reveal the tripcode key.

>>10096108
It wasn't posted with a tripcode.

>>10096169
>>10096108
>>10096096
If the mathematician really wants to get in contact with that anonymous poster, the 4chan staff might be able to help.

I know IPs can be dynamic but 4chan staff could trace that particular IP from 2011 to see if he or she made posts under a trip or name either on /sci/ or other boards and if so, perhaps that 2011 anonymous poster may have left his or her email address for posters to contact.

As for the fate of that poster and seeing that proof never posted elsewhere, he or she may not have been a grad student or professional mathematician but an amateur math hobbyist or wanted to go to grad school but couldn't afford it and so gave up his or her hobby for math.

If you want to be more pessimistic as to this anonymous mathematician's fate, then feel free to do so.

I'm just saying 4chan staff/mods should have the ability to narrow down that 2011 anonymous poster and it would be a shame for someone on /sci/ to miss out on a Fields Medal.

>>10096204
>miss out on a Fields Medal
How important do you think this problem is? It's just an interesting open problem that's simple enough to be accessible to non-mathematicians. There are many such problems. You could even take a crack at one yourself if you're interested:
http://www.openproblemgarden.org/

>As for the fate of that poster and seeing that proof never posted elsewhere, he or she may not have been a grad student or professional mathematician but an amateur math hobbyist or wanted to go to grad school but couldn't afford it and so gave up his or her hobby for math.
Or maybe the poster was a grad student in another field. You know, they usually pay you in grad school.

>4chan staff could trace that particular IP from 2011
I certainly hope they don't keep our IPs that long.

>>10096204
>combinatorics
>fields medal
>ever

>>10096204
Moot said they only retain ips for live threads, everything else gets purged
Its long gone

>>10094687
Reddit is cancer. I recently spent several weeks on a sub for a game that /v/ rarely discusses and the memeposting alone was enough to make me want to firebomb a few houses. Think of the most pathetic /b/ tier garbage from 10 years ago and they spam it out like it's the hottest fucking thing. There is a massive cultural difference between r*ddit and most imageboards, let alone 4chan. It's all karmawhoring and virtue signalling. I actually had a faggot try to get me banned for promoting violence for calling him a helicopter dodger.

>>10089701
>I don’t suppose the anon in question would be interested in writing a paper on it?
To be honest, the idea of anon having made a useful contribution that serious mathematicians find too awkward to cite is a much more amusing state of affairs than the actual paper would be. Publishing a paper to cite would ruin the delicious awkwardness, which is almost as sweet to drink as tears.

What does it mean to say that rapists and murderers commit their crimes of their own free will? If this statement means anything, it must be that they could have behaved differently-not on the basis of random influences over which they have no control, but because they, as conscious agents, were free to think and act in other ways.

To say that they were free not to rape and murder is to say that they could have resisted the impulse to do so (or could have avoided such an impulse altogether)-with the universe, including their brains, in precisely the same state it was in at the moment they committed their crimes.

What does /sci/ think of free will?

>>10096466
shut the fuck up

this is so coolllll

>>10092532
>literally an anime girl from an anime game which has become an anime meme in the OP

>>10096332
Did moot make a statement to you under oath? I didn't think so.

moot had zero reason to mention the inner workings of 4chan to you.

He could lie to you without consequence as well.

No important statement not made under oath isn't worth much.

>>10096332
Gookmoot != Moot

>>10096587
2011 was moot era though

>>10096466
Go ask that in the stupid questions thread or make a new thread if you don't think your question is stupid

>>10089701
14. Parameters require each of the data to be watched at least once (14 minimum) but redundant/repeat viewings don't spontaneously generate a 15th, 16th, ... 100000000000th etc discrete episode and the original quantity is preserved (14 maximum).

>in every possible order

There are 14! (87,178,291,200) minimum unique viewing orders, still 14 episodes to be watched.

>>10096706
Congratulations anon, you're very clever. Now fuck off.

>>10089701
>this shit is on ANN
What have you lot done?

https://www.animenewsnetwork.com/interest/2018-10-25/haruhi-helps-crack-a-25-year-old-mathematical-conundrum/.138635

>>10096706
how did you think that would be a good post?

>>10094690
>Some famous mathematicians have become cute 2D girls in Japanese manga or anime
I know it's happened to fighter aces and historical/mythological figures, but I don't think Fate and it's ilk have touched anyone less well-known than Einstein yet.

>>10096463
This.

>>10097573
Archimedes?

>Greg Egan
inspirational book for me

How about the ordering where Helene has been riding the wave of people thinking I was weird ever since she raped me in the ass with a thermometer, causing extreme sharp pain in my side as she rearranged my insides with her tool, when I was a little boy?

Disproof of the Riemann Hypothesis
http://www.vixra.org/abs/1809.0557

I'm more interested in how they stumbled upon it in the first place.

>>10097970
almost certainly it was one of them but they don't want to jeopardize their careers

>>10097984
And waited 7 years just to cite "The Haruhi Problem by Anonymous form 4chan" in the end?

>>10094687
Please go back and never return.

>>10096427
>used a newfag insult to prove how chantard he is
you should kys

Wait
>Haruhi - number of iterations
>Kurisu - number of jumps between iterations
Did I get it right? If yes then it's hilarious in too many ways to count.

>>10097970
>>10097984
>>10098010
https://twitter.com/robinhouston/status/1055511527539818496

Robin Houston: I found a link to it on Nathaniel Johnston’s blog. So the real question is, how did Nathaniel Johnston come across it? And he can’t remember!

http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/#comment-1325839

Nathaniel Johnston is some Canadian mathematician who blogged about this Haruhi problem in 2013 and Robin Houston found it later.

Nathaniel Johnston is not the /sci/ anonymous poster we want though because Robin asked how he stumbled onto the Haruhi proof and Nathaniel can't remember.

>>10098576
Nathaniel Johnston just posted on reddit and judging from his posts, the anonymous /sci/ mathematician is not him.

I'm a brainlet and remember only elementary school math (if even that). I understand after seeing pic in gdoc how to get one short sequence (pic related), but how to you get second and the others when it's 5 numbers and more?
>https://docs.google.com/viewer?a=v&pid=forums&srcid=MTUwMTUxMjExNDk4NTk5NjY5OTkBMDMxNDgwMTA5ODA5OTYyNzcyNDQBVF9leXJHY19Dd0FKATAuMQEBdjI&authuser=0

>>10094701
Are you telling me the secret "Anonymous" group that contacted me is fake? What were all those secret meetings where I had to take my clothes off to prove I wasn't being tracked by the FBI?

>>10098017
Why does your pic have Penn? Reddit sucks his cock all the time, throw him into the bin with the rest.

>>10094329
Orange Man Bad!

>>10100349
>>>/pol/
We're doing math here. Shoo.

>>10092530
No, the lower bound means that you have shown that every sequence shorter than that is *not* the answer.

Ok, /sci/, in the original post, anon defined a function I call [math]\mathcal{K}_n[/math] which takes [math]n[/math] characters from the beginning of the string, reverses them, and moves them to the end. I find if you apply this function [math]m[/math] times, which I will denote as [math]\mathcal{K}_n^m[/math], it will repeat itself. I tested this with a number of strings of sizes from 1 through 25 and each time with [math]n[/math] from 1 to the size of the string.

Figuring out what [math]m[/math] I needed to get the function to return to its origin gave me a table http://mathb.in/28811 where the 0s meant the function was not tested due to being undefined at those points. Can anyone spot a pattern in that table?

>>10100349
>from english_langugage import negative_connotations
>def interaction(string):
>if 'trump' and negative_connotations in string:
>return './epic_4chan_pics/NPC_meme.jpeg'
>else
>return 0

>>10089701
This is for 4
12341231423124312342132413214321
its 32 distance when his theorem says it should be 33+ Am I making a mistake? The permutations are shown in this order (the one on the right is the permutation starting with 1 to help)
1234 1234
2341 1234
3412 1234
4321 1234

2314 1423
3142 1423
1423 1423
4231 1423

3124 1243
1243 1243
2431 1243
4312 1243

3421 1342
4213 1342
2134 1342
1243 1342

2413 1324
4132 1324
1324 1324
3241 1324

1432 1432
4321 1432
3214 1432
2143 1432

>>10100558
never mind im a retard.

>>10100558
>>10100558
ittle typo, it should be
1234 1234
2341 1234
3412 1234
4123 1234
in the first 4 the last one was wrong.

>>10100484

>>10100536
kek

>>10100951
Yeah, I saw that too, but it's not really enough to make a closed-form expression. On the other hand, for the special case of [math]\mathcal{K}_2[/math], I did find a pattern: it's [math]2n[/math] for even [math]n[/math] and [math]n+n^2[/math] for odd [math]n[/math]

I was on this board back in 2011 and still here, I hope the same case is with this anon.

Here's the relation graph for [math]\mathcal{K}_1[/math] and [math]\mathcal{K}_2[/math] for strings of size 7. I know it's not really legible, but it's strongly connected, and is a Hamiltonian graph.

>>10096580
He made the statement under oath when he was on court

I THINK I might have found a new, tighter upper bound by considering a variant of [math]\mathcal{K}[/math] I'll call [math]\Delta\mathcal{K}[/math] which returns just the last [math]n[/math] characters of the corresponding [math]\mathcal{K}_n[/math]. By appending those character to the string you've viewed (which for clarity I'm gonna start calling "the tape"), then at each step, the [math]|\Sigma|[/math]-suffix of the tape is a permutation of the string [math]\Sigma[/math].

Since we've said that the union of relation graphs of [math]\mathcal{K}_1[/math] and [math]\mathcal{K}_2[/math] is connected and Hamiltonian, but neither of the component graphs are, then at the very worst for an input string of length [math]m=|\Sigma|[/math], you'd need to start with a tape of length [math]m[/math] containing one of the permutations, apply [math]\mathcal{K}_2[/math] [math]m-2[/math] times, and then apply [math]\mathcal{K}_1[/math] once, for a total tape length of:
[eqn] m+2(m!-2)+1 [/eqn]

>>10102974
Typo: [math]m! - 2[/math] times.

>>10102974.
So, how many episodes it would be for 14?

>>10103349
Between 93,884,313,611 and 93,924,230,411.

Wait, I may have made an off-by-one error. You don't need to make a complete circuit, you just need to get from some member of [math]\mathfrak{G}(\Sigma)[/math] to some other member with a path that traverses all other nodes. This does not have to exist for any such pair, but it must exist for at least one pair.

I don't even understand the question, can someone give me an example with 3 episodes?

1,2,3
1,3,1
2,3,1
2,1,3
3,1,2
3,2,1

>>10103931
123121321

>>10103931
You've got half the concept. Now put them all in one string and realize that each entry can be a part of multiple sets.

e.g.:
12312 contains {123}12, 1{231}2, and 12{312}. So you're three sets down with only five episodes watched. Now you just need to create the smallest possible string of episodes that contains, somewhere, every permutation of episode orders.

>>10103938
>>10103940

Ok, so how comes the minimum of episodes is actually bigger than 14 ! ?

In the example with 3 episodes, you can only get 6 strings.

>>10103949
6 strings with 3 episodes each = 18 episodes.
Or, you could use the superpermutation given by >>10103938, and you'd watch every single possible combination in a single larger string of 9 episodes.

Same thing goes with 14 episodes, you get 14! combinations normally, but there are ways to watch them all in a single string of episodes, which is pretty large but the total amount of episodes you need to watch is less nonetheless.

>>10103971
So the worst possible outcome would be 14! * 14 episodes?

The question is clearly asking for the lower limit, that much I can understand, but what's the worst case scenario (which is usually easier to understand for brainlets like myself).

>>10103978
That's the naive worst case, but if you can create some algorithm which always generates a superpermutation, and it has a definite output length, then that length becomes the new upper bound, because your next algorithm has to be at least as good.

>>10103990
Christina!, I knew you were a 4channer! Virgin perverted genius girl!
>>10100959
Pretty much possible it leads to a self-repeating pattern.

>>10104316
I don't know you and my name's not Christina.

I've found out that since all permutations can be represented as the composition of the swaps of two adjacent elements, then [math]\mathcal{K}_1[/math] and [math]\mathcal{K}_2[/math] complete the symmetric group [math]\mathfrak{G}(\Sigma)[/math] because they can be used to generate any such swap.

>>10096463
>Publishing a paper to cite would ruin the delicious awkwardness, which is almost as sweet to drink as tears.
Only one choice.
Publish an irregular /sci/entific Journal on our own.

>>10104324
is that more efficient, though?

What complexity class is finding the shortest superpermutation?

A brute-force approach to generating all superpermutations would be O(n!!) I guess.

>>10104669
Well, it's obviously at least NP-hard, although I can't really come up with a reduction of SAT to Haruhi.

>>10089776
I'm confusing the two. Why are they not the same?

>>10092136
https://oeis.org/A180632/a180632.pdf
Guess who's the first author?

>>10104706
I'm beginning to think it's a special instance of the travelling salesman problem, where the distance between vertices is the number of characters that have to be appended to the tape in order to add a new permutation.

>>10104669
>What complexity class is finding the shortest superpermutation?
According to conversation on the plebdit 4 years ago
>https://www.reddit.com/r/math/comments/20jv9j/whats_the_shortest_string_of_the_digits_1_2_3/
>is there an easy explanation why five is still unknown... it seems small enough brute force approach would solve it
> >Well, it would suffice to show that no string of length 152 is a superpermutation. So to brute force that, you would have to check all strings of length 152 on 5 symbols, which is a set of size 5^152, which is astronomical.
> >There are of course many improvements that you can make (e.g., only search the strings that start with "12345"), but those only reduce "astronomical" to "slightly less astronomical".
> >In other words, for the case of n digits, remember that you're not checking strings of length n, but rather checking strings of length that grows like n! (so your search space grows like n^n! , which is crazy).

>>10104856
> I’m beginning to think it’s a special instance of the travelling salesman problem

That’s a very good idea. It led to the disproof of the original conjecture on how long superpermutations have to be.

https://arxiv.org/abs/1408.5108

>>10092532
>>booette shitposter
Hey leave him alone

>>10089701

Is there a proof that the optimal string will never contain repeats of a permutation? Might be trivial, but I havent thought about it too much.


>>10104669
>>10104706
Maybe a different version is, after all you're basically trying to solve a special case of TSP on the permutation graph.

But I dont think you could reduce 3SAT to a problem with only one parameter, n.

>>10104856
Robin Houston actually used this in his 2014 paper to heurustic out a short solution for n=6. I wonder if theres any underlying structure to that solution that would yield insight. The thing I find interesting is how often it prematurely exits 1 cycles. In the standard algorithm, 1 cycles are always completed as a group, e.g. 123, 231, 312 are the first three permuations and they all belong to the element (1 2 3). So if you take a list of the 720 permutations in the order they appear in the standard solution and group them by 1 cycle, you get a list of 120 1 cycles. For Houston's solution you get 145.

>>10105805
>Is there a proof that the optimal string will never contain repeats of a permutation?

No, there isn’t! That does seem to be true in practice, but no one has proved that the optimal string can’t contain repeats.

Maybe someone here can prove it.

>>10105816
>but no one has proved that the optimal string can’t contain repeats.
I don't think it can. I'm bruteforcing n=4 now for shit and giggles, and so far I see one clear pattern: for 34 you list all combinations, for 33 you list all but one combination. If you exclude more than one combination, you will not get anything. Since n=4 was bruteforced many times by various methods with various algorithms and machine assistance, there's little doubt about it.
For n=5 there should be excluded 9 combinations to get 153 numbers.

>>10105805
>I wonder if theres any underlying structure to that solution that would yield insight.

There are now *loads* of known superpermutations of 872 characters on 6 symbols.

The best way to understand their structure seems to be to look at the 2-cycles they visit. Each of them visits 29 different 2-cycles. Draw a graph of these 2-cycles where you connect two 2-cycles if they share a 1-cycle. Then they all seem to have the same basic structure: a single 3-cycle that has all the other 2-cycles attached to it in a tree.

>>10105837
>I don't think it can.
I don’t think it can either, but sadly that isn’t a proof.

>>10105840
> There are now *loads* of known superpermutations of 872 characters on 6 symbols.
There’s a collection of them at https://github.com/superpermutators/superperm/tree/master/superpermutations/6/872

>>10105843
>I don’t think it can either, but sadly that isn’t a proof.
It not a proof but by nature superpermutation itself _has_ to contain all combinations. The moment you get repeats, doubles, or whatever, it means your result doesn't contain all combinations or longer than most short result possible. And the shorter your result, the tighter your combinations placed, so there's no place for repeats of any kind. It's just won't be possible.

https://drive.google.com/file/d/1WPsVhtBQmdgQl25_evlGQ1mmTQE0Ww4a/view

Is there anybody else noticed that Atya completed the theory of every thing?
Apparently he pointed out that the multi-dimensional universe is entangled with 8 cycles.
However, if his proof is true, it will be logically guided that for all the universe tangled in this 8 cycle, all substances with micro information volumes are extremely massive black holes.
However, from us as one of the multi-dimensional cosmos it seems to be only particles with a very small information volume.

Atiyah is to say in the paper that it should give up the anthropic principle, I do not agree too.
Because, if his proof is correct, if everything with a small amount of information in the classical observation of this world are all black holes, our brain which is handled by the exchange of electrons is in the quantum brain. So logically collective unconscious will exist.
Though there is a collective unconscious, I wonder should abandon the anthropic principle?

>>10105805
>I dont think you could reduce 3SAT to a problem with only one parameter, n.

In theory you can encode literally everything, say, the entire observable Universe, in a single n.
The question is, if you then still have a decision-preserving bijection between the problems at hand, and I also don't see how you could do that.

>>10105057
I was more thinking if it fit in NP, but I don't have the necessary expertise.

>>10105805
>But I dont think you could reduce 3SAT to a problem with only one parameter, n.

Why not? This is brute-force.
I am taking a list of all episode permutations k=(n!) and fetching all permutations of that list k! .

Shoving it together as far as possible should be negligible compared to O(n!!) .

>>10105943
Is O(n!!) for naive brute-force to definitely find all minimal optimal solutions that far off?

>>10104828
Each ordering corresponds to a string containing every episode in a distinct order from all other such strings. The number of episodes you'd have to watch is the shortest string such that you can find every string within it at least once.

What is a minimal superpermutation good for anyway?

Ensure that you tested all plausible state transitions in complete cycles that walk through all states once in series?
Graph-walking all state combinations while ensuring that you would never move to the same state before not having walked through the others?

Is it always possible to find a superpermutation whose length is equal to "n * n!", while merging subsequences together whenever possible?

>>10106871
It's not possible for n=2

>>10106154
Well, with O(n!!) you have looked at all possible orders in which permutations could start in the superpermutation.
In order to be sure to have found the minimal superpermutation you'd have to always create a maximum overlap between successive permutations, which is trivial.

That should work. Yes, it's probably O(n!!).

>>10105805
>Is there a proof that the optimal string will never contain repeats of a permutation
I was asking myself the same thing. Intuition says this should be true - after all, any repeated permutation will add redundant characters and I doubt you can increase overlapping by adding one.

Anyway, he's a few nice pictures from my research.

>>10106889
n!! is crazy
1, 2, 720, ~2^79, ~2^660, ~2^5801, ~2^54724, ~2^558703, ...

>>10106879
I forgot about that. So it's probably not possible for higher n too, I guess.

>>10106925
>n!! is crazy
Be glad it's at least not the Ackermann function.

>>10106935
Mhm.

>>10106892
>yfw when calculation of some number will give you a picture
>yfw it will be a SOS Dan logo
Haruhism is real! Praise return of the true goddess IRL! Kek, Moloch, Yahweh, Buddha and others will not stand a chance!

Huh, interesting. I was actually plaything around with an extremely similar thing a while back.

I'll look into it more.

>>10099095
You don't.
It's not solution to the problem, it's just the lower bound. We don't know how to calculate the smallest superpattern, but we know it has to be more than the formula.

I have a question. Did anyone even attempt to check "superpermutation of length 872" here https://oeis.org/A180632 ?
Because this shit doesn't contain 123564 and it's almost broke my mind since everything else visually had very simple and logical structure.

>>10107430
It also doesn't have 124365 and 162543. There's probably some duplicated combination but I'm not autistic enough to search for it. It also has 65[12341]56 combination, which is an instant no go, kek.

>>10107430
Also, now that I think about it, it's very easy to check them in Word. Just use 1[2-6]{5} with wildcard checked: right combination for n=6 will contain 120 matches, wrong combination, like this one contains only 114 matches.

>>10089745
given 1, 2, 3

you can order them as 123, 132, 231, 213, 312, 321

but you would have to watch 3x6 = 18 episodes to watch all possible order of the episodes. we try to find ways where we watch all the possible order of episodes by watching the least amount of episodes.

consider one where you watch the episodes in this order: 123121321

you can check that it contains all the orders possible.

>>10104833
i cringe everytime people use "we"
neckbeard who psots pedophile cartoons contribute nothing to the discussion. the poster probably skipped 4chan altogether given how shitty this "Scientific" board have become

>>10107592
See this is being good at explaining things.

>>10107430
>Because this shit doesn't contain 123564
Try putting it all on one line, and search again. (12 at the end of line 2, 3564 at the beginning of line 3.)

When was the proof of the lower bound even posted?

Did mathematicians just randomly find that proof on the wiki?

>>10107963
>When was the proof of the lower bound even posted?
2011
>Did mathematicians just randomly find that proof on the wiki?
Yes

>>10107983
>>10107983
Damn, i didn't even browse /sci/ until 2012.
Either way, i doubt that guy will ever see this in time. Given that many people who come here are usually mentally unstable, there is a chance that the anon commited suicide. Hopefully not, i feel obliged to make sure nobody takes credit for this work though, or at least gives credit for this anon dude but his h-index wont be improved unless he writes the paper.

I remember back in 2012 how hated the tripfags were but there are occassions when trip-codes are actually useful and unfortunately it wasn't used here. Besides even if he did, who will remember his own trip code 7 years later?

I wonder even if the op's tripcode is still alive.

This proof is surely more useful but i want to share this thing while bumping the thread; another clever 4chan invention was sleepsort, on 4chan's /prog/ textboard back when textboard werent discontinued. It actually hit ytnd news and who the real poster was behind that clever thing was never found out nor did anyone come out to claim it.

This might be the case here aswell.

http://mathsci.wikia.com/wiki/Special:Contributions/Renaldo_Moon

is the guy who posted the proof on the wiki, damn props on you for doing that holy shit.

Was renaldo moon the op?

>>10108049
As it happens, both the OP and the author of the proof are alive and well, and know what’s going on. The OP has publicly talked about it on Twitter (@HitagiKrab), so that’s no secret. The author of the proof wishes to remain anonymous.

The only one I don’t know about is RenaldoMoon, but someone with a similar username deleted an old (2011) post about this from another forum in the past few days, so if that’s the same person then it’s a pretty huge coincidence if they don’t know about this.

>>10107484
You need to use something that ignores overlapping results.

>>10107952
>>10108121
Yeah, something somehow coped wrong. That 872 also contains 120 matches. Damn thing is a visual vomit and probably can't be symmetrical or anything by design.
After checking results from http://www.njohnston.ca/superperm5.txt it seems like there's simple strings that have very simple visual structure, and mindfucks. Simple n=5 (153) has the same logical visual structure as n=4 (33), same logic applies to n=6 (873).
On the other hand, n=6 (872) has the same lack of logical structure whatsoever (at least I don't see it), same as n=4 (34). So, either there's simple strings for n=6 (872) that have the same simple visual logical structure, or there's n=6 (871) with simple structure (though I can't imagine how) or there's n=5 (152) with the same lack of structure (also can't imagine).

>>10108315
Has n=5 been definitely solved to be the absolute minimum of all permutations of permutations?

I wonder how hard it is to extract all permutations from a superpermutation.

>>10108411
It's [math]O(n!)O(f)[/math] where [math]f[/math] is the string searching algorithm you're using.

>>10108411
>I wonder how hard it is to extract all permutations from a superpermutation.
I won't do the 5 tho.

>>10108504
I was thinking about an algorithm that picks out a list of permutations from a superpermutation.

It feels like this can be done in O(n) if superpermutations do not feature duplicates.

>>10108411
Yeah, n=5 has been completely solved. There’s an explanation of the algorithm with attached C code at http://www.njohnston.ca/2014/08/all-minimal-superpermutations-on-five-symbols-have-been-found/

>>10104833
ebin

for those still trying to figure out who it was, the author of the post has already acknowledged the situation and chosen to remain anonymous

even in the original thread they said that they'd keep working on the problem but that proof was all they were were going to post publicly

>>10108049
>there are occassions when trip-codes are actually useful
And in all those cases 4chan isn't the right place for you.
If you have some stupid idea, that may very well be wrong, and making it public with your name attached could ruin your life/career, but you don't want to let it go to waste, post it here. It may lead to something worthwhile.
That's exactly what 4chan is absolutely amazing for.
If you have a sure-fire idea that will get you a Nobel Prize, write a paper and release it in a journal. 4chan isn't the place to post uninteresting shit like that.
4chan is primarily for discussing shit you absolutely don't want to have your name or pseudonym attached to, and I'm glad it's there.

As a side note: Fuck the new captcha.
>google-analytics
That wasn't there before, either.

>>10108738
Source for that statement?

>>10110596
I don’t think there is a public source. You can believe it or not, as you choose. It is true, though – and I’m not the same anon as the one you’re replying to.

So at this point I've reduced the problem to a particular instances of another: the asymmetric traveling salesman problem where all distances are either 1 or 2. Surprisingly, there is some prior research on this subject. I'm reading one paper, and trying to get access to another.

>>10110995
That sounds great. Do you mean we only need to consider superpermutations where, to get a new permutation, you add either 1 or 2 symbols? If you’ve reduced it to that case, by showing there can never be a shorter superpermutation that uses edges of weight 3+, that’s MAJOR progress, and comes close to completely solving the problem.

Quite a lot is known about that case. Greg Egan’s construction gives an upper bound of n! + (n-1)! + (n-2)! + (n-3)! + (n-3), and the lower bound is n! + (n-1)! + (n-2)! + (n-3)! + (n-4). Almost certainly the lower bound is optimal.

Tell us more?

>>10089701
If you show me the paper I can have it up to 100 pages by January or 20 by like next week with a lot of segue for inference where I cnn approve explanations that'll fit my candor or at least let me repost.

Finished english too so some of the scientists can get on with waiting for more special theorems. we general lines here. no simpletons.

>>10111067
Yes, because I determined that any permutation can be decomposed into repeated applications of the two [math]\mathcal{K}[/math] transforms, and therefore every pair of permutations is reachable by some sequence of them.

>>10110995
>I've reduced the problem to a particular instances of another

Isn't that the uninteresting way round?
This doesn't yield a lower bound on complexity, but an upper bound.

Wait, is this supposed to be discussing that one part in Suzumiya Haruhi where they were stuck on repeat?

Was he really calculating the amount of Haruhi episodes, or is his proof applied afterwards?

>>10111077
>Yes, because I determined that any permutation can be decomposed into repeated applications of the two K
> transforms, and therefore every pair of permutations is reachable by some sequence of them.
I agree that is true. But how do you know there isn’t a more efficient way to build a superpermutation that uses longer jumps?

In practice that seems to happen. On six symbols, the shortest known superpermutation using only K1 and K2 has length 873, but there are shorter ones (length 872) that use K3 as well.

>>10111081
Tightening both the lower and upper bounds contributes to reducing the possible range of the problem's size, and finding new algorithms and analogizing the problem to others helps to narrow in on its complexity class.
>>10111112
Adding higher possibilities for [math]\mathcal{K}_n[/math] is simply equivalent to taking the union of the [math]n=2[/math] graph (which we already know to be connected) with the relation graphs of the higher orders. That may make it possible to determine the optimal [math]n[/math] by induction.

>>10110995
Which problem, exactly? There are actually a lot of questions about superpatterns here.

I'm familiar with viewing it as the TSP, but if you're looking at the lower bound for the shortest superpermutation, aren't you using the "greedy" approach in assuming it's only distance 1 or 2?

>>10111736
I for one think that the lowest number should follow "basic" >>10108315 pattern. If you can't recreate same pattern with less numbers, then that means a) it's the lowest possible number using this pattern; b) there's possibility of even lower number that doesn't have simple pattern (see n=6 (872)).
Same, probably, could be applied to >>10108504 - if you have something that looks like 34 (i.e. there's more than 2 points where numbers don't overlap at all), then it should be possible to make it with less numbers. Actually, if someone could write a program (maybe one that using both CPU and GPU to speed things up) that would check results and present them like this (and highlight all vertical points with least numbers or indicate point were they don't overlap), we pretty easy could figure if what we have is the lowest possible combination or not. That should get rid of ambiguousness we have now with confirming results.

>>10111879
How can you say for sure that taking an instance where numbers dont overlap at all and rearranging it so that that permutation uses less numbers won't screw things up later and require more numbers? e.g. maybe expending two extra numbers by not overlapping grants access to a cycle that's less redundant in the long term than the one you're forced into by overlapping a few more digits

>>10089701
>Plus for some reason not everyone thinks /sci/ is a reputable source.
It wasn't /sci/ that was checked, it was /a/. and since the post in question was from 2011, it was a secondary site that archives 4chan posts. Possibly someone was going through old anime posts, and stumbled across it?

>>10111973
No, it was /sci/.

>>10111973
The /sci/ thread archive is literally linked in the news article I saw.

So this is why all other boards look down on us...

>>10112185
>anyone looking down on /sci/
Nigga the other boards don't even think about us. The containment boards are /pol/ and /r9k/.

>>10112279
Any chance you have and could share those data from the pic? I'd like to do some hierarchical clustering and community detection on that matrix.

>>10112279
/gd/ looks so lonely
moot was right and should have just merged /gd/ and /3/

>>10112302
Another anon made it. The image was originally posted in a meta thread where /sci/ was complaining about /pol/. Moot was posting in it too and the next day he turned /pol/ into /cuck/ for a week.

>>10112313
>the next day he turned /pol/ into /cuck/ for a week
kek

>>10096580
He said it in his last QA when he was fucking retiring. He had no more stock in this place then.
You think he is some mastermind cabal overlord in league with the FBI and NSA but he was just a kid that made a anonymous bbs style forum to talk to his ADTRW goons about anime with. Given my personal experience with this place, everything he said during that last QA makes perfect sense and I really think he was telling the truth.
PS Fuck you

>>10112185
>racists and Nazi wannabes

Especially the term "Nazi" has been used so broadly by the left that it has lost all its original meaning. Now it's practically "guy with an opinion that I don't like".
In that sense it's similar to "fascism" (="ideology I don't like").
To be a Nazi in the original sense (=national socialist) you also need a socialist component.
Most right-wing faggots these days have none of that. They only have the nationalist/patriotic bit.

/b/ is a shithole I visited once or twice back in 2005, but didn't feel like coming back to. It's probably only become worse since then.
/pol/ is decent on election nights. Probably because different people than usual are in those threads. Warning: US elections may be a different story.

>>10089701
Its imposible

>>10112351
>/b/ is a shithole I visited once or twice back in 2005
guess how I know you are lying you little limp harbl

>>10112359
No idea. I'm not lying.

Found 4chan back in 2005 while looking for wallpapers.
/b/ was garbage. /a/ and /v/ are what kept me here.

>>10111970
I wasn't talking about building superpermutation, but about checking results of the build. With computer analysis and graphic representation it's possible to make some conclusions while not spending hours on it.
Pic related for example can let you make conclusion that sequence which starts with 123... and has 121 in the middle can work as litmus test. Also, the shortest superpermutation probably will have only those 3 numbers being the shortest vertically, aside from the beginning and the end (which means theres 152 or even 151 for n=5). So, if someone manage to make n=6 (872) which fits this condition we may learn something new.

>>10112749
Fixed.

>>10112749
Also this.

>>10112351
The semantic issue with Nazis and socialism is a lot older. The national socialist party existed before Hitler took it over, but once he did, he slowly cleansed it of socialist elements, completely purging them with the execution of the Strasser and Röhm factions in the Night of the Long Knives.

>>10112980
Half-truths.

>>10112754
Wait, I've made a mistake in first two for n=5. That's why we need computer analysis for this. And, indeed, 153 is the shortest possible number for 5.

>>10112759
Fixed.