問題タブ [number-theory]

乱数シードを範囲の1つの境界に向かって歪める方法について、今日早くこの回答を得ました。

しかし、それは明らかに指数曲線に沿ってそれを歪めます。どうすればそれを線形にすることができますか？

また、関連性があります。さまざまな種類の分布を視覚化するために、この単純なスクリプトを作成しました。この質問に役立つかもしれません：http：//jsfiddle.net/RTbrL/

ここにあるPEからの質問の数に驚いています。さて、私は解決策を望んでいませんが、問題402の正しい方向へのある種のヒントが欲しいです。

S（N）の閉じた形の解を見つけることができませんでした。これは私が得た限りで、かなりのループです。

これで、Fib（N）mod1e9が定期的であるなどのことがいくつかわかりました。ピサーノピリオドを見てください。S（N）にもピリオドがあります。

ビットシフトまたはビットごとの演算子のみを使用して、整数を別の整数 (両方とも正) で割って剰余を取得する方法を知りたいです。/operator またはoperatorは%使用しないでください。

たとえば、除数が次の形式の剰余を取得するには2^k、次の操作で剰余が得られます。

m = Remainder

n = The number

d = The divisor

m = n & ( d - 1 )

ただし、このメソッドdは が の形式の場合にのみ機能し2^kます。の累乗以外の同様の方法を知りたいです2。私は現在問題に取り組んでおり、programming challengesプログラムの実行時間を短縮するためにそのような方法を採用したいと考えています

シュノール群生成子を見つけるには、次のような 3 つの数 p、q、r を見つける必要があります。

• p = qr + 1
• p と q は素数

p と q が非常に大きな素数でなければならない場合、すべての基準を満たす q と r を見つけることは非常に困難です。GNU GMP ライブラリを使用して q と r をランダムに見つけようとしましたが、ラップトップで 30 分間見つけた数字で上記の基準を満たすものはありませんでした。

そのような数とショール群ジェネレーターを見つけるための高速な方法はありますか?

ありがとう！

m, m より小さい n と互いに素な数を数える

(phi(n)/n)*mでこれを行うことを考えましたが、常に小さなエラーが発生します。

包含と排除の原則を使用する方法もありますが、それよりも優れたアルゴリズムを探しています。

例えば

整数nが与えられた場合、φ（x）=nとなる最小の整数xを見つけます。

（10 ^ 5 <n <10 ^ 8）

検索の下限はn+1で、上限は

n /（（pow（e、0.577）* log（log（n）））+（3.0 /（log（log（n）））））

同じことをするための他の方法を教えてください。

ありがとう。

更新：C（n、k）はBinomial Coefficient

私は数論の問題を扱っています。私は大きな問題を単純な問題に変換しました： 計算方法C(n,k)%3、n <= 10^15。1秒m ( <= 10 000 )以内に計算するために必要なデータセットについてあります。

私がそれを解決する方法は、を使用することですLucas' theorem。ですO(m log n)。そして、それは問題を解決するのに十分速いです。しかし、私はこの問題に対するより良い解決策があるかどうか、さらにはn <= 10^100それともm <= 1 000 000？

どうもありがとう！

この質問がサイトにうまく当てはまらない場合は申し訳ありません... Maple コードの一部を Mathematica に変換しようとしています。Maple はまったく知りませんが、Mathematica は少し知っています。私は自分が何をしているのか本当にわからないので、誰かが私を少し助けてくれるのではないかと思います:

以外はすべて理解していると思います

確信はないけど。前もって感謝します！

セット内の整数の間に発生する可能性のある正の整数の数を減らすために、厳密に増加する (または厳密に減少する) 正の整数 P のセットをどのように再コーディングしますか?

なぜこれを行う必要があるのでしょうか: P をランダムにサンプリングしたいとしますが、1.) P は大きすぎて列挙できません。2.) P のメンバーは非ランダムな方法で関連付けられていますが、サンプリングするには複雑すぎます。に。ただし、P のメンバーは、見ればわかります。P[0] と P[n] はわかっているが、P のすべてを列挙したり、P のメンバーがどのように関連しているかを正確に理解したりするという考えを受け入れることができないとします。同様に、P[0] と P[n] の間で発生するすべての可能な整数の数は、P のサイズの何倍も大きく、P のメンバーをランダムに描画する可能性は非常に小さくなります。

例: P[0] = 2101010101 & P[n] = 505050505 とします。おそらく、特定の品質を持つ P[0] と P[n] の間の整数 (たとえば、P[x 内のすべての整数) ] の合計が Q 以下になる場合、P の各メンバーは最大の整数として 7 以下になります)。したがって、すべての正の整数 P[n] <= X <= P[0] が P に属するわけではありません。私が興味を持っている P については、以下のコメントで説明します。

私が試したこと: P が厳密に減少するセットであり、P[0] と P[n] がわかっている場合、各メンバーを P[0] から減算されたかのように扱うことができます。そうすることで、各数値がおそらく大幅に減少し、各メンバーが一意の整数として維持されます。私が興味を持っている P (以下) については、P の各減少値を共通の分母 (9,11,99) で割ったものとして扱うことができます。これにより、P のメンバー間で可能な整数の数が減少します。これらのアプローチを組み合わせて使用​​すると、すべての P[0] <= X <= P[n] のセットが数桁減少し、すべての正の整数 P[n ] <= X <= P[0] まだ非常に小さいです。

注: 明らかなように、P について何かを知っている必要があります。そうでない場合、それは基本的に、何を探しているかの手がかりがないことを意味します。P[0] と P[n] (記録されているかどうかに関係なく) の間の整数をランダムにサンプリングするとき、実際にそうである場合、「うん、それは P に属している」と言うことができる必要があります。

良い答えは、私が開発したコンピューティング アルゴリズムの実用的なアプリケーションを大幅に向上させる可能性があります。私が興味を持っている種類の P の例は、コメント 2 に示されています。