4

任意の値からループするカウンタ間の値が被らないことを確認したいのですが、その条件を出しかねています。
数学的にアプローチできると良いのですが、ネタも知識も不足しており、どのようにアプローチすれば良いのかも判断ついておりません。
どのように考えれば良いのかヒントとなる何かでも良いのでご教示いただけたら幸いです。


255までの数値を1~10個格納できる配列がある。格納した個数を格納数とする。
格納数分だけカウンタを用意する。
1回目の処理で各カウンタは1から順に値を与えられて初期化される。
このカウンタは、処理のタイミングでデクリメントされていき0になったら、対応する配列に格納された値に戻す。
この処理を延々繰り返しても、カウンタ間の値が被らないことを、配列に格納した数値から確認したいのですが...

配列に格納した数値、格納数、数値が格納された位置によっても被る、被らないが変化してしまうため、値から論理的に判断する術が見つかっていません。
何か判断する方法はないでしょうか?

e.g.)[6,8] 格納数2:被らない格納パターン
画像の説明をここに入力

e.g.)[6,6,8] 格納数3:被る格納パターン
画像の説明をここに入力


設定される値の条件として、以下のような条件であれば、10件設定されていてもカウンタが被る値になることはありません。
・格納数以上の値を設定
・格納される値は、最小値の倍数を設定

しかし、これはゆるい条件です。
件数が少なかったり、格納位置(index)によっても影響があるため、説明しきれていません。

0

1 件の回答 1

5

インデックスiの値を配列の要素をAi、
処理回数をtとしたときの、カウンターの値をCtiとすると、
Cti == Ctjであるとき、あるxについてCxi == Cxj == 1が成り立ちます。
この時、

x == C0i (mod Ai)
x == C0j (mod Aj)

となり、このようなxが存在するかどうかは、いわゆる中国の剰余定理(と少し応用)で求めることができます。

具体的にはAi, Ajの最大公約数をGとしたとき、C0i - C0j == 0 (mod G)が成り立つときにかぶりが発生し、そうでないとき発生しません。

3
  • すみません。最後の部分の0 (mod G)の部分をもう少し詳しく教えていただけないでしょうか?==は等価演算子という認識で良いのですよね?
    – 豚吐露
    2020年3月13日 5:25
  • 右辺と左辺をそれぞれGで割った余りが等しいというような意味でとらえてください。つまり、そこの部分に関してはGの倍数になるということです。
    – yudedako
    2020年3月13日 5:43
  • 右辺は0なので常に余り0ですね。なので左辺で計算してる差が最大公約数Gの倍数になっているとアウト!ということで認識しました。確かにそのようになりそうです。解答ありがとうございました。
    – 豚吐露
    2020年3月13日 8:45

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。