<div dir="ltr">A trick you can use is to skip checking the bound until after a finite (but possibly large) number of steps. Basically you write a fast search that takes a counter starting at a billion (say) that ignores the bound and only when that counter reaches zero do you switch to the slow search where you check the bound. For your example:<div><br></div><div><a href="https://gist.github.com/UlfNorell/f2d8674b1d6b98172827">https://gist.github.com/UlfNorell/f2d8674b1d6b98172827</a><br></div><div><br></div><div>Apologies for making a mess of the ordering proofs, I don&#39;t really know my way around the standard library.</div><div><br></div><div>/ Ulf</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Mar 28, 2016 at 5:48 PM, Sergei Meshveliani <span dir="ltr">&lt;<a href="mailto:mechvel@botik.ru" target="_blank">mechvel@botik.ru</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, 2016-03-28 at 16:46 +0300, Sergei Meshveliani wrote:<br>
&gt; Here is a concrete example.<br>
&gt; Goal: find the first prime after a given prime  p : ℕ.<br>
&gt;<br>
&gt;  firstPrimeAfter :<br>
&gt;       (p : ℕ) → IsPrime p →<br>
&gt;                 (∃ \q →  p &lt; q  ×  IsPrime q  ×  NoPrimeBetween p q)<br>
</span>&gt; [..]<br>
<span class=""><br>
&gt;  bound p = let ps = p1, p2, ..., p   -- all primes up to p<br>
&gt;                a  = product ps       -- = p1 * p2 * ... * p<br>
&gt;                b  = 1 + a<br>
&gt;            in<br>
&gt;            firstNonUnityFactor b<br>
&gt;<br>
<br>
<br>
&gt; It is proved in Agda that  p &lt; bound p  and  IsPrime p.<br>
</span>&gt; [..]<br>
<br>
<br>
Sorry, fixing a typo:<br>
<br>
 It is proved in Agda that  p &lt; bound p  and  IsPrime (bound p).<br>
<br>
<br>
------<br>
Sergei<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
<br>
_______________________________________________<br>
Agda mailing list<br>
<a href="mailto:Agda@lists.chalmers.se">Agda@lists.chalmers.se</a><br>
<a href="https://lists.chalmers.se/mailman/listinfo/agda" rel="noreferrer" target="_blank">https://lists.chalmers.se/mailman/listinfo/agda</a><br>
</div></div></blockquote></div><br></div>