10 ms·
Mystery math whiz and novelist advance permutation problem
- deleted 3y ago[deleted]
- ftxbro 3y agoit was on hacker news before https://news.ycombinator.com/item?id=23968618 https://news.ycombinator.com/item?id=23968618
- bombcar 3y agoDidn’t futurama prove something tangentially related?
- tehlike 3y agoThis one? https://theinfosphere.org/Futurama_theorem https://theinfosphere.org/Futurama_theorem Also futurama is coming back, in case you didn't know.
- rhaps0dy 3y ago(2018)
- sashank_1509 3y agoInteresting that the folks who wrote a proof based on the 4Chan user's post listed him as a first author. In all of my experience, Mathematics truly seems to be the field with the highest integrity.
- AmericanChopper 3y agoImagine getting disciplined for plagiarising your paper from 4chan tho…
- kkylin 3y ago> Mathematics truly seems to be the field with the highest integrity. Mathematician here. I'd like to think we have high (not sure about highest) integrity. But I should also point out that the custom in the field is to list authors alphabetically by family name, and the paper in question (https://oeis.org/A180632/a180632.pdf https://oeis.org/A180632/a180632.pdf) does not break with custom if you view "anonymous" as "family name"...
- Paul-Craft 3y agoI would think that "4Chan Poster" would be the "family name" here. Which, of course, would come lexicographically before most real family names.
- fsckboy 3y agoI would think they should have listed newfag as the author. https://en.wiktionary.org/wiki/newfag https://en.wiktionary.org/wiki/newfag
- Paul-Craft 3y agoHeh. "4Chan Poster, Newfag" would have been a great way to list the author's name. Perhaps ironically, the convention would then imply that newfag comes before oldfag. https://en.wiktionary.org/wiki/oldfag https://en.wiktionary.org/wiki/oldfag
- 3y ago
- fastball 3y agoAre you actually allowed to use Super positions for this (watching the TV show in every order). Presumably the whole point is that you get a different experience from watching a certain episode after watching others and vice versa, and since our brains don't really exist in a state of quantum superposition, not sure you can kill two birds with one stone. You're either watching it in the context of earlier than these episodes or later than these episodes, but never really both.
- quickthrower2 3y agoYes but that doesn’t lead to new mathematics!
- Someone 3y agoIt also isn’t a practical problem, even for very low number of episodes. For n >= 2, you’d want to look both at #1 before you’ve seen #2, and at #2 before you’ve ever seen #1. As long as we’ve no way to zap memories, that is impossible.
- quickthrower2 3y agoI can. Just wait 6 months between sittings.
- defrost 3y agoCuriously no input from Cheryl Praeger even considering her retirement in 2017.
- mchangun 3y agoCan someone motivate the problem for me? Why isn't the answer just 14! ?
- defrost 3y agoIf you watch the 3 episode series Example in the order 1 2 3 you have seen all the series episodes in one order. If you watch the episode sequence 1 2 3 1 you have now seen the series in two orders by watching a sequence of 4 episodes.
- jfoutz 3y agooverlaps. I wanna say it's a de Bruijn sequence. > 2! is > 1, 2 then > 2, 1 but you can skip an episode, and hit all permutations with > 1, 2, 1
- anonymoushn 3y agoThe question is what's the shortest sequence that contains every permutation as a substring. If each episode after the 14th got you a new permutation, you would need 13+14!, but that's not possible. For example with 3 episodes, you could begin 12312, then any episode you choose from that position does not contribute a permutation. I think the shortest sequence goes 123121321.
- quickthrower2 3y ago> If a television series has just three episodes, there are six possible orders in which to view them: 123, 132, 213, 231, 312 and 321. You could string these six sequences together to give a list of 18 episodes that includes every ordering, but there’s a much more efficient way to do it: 123121321.
- tromp 3y agoAnd with 7 substrings of length 3, it's provably minimal, since making every 3-substring a permutation of 123 forces every element after the first 2. Assuming without loss of generality that it starts with 1 2, it is forced to start with 1 2 3 1 2 3 but there already repeats the same permutation. So one substring must be wasted (in the article this is phrased as having to traverse one higher cost edge in the corresponding graph).
- wly_cdgr 3y ago[flagged]
- tus666 3y agoI wonder if duplicate sequences are allows - i.e. a sequence that makes you watches every possible permutation, but only exactly once.
- vintermann 3y agoFrom the definition, they should be. It only says every permutation should exist as a substring, not that it should only exist once.
- r721 3y agoDiscussion from 2018: https://news.ycombinator.com/item?id=18389080 https://news.ycombinator.com/item?id=18389080 (80 comments)
- tarentel 3y agoThis is kind of interesting to look back on. I checked the group really quick and they shut down the program trying to find a better solution to the n=6 problem in March of this year. The most upvoted post was also a bit optimistic in thinking this problem might be solved in a few weeks. I don't know much about it but I am assuming it has not been solved yet.
- AtNightWeCode 3y agoIs this not the same problem as older numerical keypads on doors? The ones that opens as soon as you enter the correct 4-digit sequence. The cops used a pattern to crack those fairly quickly back in the 90s at least.
- krackers 3y agoThat's a https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence
- AtNightWeCode 3y agoThank you
- beardyw 3y agoNo t quite as abetusk points out in this thread, since repeated numbers are not part of the requirement.
- mimmodj2017 3y agobella domanda in my mind i think that everybody can match
- fsckboy 3y agoall I have to add, and this may be of interest to nobody but me, I remember this discussion back in the day. Not because of the number of permutations of orderings to watch, but because I was intrigued that people had different reasons for preferring different orderings for the shows. Just struck me as strangely beautiful.
- layer8 3y agoI wonder if the problem would be simpler if the superpermutation would be treated as a repeating (circular) sequence. I.e., what is the shortest sequence (having length n) such that if the episodes where shown in an endless repetition of that sequence, viewers could start at any episode and watch the next n + k episodes to catch all permutations. This would remove both ends of the superpermutation being a special case, so to speak. (Cue comments about the Endless Eight.)
- lawrenceyan 3y agoI'm not sure I'd recommend choosing to go on 4chan actively as a hobby, but I definitely had an interesting experience growing up on it. I must have been in middle school when I first started going on there, and it's where I first learned about Bitcoin in ~2010/2011.
- emptyfile 3y ago[dead]
- adamgordonbell 3y agoAnyone read Luminous by this author? It's an action packed short story about math truths. Super good. > A truly wonderful story in which two math grad students discover that the things we consider to be "truths" in number theory are actually part of a dynamical system, subject to change over time and in competition with alternative "truths" that are equally valid at other "locations" in the number system. https://www.amazon.com/exec/obidos/tg/detail/-/1857985737 https://www.amazon.com/exec/obidos/tg/detail/-/1857985737
- badcppdev 3y agoSurely Permutation City by Egan is more relevant :-D
- adamgordonbell 3y agoI mean the title of Permutation City is more relevant. :) But the one I linked to is an action / adventure story about discovering new something in math. So content wise, it's more relevant. And I just liked it and want people to read it.
- Randomizer42 3y agoInb4 it was ChatGPT. lol
- 7373737373 3y agoThat'll most definitely happen at some point: https://openai.com/research/improving-mathematical-reasoning-with-process-supervision https://openai.com/research/improving-mathematical-reasoning...
- badcppdev 3y agoHeadline should have read: "Mystery math whiz and mysterious novelist advance permutation problem".
- djoldman 3y agoThis problem has been fun to tackle computationally via a few kaggle competitions. Example: https://www.kaggle.com/competitions/santa-2021 https://www.kaggle.com/competitions/santa-2021
- NoMoreNicksLeft 3y agoThis has (or had) real world implications. Back when phone answering machines were a thing, and you could dial a pin number to your own to have it play back messages... well, I remember an article in 2600 (I think) that explained that there was a superpermutation that gives up the goods. It would take up to 3 or 4 minutes to dial in, but eventually you could start hearing the messages. There was some mention of news reporters doing this to the phone numbers of local politicians, but that must have been speculative or outright bullshit (even then there would have been an applicable law against using such an exploit).
- justjonathan 3y agoFrom just the headline I bet it was going to be Greg Egan, author of Permutation City. Was not disappointed.