<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'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"><<a href="mailto:mechvel@botik.ru" target="_blank">mechvel@botik.ru</a>></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>
> Here is a concrete example.<br>
> Goal: find the first prime after a given prime p : ℕ.<br>
><br>
> firstPrimeAfter :<br>
> (p : ℕ) → IsPrime p →<br>
> (∃ \q → p < q × IsPrime q × NoPrimeBetween p q)<br>
</span>> [..]<br>
<span class=""><br>
> bound p = let ps = p1, p2, ..., p -- all primes up to p<br>
> a = product ps -- = p1 * p2 * ... * p<br>
> b = 1 + a<br>
> in<br>
> firstNonUnityFactor b<br>
><br>
<br>
<br>
> It is proved in Agda that p < bound p and IsPrime p.<br>
</span>> [..]<br>
<br>
<br>
Sorry, fixing a typo:<br>
<br>
It is proved in Agda that p < 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>