まもめも

主に素数大富豪に関することを書いていきます

1001チェックが通らなかった場合のカードの入替えについて

この記事は、 素数大富豪 Advent Calendar 2022 - Adventarの2日目の記事です。
昨日は二世さんによる、2022年の素数大富豪でした。
今年も色々なイベントがありましたね。

素数かどうかわからない数を出すときに、1001チェックや91チェックを行う場合があります。
1001チェックでは7 or 11 or 13の倍数かどうかが判別でき、91チェックでは7 or 13の倍数かどうかが判別できます。
1001チェックや91チェックの結果、7 or 11 or 13の倍数であることがわかった場合、札を並び替えて数を変える必要があります。

(1)11の倍数だった場合に再度11の倍数にならない方法
11の倍数には奇数桁の和と偶数桁の和の差が11の倍数になるという性質があります。
このため1001チェックの結果11の倍数だった場合、奇数桁の数と奇数桁の数を入替えたり、偶数桁の数と偶数桁の数を入替えても11の倍数のままなので、別の方法で数を並び替える必要があります。
なお札が全て2桁札の場合、どう並び替えても奇数桁の和と偶数桁の和は変わらないので11の倍数のままになります。

(2)7の倍数だった場合に再度7の倍数にならない方法
2つの数の場所を入替えた場合、元の数と入替えた後の数の差は次のようになります。

元の数が4桁の数abcdの場合 (a~dはそれぞれ1~9の任意の数)
①cとdを入替えてabcd→abdcとした場合 abdc-abcd=9×(d-c)
②bとdを入替えてabcd→adcbとした場合 adcb-abcd=99×(d-b)
③aとdを入替えてabcd→dbcaとした場合 dbca-abcd=999×(d-a)

2つの数字の場所を入替えた時、元の数と入替えた後の数の差は、2つの数字の差の倍数になります。
よって、入替えた2つの数字の差が7なら、元の数と入替えた後の数の差は7の倍数になります。

7の倍数に7の倍数を足し引きしても7の倍数のままなので、1001チェック等をした結果7の倍数だった場合、1と8、or 2と9を入替えても7の倍数のままになります。
このため7の倍数だった場合に数を入替える際は、1と8、or 2と9の入替えをしてはいけません。

なお上記③以降も桁を増やしていくと、掛ける数字が9999、99999、999999・・と9が増えていきます。
このうち「999999」は7と11と13倍数になります。
1001チェック等で引っかかった後にこの方法で入替えても7・11・13の倍数のままなので今回の記事では使い道はありませんが、この「999999」という数は別の使い道がありそうなので、詳しくは12月9日のAdvent Calendarに書きたいと思います。

(3)13の倍数だった場合に再度1001チェック等をしなくてすむ方法
(1)の方法で11の倍数だった場合に11の倍数にならないよう入替えても、入替えた後の数が7の倍数や13の倍数なってしまった可能性があるため、再度1001チェック等を行う必要があります。

(2)においても7の倍数だった場合に7の倍数にならないよう入替えても、入替え後の数が11の倍数や13の倍数なってしまった可能性があるため、再度1001チェック等を行う必要があります。

再度1001チェック等を行わずに済む方法はないでしょうか。
ここで、1001チェック等の結果13の倍数だった場合を考えます。
11の倍数ではない数に11の倍数を足しても11の倍数にならないこと、7の倍数ではない数に7の倍数を足しても7の倍数にならないことから、元の数と入替え後の数の差が7の倍数かつ11の倍数(77の倍数)であれば、再度1001チェック等を行わずに済みます。

元の数と入替え後の数の差を77の倍数にするためには、(1)と(2)を踏まえると、1と8、or 2と9を奇数桁同士又は偶数桁同士で入替えれば良いことがわかります。

例を上げると、次のようになります。
a8c1e→a1c8e
9b2de→2b9de

(4)再度1001チェック等を行わずに済む数列
7の倍数だった場合や11の倍数だった場合ですが、13の倍数だった場合の時に用いたような簡単な法則はありません。(多分)
このため法則に従って数を入替えるのではなく、13の倍数だった場合の入替えが可能であり、かつある並び替えだと91(7×13)の倍数になり、かつ別の並び替えだと143(11×13)の倍数になるような数列を探すことにします。

まとめると、探す数列の条件は次の4つです。
・13の倍数だった時用に、奇数桁同士又は偶数桁同士に1と8、or 2と9が含まれている
・11の倍数だった時用に、元の数と並び替え後の数の差が91(7×13)の倍数
・7の倍数だった時用に、元の数と並び替え後の数の差が143(11×13)の倍数
・並び替えが簡単であること

1001チェック等で時間を消費していることを想定し、並び替えが簡単であることを条件としました。
探索に当たり今回は10、J、Q、K、0は除外します。

        ・
        ・
        ・
(プログラムのスキルがないのでエクセルを使用)
        ・
        ・
        ・

探索の結果、「38415」「61584」「49526」「72695」の数列が見つかりました。

これら5桁の数字をabcdeとした時、次のようになります。
①13の倍数だった場合
1と8 or 2と9を入替えることによって、7と11の倍数ではないまま13の倍数ではなくすることができます。
②11の倍数だった場合
dを3つ前に移動しabcde→dabceと並び替えることによって、7と13の倍数ではないまま11の倍数ではなくすることができます。
③7の倍数だった場合
eを3つ前に移動しabcde→aebcdと並び替えることによって、11と13の倍数ではないまま7の倍数ではなくすることができます。

この並び替えをすることにより、1001チェックで引っかかっても再度1001チェックを行わなくても済むようになります。

(5)使用例
①「38415」を含んだ「9384151」が1001チェックの結果7の倍数だった場合
→eにあたる5を3つ前に移動させて「9358411」に並び替え

確認するとわかりますが、13で割った余りと11で割った余りは同じままで、7で割った余りが0ではなくなっています。

②「61584」を含んだ「27615841」が1001チェックの結果11の倍数だった場合
→dにあたる8を3つ前に移動させて「27861541」に並び替え

こちらも13で割った余りと7で割った余りは同じままで、11で割った余りが0ではなくなっています。

③「49526」を含んだ「843495263」が1001チェックの結果13の倍数だった場合
→奇数桁同士の9と2を入替えて「843425963」に並び替え

こちらも7で割った余りと11で割った余りは同じままで、13で割った余りが0ではなくなっています。

なお、並び替え後の数の「9358411」「27861541」「843425963」は3つとも素数ですが、素数になる数を意図して選んだだけなので、この方法で並び替えたら必ず素数になるというわけではありません。


(6)最後に
今回見つけた数は4つとも偶数のため末尾には置けないのが少し残念ですが、末尾以外の場所に置けばよく、使用している数も偶数が多めでバラけているので割と使いやすいのではと思っています。

明日はもりしーさんによる「素数で音楽を作ろう!」です。楽しみですね!