--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq2VTniqBQR2KntK3_%3DO67%3D0ZfvRRejRAD4y6Q%2B%2B%2Bvh64w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
In a path where all edges have weights 1 or 2, we can never have n(n-1)-1 consecutive edges that all belong to the same 2-cycle, except right at the end of the path, because if they did the next edge (of weight 1 or 2) would visit a node in the same 2-cycle, which must have already been visited.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e197889e-223e-456c-bd19-7545ad03b6de%40googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq3WKaV2Jvb2hSoQCJj-cJnHL9XvWpbYFOzMcrnouMvwjg%40mail.gmail.com.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
The key lemma that makes this work is: if x1(p') - x1(p) = 1 then x2(p') = x2(p).
Thank you! I was worried no one would have the time or energy to check it carefully. It’s very kind of you.
So this together with your improved upper bound brings the gap between the two down to (n - 3)!
I’m in awe of the anonymous anime fan who came up with this beautiful, subtle proof. I’ll see if there’s any way to get in touch with him/her.
On Tue, 23 Oct 2018 at 08:44, Greg Egan wrote:
I’ve gone through this as carefully as I can, and I’m pretty sure it’s right. It’s really hard to pick correct definitions here and to be sure about all possible cases, but I think you’ve done it — I certainly can’t see any flaws. Well done!--
On Tuesday, October 23, 2018 at 3:48:33 AM UTC+8, Robin Houston wrote:I think I have it!
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
Thanks for your proof Robin! I also happened to spend a long time yesterday understanding the lower bound, and I think we are mostly in agreement. If I'm understanding your proof correctly, I think there is a small gap. You claim:The key lemma that makes this work is: if x1(p') - x1(p) = 1 then x2(p') = x2(p).but I'm not sure this is true. It seems to me that you could take a 2-step in the middle of a 2-loop, and if the cycle you're leaving has already been completed. then x0, x1, and x2 all increase by 1. (You can rule this out if you prove that a permutation is never re-visited in a superpermutation, but to my knowledge we haven't proved that yet. As a side note, I think that will be an important step to making the upper and lower bounds meet.)I wrote a short note explaining how I read the proof, using the easier lower bounds as a warmup. I handle the gap I mentioned above in the long, tedious paragraph in the middle of page 3. My notation is a little hand-wavy, but I didn't think it was worth rewriting just yet. Let me know if any parts don't make sense!And thanks for gathering so much interest around this problem.
On Tuesday, October 23, 2018 at 3:16:02 AM UTC-5, Robin Houston wrote:
Thank you! I was worried no one would have the time or energy to check it carefully. It’s very kind of you.
So this together with your improved upper bound brings the gap between the two down to (n - 3)!
I’m in awe of the anonymous anime fan who came up with this beautiful, subtle proof. I’ll see if there’s any way to get in touch with him/her.
On Tue, 23 Oct 2018 at 08:44, Greg Egan wrote:
I’ve gone through this as carefully as I can, and I’m pretty sure it’s right. It’s really hard to pick correct definitions here and to be sure about all possible cases, but I think you’ve done it — I certainly can’t see any flaws. Well done!--
On Tuesday, October 23, 2018 at 3:48:33 AM UTC+8, Robin Houston wrote:I think I have it!
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee95265a-c969-48a0-840d-89f33d3b6ac4%40googlegroups.com.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.
Hi Everyone!
I wasn’t aware of the Haruhi problem up to these days, when someone on 4chan gave a kind of solution.
I had a look on it and I’d like to post here my approach.
The shortest string containing all the permutations of n digits occurs when you are able to take advantage of the maximum overlap between each permutation, obviously.
Given a permutation of n digits, I can find at maximum (n – 1) different permutations that grant the maximum overlap (n – 1) with an overall length of (2n – 1) digits.
Than I have to lower down to an overlap of (n – 2) for finding a new different permutation that grants other (n – 1) different ones with maximum overlap (n – 1); this new series has length equal to 2n – 1 – (n – 2) (I’m subtracting n – 2 because of the overlap with the previous permutation series).
Lets call L a string of n permutations with overlap (n – 1) between them.
I can put in a row (n – 1) L strings with overlap between them equal to (n – 2) than I have to lower down to (n – 3) for being able to create a new block.
Here it follows the L string lengths for n = 5:
L1 => length 9 (2n – 1)
L2 => length 6 (2n – 1 – (n – 2) for the overlap with L1)
L3 => length 6
L4 => length 6
_______________________________________
L5 => length 7 (2n – 1 – (n – 3) for the overlap with L4)
L6 => length 6
L7 => length 6
L8 => length 6
_______________________________________
L9 => length 7 (2n – 1 – (n – 3) for the overlap with L8)
L10 => length 6
L11 => length 6
L12 => length 6
_______________________________________
L13 => length 7 (2n – 1 – (n – 3) for the overlap with L12)
L14 => length 6
L15 => length 6
L16 => length 6
_______________________________________
L17 => length 7 (2n – 1 – (n – 3) for the overlap with L16)
L18 => length 6
L19 => length 6
L20 => length 6
_______________________________________
L21 => length 7 (2n – 1 – (n – 3) for the overlap with L20)
L22 => length 6
L23 => length 6
L24 => length 6
Total = 152
Lower bound formula = n^2(n – 2)! + n – 3
Hope my post could be of interest.
Best regards.