« first day (1264 days earlier)      last day (63 days later) » 

H.PWiz
H.PWiz
15:19
I haven't thought very carefully about this problem... but while playing, I found x+((|||||)x+)|x for n³
which I suppose is just (|||||)x+x+|x
H.PWiz
H.PWiz
16:10
((|||||||||||)x*x+)?x?x+ works for n^4
Which could be ((|){2,3}x*x+)?x?x+
I'm not sure what the best way to multiply by 12 is
The way I found this was by guessing random things... I saw that x?x*x+x+ gave me oeis.org/A002415, which looks pretty close to n^4. So I multiplied by 12, and added n^2
H.PWiz
H.PWiz
17:05
Odd powers can be nicer in some ways. For n^5 I've got (||){1,4}x*x+x+x+|(|){1,4}x+x+|x, but there should be a better way
Deadcode
Deadcode
@H.PWiz Wow, amazing! I didn't expect there to be that much room for improvement.
@H.PWiz How does this work? I'm figuring it to be ((2^3+2^2)*(n+2)*(n+1)*n/6 + 1)*n^2 = (2*n^3 + 6*n^2 + 4*n+1) * n^2 but that's obviously not true. What did I do wrong?
H.PWiz
H.PWiz
I tried to explain it above.
> I saw that x?x*x+x+ gave me oeis.org/A002415
Deadcode
Deadcode
Er, I mean ((2^3+2^2)*(n+2)*(n+1)*n/6 + n + 1)*n^2 = (2*n^3 + 6*n^2 + 5*n+1) * n^2, but it still doesn't work out, and is 1 degree higher than the regex actually evaluates to
H.PWiz
H.PWiz
I think x*x+ shouldn't be (n+2)*(n+1)*n/6
Deadcode
Deadcode
Well that part is correct
((|){2,3}x*x+|) really is ((2^3+2^2)*(n+2)*(n+1)*n/6 + n + 1
But the last part is where it's not matching up, concatenating it with x?x+
H.PWiz
H.PWiz
17:18
@Deadcode Yes, I suppose you're right. The problem is, that you aren't really multiplying by n^2. That would be (?*(|){2,3}x*x+|)x?x+ (I think)
Deadcode
Deadcode
Oh, right.
H.PWiz
H.PWiz
The best way to analyze it is by looking at (|){2,3}x*x+x?x+|x?x+
Deadcode
Deadcode
(2^3+2^2)*((n+2)*(n+1)*n*(n-1)/24 + (n+1)*n*(n-1)*(n-2)/24) + n^2 = n^4, yes :-)
Nice work!
@H.PWiz Any ideas how to do a generalized n^m without molecular lookahead? Even just something like ^(?=(x*)\1{7}(x{4}())?(xx())?(x())?)((?=\1(x*))(x+(|){3}|\3(|||)|\5(|)|\7).*(?=\9$)){8} except where merely changing just the {N} would change the power.
H.PWiz
H.PWiz
I haven't thought about it yet
Have you got any method for figuring out how to multiply by n?
For n^7, I want to do 5040, and 1680, and ...
Deadcode
Deadcode
17:37
@H.PWiz Nope, no idea yet. That's the question.
@H.PWiz Maybe you've already generated one of these yourself by now, but here's what I have so far: number-of-match-constant-multiplication.txt
Most of the larger numbers are not optimized yet. I was planning to write a brute-forcer for the factoring aspect of it.
Currently the only factoring is what I did manually.
H.PWiz
H.PWiz
@Deadcode No, that should be useful. Anyway, here's one for n^7 that I found manually (||||||)((||){2,5}(|)x*x+|(|)(||){1,4})x*x+x+x+|(|){1,6}x+x+|x
For odd powers, you can do something like x*x*x+x+x+x+ which gives (n-3)*(n-2)*(n-1)*n*(n+1)*(n+2)*(n+3)/7!. Then multiply by the factorial, and you get something like (n^2-9)(n^2-4)*(n^2-1)*n. When expanded all the terms have odd powers, and you can gradually improve it
We have n^7-14n^5+49n^3-36, so we add 14*(n^2-4)*(n^2-1)*n to get n^7-21*n^3+20*n
Then you can take add 21*(n^2-1)*n, and then add n
Deadcode
Deadcode
@H.PWiz Very nice! 7*((3^5+3^4+3^3+3^2)*2*(n-3)*(n-2)*(n-1)*n*(n+1)*(n+2)*(n+3)/5040 + (2*(3^4+3^3+3^2+3)*(n-2)*(n-1)*n*(n+1)*(n+2)/120)) + (2^6+2^5+2^4+2^3+2^2+2)*(n-1)*n*(n+1)/6 + n = n^7
H.PWiz
H.PWiz
In my regexes for 5 and 7, I have (||){1,4}, which can be (|){3,6} according to your list
Deadcode
Deadcode
Ohhh
Deadcode
Deadcode
18:39
@H.PWiz Okay so clearly with the kind of optimizations you've found, it'll be later that the more generalized approach wins, so I generated it up to a higher point:
^(?=(x*)\1(x()|))\2(x+(|)|\3).*(?=\1$)(?4)
^(?=(x*)\1\1(x())?(x())?)((?=\1(x*))(x+(||)|\3|\5).*(?=\7$)){3}
^(?=(x*)\1{3}(xx())?(x())?)((?=\1(x*))(x+(|||)|\3(|)|\5).*(?=\7$)){4}
^(?=(x*)\1{4}(xx())?(x())?(x())?)((?=\1(x*))(x+(||||)|\3(|)|\5|\7).*(?=\9$)){5}
^(?=(x*)\1{5}(xx())?(xx())?(x())?)((?=\1(x*))(x+(|||||)|(\3|\5)(|)|\7).*(?=\9$)){6}

« first day (1264 days earlier)      last day (63 days later) »