Comments on Une expression régulière pour les multiples de 7

quelqu'un (2020-09-02T10:39:51Z)

Anders Kaseorg on Code Golf Stack Exchange has a 10791 char solution (without anchors, so would be 10793 with them) <URL: https://codegolf.stackexchange.com/a/75326/ >

jonas (2020-09-02T10:36:10Z)

It turns out that Golf SE has a post for finding such a regular expression <URL: https://codegolf.stackexchange.com/q/3503/ >. The current best answer there ties but predates int-e's regex with 10791 characters. And that post was motivated by Matthias Görgens having computed such a regex <URL: https://github.com/matthiasgoergens/Div7 > in 2010-11.

int-e (2020-09-02T00:02:55Z)

I've got 10793 (obviously with no claim of optimality):

^(0|7|46*[29]|(2|9|46*4)(3|56*4)*(1|8|56*[29])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18]))|(5|46*[07]|(2|9|46*4)(3|56*4)*(6|56*[07])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])))|(3|46*5|(2|9|46*4)(3|56*4)*(4|56*5)|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(5|46*[07]|(2|9|46*4)(3|56*4)*(6|56*[07])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5)|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))))(1|8|[29]6*5|(0|7|[29]6*4)(3|56*4)*(4|56*5)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(5|34*6|(2|9|34*3)(6|[07]4*3)*(2|9|[07]4*6)|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(1|8|64*6|(5|64*3)(6|[07]4*3)*(2|9|[07]4*6))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))))|(6|46*[18]|(2|9|46*4)(3|56*4)*(0|7|56*[18])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07]))|(5|46*[07]|(2|9|46*4)(3|56*4)*(6|56*[07])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])))|(3|46*5|(2|9|46*4)(3|56*4)*(4|56*5)|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))|(5|46*[07]|(2|9|46*4)(3|56*4)*(6|56*[07])|(1|8|46*3|(2|9|46*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07])|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6)))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5)|(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4))))(1|8|[29]6*5|(0|7|[29]6*4)(3|56*4)*(4|56*5)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(4|34*5|(2|9|34*3)(6|[07]4*3)*(1|8|[07]4*5)|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(0|7|64*5|(5|64*3)(6|[07]4*3)*(1|8|[07]4*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])))))(2|9|53*[07]|(0|7|53*5)(6|43*5)*(1|8|43*[07])|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18]))|(4|[07]6*3|(5|[07]6*4)(3|56*4)*(2|9|56*3)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])))|(6|53*4|(0|7|53*5)(6|43*5)*(5|43*4)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(4|[07]6*3|(5|[07]6*4)(3|56*4)*(2|9|56*3)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))(1|8|[29]6*5|(0|7|[29]6*4)(3|56*4)*(4|56*5)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(4|34*5|(2|9|34*3)(6|[07]4*3)*(1|8|[07]4*5)|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(0|7|64*5|(5|64*3)(6|[07]4*3)*(1|8|[07]4*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(3|63*[07]|(1|8|63*5)(6|43*5)*(1|8|43*[07])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(5|36*[18]|(1|8|36*4)(3|56*4)*(0|7|56*[18])))))*(3|53*[18]|(0|7|53*5)(6|43*5)*(2|9|43*[18])|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))|(4|[07]6*3|(5|[07]6*4)(3|56*4)*(2|9|56*3)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29])))|(6|53*4|(0|7|53*5)(6|43*5)*(5|43*4)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(4|[07]6*3|(5|[07]6*4)(3|56*4)*(2|9|56*3)|(1|8|53*6|(0|7|53*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))(1|8|[29]6*5|(0|7|[29]6*4)(3|56*4)*(4|56*5)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(0|7|63*4|(1|8|63*5)(6|43*5)*(5|43*4)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(2|9|36*5|(1|8|36*4)(3|56*4)*(4|56*5))))*(5|34*6|(2|9|34*3)(6|[07]4*3)*(2|9|[07]4*6)|(0|7|34*[18]|(2|9|34*3)(6|[07]4*3)*(4|[07]4*[18]))(3|56*4|(6|56*[07])(4|36*[07])*(1|8|36*4))*(1|8|64*6|(5|64*3)(6|[07]4*3)*(2|9|[07]4*6))|(6|[29]6*3|(0|7|[29]6*4)(3|56*4)*(2|9|56*3)|(3|[07]3*6|(2|9|[07]3*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))(5|[18]6*3|(6|[18]6*4)(3|56*4)*(2|9|56*3)|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(0|7|36*3|(1|8|36*4)(3|56*4)*(2|9|56*3)))*(4|63*[18]|(1|8|63*5)(6|43*5)*(2|9|43*[18])|(2|9|63*6|(1|8|63*5)(6|43*5)*(0|7|43*6))(4|36*[07]|(1|8|36*4)(3|56*4)*(6|56*[07]))*(6|36*[29]|(1|8|36*4)(3|56*4)*(1|8|56*[29]))))))*$

This was obtained using a refinement of the state elimination method: Construct regular expressions that capture paths from a starting state, via a set of intermediate states, to a final state. The main regular expression results from a path from 0 via {1..6} to 0. To realize a path from a via B to c, we pick an intermediate state s in B, let B' = B - {s}. The path splits into a path from a via B' to s, then any number of paths from s via B' to s, and finally a path from s via B' to c. Alternatively, we never visit s and have a path from a via B' to c. This refines the state elimination method because we get to pick different intermediate states for the resulting subproblems.

Gonzolino (2013-03-24T09:08:55Z)

Bon, je viens de pythoniser ça. Je pars évidemment de l'automate (minimal) des congruences, et trouve l'expression «à la Arden».

Pour les multiples de 2, j'obtiens :
(4+0+8+6+2+(3+9+5+7+1)(3+5+7+9+1)*(4+8+6+0+2))*

Pour les mutiples de 7, ça donne une chaîne de longueur 18003 :-(

Exercice : trouver une expression décrivant len entiers divisibles par 7, mais lus à l'envers ! Après avoir expliqué à mes spés comment faire ça de façon générique, l'un d'eux a remarqué que dans ce cas précis, on pouvait se contenter d'un automate (déterministe) à 7 états, plutôt que les 42 de la construction «générique»

J'obtiens alors pour les multiples de 2 :
(0+4+6+2+8+(6+0+4+2+8)(5+3+9+7+1)*(7+1+3+9+5))*

Et pour les multiples de 7… une chaîne de longueur 18003 \o/

Le Rodeur (2011-04-28T17:11:12Z)

Hubert --> Effectivement, cela semble un problème insoluble.
J'ai entendu parler de cette question de concours, elle a même un coefficient non négligeable. Elle est associée à la ''trafic-jam theory'': une même population de candidats aura grosso-modo un même comportement, et donc des réponses (N) très similaires: -> toutes rejetées en haut du paquet…
Il serait bien que David nous dise quel N il aurait choisi, mais je crains qu'il ne réponde pas, vu qu'il réagit peu aux commentaires.
Pour ma part j'aurais choisi N=10.

blagor (2011-04-28T11:01:42Z)

@Hubert : ce problème a-t-il vraiment une solution ? Autrement dit, y a-t-il un choix meilleur que les autres ? Car si oui, les 4000 candidats le choisiront et personne n'aura gagné. (C'est un peu le paradoxe de bison futé : si tous suivent ses conseils, le bouchon est juste déplacé.) Enfin, il doit y avoir une subtilité qui m'échappe.

hijodelachingada (2011-04-28T00:49:10Z)

@blagor : voici un test de primalité basé sur une expression rationnelle.

$_ x '?' =~ /^(\?\?+)$/

:-p

PS : désolé, David, cela doit être la première fois qu'une émoticone est utilisée dans ton blog !

Hubert (2011-04-26T19:35:45Z)

Le Ruxor, il est fascinant mais néanmoins intéressant de voir à quel point tu te triture les neurones pour des problèmes à priori sans intérêt … J'ai bien aimé le ''defi métro'' que tu relates sur tes pages. Que penses tu de celui-ci:
Une université Californienne fait sensation depuis 1998 avec cette question, ajoutée aux épreuves d'entrée : chaque candidat (sur 4000) doit choisir un nombre entier N, positif ou nul. Si n candidats choisissent un même N, il est alors remplacé à chaque fois par N+n. Le but est d'obtenir un N final le plus bas possible …
Quel serait ton choix ? (les lecteurs peuvent participer). Je sais que tu vas me dire qu'il suffit de connaître la courbe des réponses d'une année pour se faire une idée … mais ce n'est pas communiqué, héhéhé !!
La deuxième question est : quelle est la moyenne des N initialement choisis ?

blagor (2011-04-26T19:30:17Z)

As-tu une expression régulière pour les nombres premiers ?

Blague à part, peut-on construire une telle expression régulière pour n'importe quel nombre premier, 13 par exemple (sans tenir compte de la longueur de l'expression bien sûr) ?

mokmok (2011-04-26T15:55:51Z)

Moi ce qui me fascine c'est que cette expression régulière soit finie.

valerio (2011-04-26T11:56:43Z)

Ah, enfin un critère de divisibilité par 7, qui dispense d'effectuer la division!

Fork (2011-04-26T11:23:37Z)

Quelle idée farfelue ! Et diablement illisible effectivement.
Pour ce qui est d'arriver à une expression différente, est-ce que les méthodes DFA -> regex donnent toutes le même résultat ? Parce que si oui, en minimisant ton automate de départ y a pas de raison que tu arrives sur quelque chose de différent (mais tu y a sûrement pensé) ?

jonas (2011-04-26T08:03:54Z)

Did you try making both a finite automaton that recognizes numbers divisible by 7, and one that recognizes reversed numbers divisible by 7, converting both to regular expressions (reversing the second one) and taking the shorter of the two?
Is one of these significantly shorter than the other?

Ruxor (2011-04-25T22:05:10Z)

Vicnent → Oui, l'automate est un automate à 7 états (les 7 congruences possibles mod 7 du nombre lu jusqu'à ce point-là). Et non, on ne peut pas faire une conversion base 10 vers base 7 par automate fini (par exemple, on ne peut pas écrire un automate fini qui reconnaît les nombres en base 10 dont l'écriture en base 7 comporte deux 1 consécutifs, ou en fait toute autre expression régulière qui ne se ramène pas, justement, à de simples congruences).

Vicnent (2011-04-25T21:43:21Z)

tu as utilisé quoi comme automate ? (un bête calcul de mod avec reste nul ?)

Sinon, n'y a-t-il pas moyen de faire : vérifier la présence du 0 terminal en base 7 ?