

それぞれある周期で循環する0と1の数列があります。

例：  
010101010101...(周期2)  
001100110011...(周期4)  
000111000111...(周期6)

ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。  
上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。

最初の列番号を求める方法は今のところ、各数列で周期内の何番目の1を選ぶかの組み合わせを全て試し、それぞれの組み合わせに対して連立合同式を解いて最小の列数を求め、全体の最小値を更新していくバックトラック法しか思いつきません。  
割合を求める方法は、全周期の最小公倍数の列数までに1が揃う列を1つずつ数える方法しか思いつきません。

・これは名前のついた問題ですか？  
・この問題はNP困難ですか？数列の数が増えても速く計算する方法はありますか？  
・0、1が続く区間や循環する周期の長さを有理数や無理数に拡張した場合はどう計算しますか？


CC BY-SA 4.0
2022-02-13T07:50:46.880
86310
2022-02-18T07:48:11.230
51403
question
アルゴリズム
区間が重なるタイミング


> ・この問題はNP困難ですか？

いいえ。多項式時間で解ける問題と思います。

Pythonによるアルゴリズム実装例です：<https://wandbox.org/permlink/8R5tfdstFdRV4NTG>

[code]

    import math
    from fractions import Fraction
    
    def solve(q):
      period = math.lcm(*[e[0] + e[1] for e in q])
      acc = (1 << period) - 1
      for e in q:
        dist = sum([1 << m for m in range(0, period, e[0] + e[1])])    
        bits = ((1 << e[1]) - 1) * dist
        acc &= bits
        print('{}+{} {:0{}b}'.format(*e, bits, period))
      print('acc {:0{}b}'.format(acc, period))
      msb = 1 + period - acc.bit_length()
      ratio = Fraction(bin(acc).count('1'), period)  # acc.bit_count() since Python3.10
      return (msb, ratio)
    
    # 問題を(1個の0, 1個の1), ... と定義
    q = [(1,1), (2,2), (3,3)]
    ans = solve(q)
    print(ans)
    # 答え=(4, Fraction(1, 6))
    
[/code]


CC BY-SA 4.0
2022-02-18T07:48:11.230
86434
2022-02-18T07:48:11.230
49
86310
answer