なぜ素数をサンプリングするこれら2つの方法が等しく実行されるのでしょうか？

Question

私は自分の小さなRSAアルゴリズムを実装しており、その過程で大きな素数を見つける関数を書いています。
最初に私は素数をテストする関数prime?を書いた後、素数探索関数の2つのバージョンを書いた。最初のバージョンでは、私がプライムを打つまでランダムなBigIntegersをテストします。 2番目のバージョンでは、ランダムなBigIntegerをサンプリングしてから、それを増やしてプライムを見つけます。このコードを実行

(defn resampling [] 
    (let [rnd (Random.)] 
    (->> (repeatedly #(BigInteger. 512 rnd)) 
     (take-while (comp not prime?)) 
     (count)))) 

(defn incrementing [] 
    (->> (BigInteger. 512 (Random.)) 
     (iterate inc) 
     (take-while (comp not prime?)) 
     (count))) 

(let [n 100] 
    {:resampling (/ (reduce + (repeatedly n resampling)) n) 
    :incrementing (/ (reduce + (repeatedly n incrementing)) n)}) 

はインクリメント機能のためのリサンプリング機能と310.74のために332.41の2回の平均値を得ました。
最初の数字がわかりました。 prime number theoremは、nの第一の素数は約n*ln(n)（ここではlnは自然対数）であると述べています。したがって、隣接する素数の間の距離は約n*ln(n) - (n-1)*ln(n-1) ≈ (n - (n - 1))*ln(n) = ln(n)（大きい値の場合はnln(n) ≈ ln(n - 1)）です。私は512ビットの整数をサンプリングしているので、素数間の距離がln(2^512) = 354.89の近くにあると思います。したがって、無作為サンプリングは、プライムを打つ前に平均して約354.89回の試行が必要です。これはきわめてうまくいきます。
私のためのパズルは、インクリメント機能が多くのステップと同じくらいかかっている理由です。素数が355単位離れているグリッドにダーツを投げると想像すれば、平均して2つの素数の間に中心を置くので、次のより高い素数まで歩くには平均して半分程度しかかかりません。

（prime?のコードは少し長いです。あなたはそれhereを見てみることができます。）

Answer 1

あなたは素数が等しく場合ではないと思われる、分散されていることを前提としています。

次のようなシナリオを考えてみましょう。素数が常に10...01と10...03のようにペアになる場合、次のペアは2*ln(n)になります。サンプリングアルゴリズムの場合、この分布は違いはありませんが、インクリメントアルゴリズムの場合、そのようなペアの内側で開始する確率はほぼ0であるため、平均で大きな距離の半分、つまりln(n)にする必要があります。

一言で言えば、インクリメンタルアルゴリズムの動作を見積もるには、素数間の平均距離を知るだけでは不十分です。