はじめに

これは、シクシク素数列 Advent Calendar 2018を題材として、2018年のBrainf**k納めとして作成したものです。

ルール

数値に4か9を含む素数をシクシク素数と呼ぶことにします
- 19とか41とか149とか。
標準入力として正の整数 N を与えたら N 番目までのシクシク素数を半角カンマ区切りで標準出力してください
- 例 N = 9 の場合、 19,29,41,43,47,59,79,89,97
N は最大で 100 とします

なぜ改めてBF?

Advent Calendar では、@hogefuga さんがトリでBrainf**kを担当されたのですが、

※記事より抜粋

シクシク素数のリストをコードに埋め込む

空白・改行を取り除けば2299バイトです。

この方法が一番効率がよく、コードの量も少なくて済みます。

こちらより文字数を減らすことはできそうだな、と感じたからです。
また、普段はbffの32bit処理系をメインにしていますが、たまにはbf等の8bit処理系にも対応してみるのもいいかな、という気もありました。
※実を言うと、4,9の桁を見るためにもともと10進数で管理した方が良いので、別に8bitでも困らなかったという事情があります。

実装例

用意した実装

今回、2種類の実装emb,tryを用意しました。
いずれも、bff(32bit版処理系), bf(8bit版処理系)で実行できました。

なお、余分な文字を除いたコード文字数はそれぞれ672B,832Bでした。

動作確認

$ tr -dC '<>[],.+-' < 49-emb.bf | wc -c # 文字数確認
672
$ tr -dC '<>[],.+-' < 49-try.bf | wc -c # 文字数確認
832
$ bff 49-emb.bf <<< 100; echo
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319
$ bf 49-emb.bf <<< 100; echo
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319
$ bff 49-try.bf <<< 100; echo
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319
$ bf 49-try.bf <<< 100; echo
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

まずは楽に

と言いつつ、なんだかんだ言って100個のデータだったら埋め込む方が楽で文字数も少ない(672B)、というのは確かでした。
ただ、各桁をそのまま持つと文字数が嵩むので、次のように考えました。

2,3以外の素数は6n-1あるいは6n+1のどちらかで表されることを利用し、6n-1,6n+1のどちらのタイプか、nの数字が何かの2パラメータで素数を管理する
単調増加の素数を扱うので、差分データのみを保持する

49-emb.bf(672B)

** input and parse N **
>>>>>>>>,+[
 +[>[+>>]<[>----------->]<<-]
 >[<<+[->>++++++++++<<]>>>,+>]
<]--
** embedded prime number parameters **
>>++>>+>+>+>>->>>+>+>>++>>+>>>+>+>+>++++>>+>+>++++>+>+>>->>>>->+>++++>>+>>->>++++>+>+++>+>++++++++>>->>+>>++>>+>>>>>>>>+>>->>+>>->+>>>>+>>>>>>>->>>+>+>>>>>>>>+>>++++>+>>>+++>+>+++>+>>>++>>+++>>->>>+>+>>++++>+>++>>+>>++>>>>+++>>++++>+>+>>++>>+>>++>+>+++++++>>>>>>+>>>>>+>>+>>>+>>>+>>+>>>>+>>+>+>>+>>++>>+>>++>>+++>>->>>+>+>>++>>++++++++++>+>+++++>>++>>+>>++>>+>>->+>>>+++
++[--<++]
<[
 ** cumulation and decide the prime type ( 6n plus 1 or minus 1 ) **
 >>+[-<+>[-<-]<[<]>>>]<[->>>+<<<<<++>>]
 ** linked multiplication by 6 and resumable divmod by 10 **
 >>+[-
  >>+<<<<<<++++++[<[+<<]>[<---------<<<+>>]>>-]
 >>>>]
 ** slinding divmod by 10 loop **
 <+<<<<<<<-[+
  [<[+<<]>[<---------<<<+>>]>>-]
 <<<<-]
 ** print a prime **
 >>>-[
  <++++++[->++++++++++<]>--.,+
 >>>>-]
 ** print comma **
 <<-[[->>+<<]++++[->+++++++++++<]>.,+]
>]

ところで、8bit処理系で問題になるところとしては、6nを計算するところ、素直にやると256でのオーバーフローが発生してしまいます。
そこで、10進数変換の最初のdivmod 10と6での掛け算をリンクさせました。divmodの計算はresumable(再開可能)なようにできていて、divmod→+6 をループさせることで、オーバーフローを起こすことなく×6とdivmodを同時にこなすことができたのです。

まじめに試し割り

ということで? 一応ここからが本番。

今回、最大の素数は1319ということで8bitではオーバーフローしてしまいます。そのため、4,9の桁を見るためにも10進数での管理は必須です。
しかし、素数判定の試し割りを行う際、最大の除数はせいぜい35で済み、こちらまで10進数で管理する必要はありません。そのため割り算の処理もそれほど大変ではありません。

なので、832Bで実装することができました。

rubyでの抽象コード

まず、BFのコードを示す前に、どのように考えたかrubyでの抽象コードを示します。

基本的なアイデアは、4,9の桁については10の位以上の桁で考えるということです。
10の位以上の桁になければ、1の位は9のみと確定しますし、そうでなければ1の位として1～9の5通り ( 5は実際にはないが抜くのが手間なのでまとめて扱う ) と候補を絞ることができます。

1の位の候補を全て試したら、10の位をインクリメントしつつ、4,9の桁の数を更新するようにループを構成します。

49-try.rb

# n: 入力(出力する素数の数)
# m: 判定中の数の10以上の位の桁での4or9の数
# c: 1の位の桁のループカウンタ
# a: 判定中の数の各桁 ( 1の位の桁～ )
n=gets.to_i
m=c=0
a=[]
# メインループ
while n!=0
  if c==0
    # 10の位の桁をインクリメント
    1.step{|i|
      cont=false
      if !a[i]
        a[i]=1
      else
        case a[i]+=1
        when 10; a[i]=0; m-=1; cont=true
        when  9; m+=1
        when  5; m-=1
        when  4; m+=1
        end
      end
      break unless cont
    }
    # 10以上の位で4or9があれば1の位は1～9、さもなくば9のみ
    c,a[0]=m==0 ? [1,7] : [5,-1]
  else
    # 1の位を2増やして試し割りで判定
    # d: 試し割りする除数、ただし-1なら(素数として)出力
    c-=1
    a[0]+=2
    d=3
    x=a.each_with_index.reduce(0){|s,(e,i)| s+e*10**i }
    while d!=0
      if d==-1
        print(x)
        n-=1
        print(",") if n!=0
        d=0
      else
        q,r=x.divmod(d)
        diff=q%100-d
        diff=4 if q>=100  # qが十分大きいと判断
        if r==0 # 合成数と判明
          d=0
        elsif (-1..3).include?(diff) # 試し割り終了
          d=-1
        else # 試し割り続行
          d+=2
        end
      end
    end
  end
end

BFコード

ということで、これがBF実装コードです。
そのまま上の抽象コードの通りなのですが、割り算で上位の余りを×10して下位に伝播するとき、単純にやると8bitの範囲をオーバーフローしてしまうので、埋め込み版のコードと同じく、resumable な divmod を活用しています。

ちなみに、10進で管理している各桁Xは7セルおきに配置し、試し割り、あるいは出力時には各隣接セルYにコピーしてそちらを使い捨てます。7セルおきは、divmodができる最低ライン ( X,Y,D,r,Q,作業余白2マス ) で決めたものです。
初期配置としては、N_CM*X______* で、Nが素数出力個数のカウンタ、Cが1の位のカウンタ、Mが4,9の桁の数(初期値0)、Xは1の位のみ(0)、各*が端検知用のマーク(-1)です。桁が増える毎に、右側に上位桁を伸ばしていきます。

49-try.bf(832B)

** input and parse N **
>,+[
 +[>[+>>]<[>----------->]<<-]
 >[<<+[->>++++++++++<<]>>>,+>]
<]
+>>>->>>>>>>>--[+<-]<[N
 >>C[-
  >>>X++>>>F+++[+
   ** dup each X to Y **
   <<<+[X-[->+>+<<]>>[-<<+>>]>>>>>+]*-<+[-<+]*-
   >>>T+>F[-
    ** should try to div **
    ** move D(F) near to the most significant digit **
    F[->-[->+]*>>D+<<*+[--<++]<F]
    <T[->+]*-<+[-
     >>>D[-<<<<<<<D+>>>>>>>D]
     <R+[-
      >+<R[<<<<<<<Y++++++++++>>>>>>>R>-]>[->]<<R
      ** resume divmod **
      <<<<<<<Y[->-D[>r+>>]>[r+[-<D+>]>Q+>>]<<<<<Y]
     >>>>>>>R]
     R<<<<<r[-<D+YR<+>>r]
    <<Y<<+]
    ->>>>>>>>>>>>Q10[-<<<<<<<Q1++++++++++>>>>>>>]
    ** reduce higher digits of Q to 0 or 1 **
    <->+[->+]*-<<<Q<+[
     >Q[[-]<-<<<<<<Q+>>]
     <[-<<<<<]
    <Q<+]>[-<<<<<<+>>>>>>]
    ** decide next D **
    <<<<<<<<<<R[,+
     ** if not divisible **
     ** restore D and calculate Q minus D ( or fixed value if Q is too large ) **
     >[->D+>Q-<<]>>>[-<Q,+++++>]
     ** proved to be prime if Q minus D in minus 1 thru 3 **
     +<Q+[-[-[-[-[,+>-<<D++>]]]]]>[-<<D,>>]
    <<<<]
    ** clear various values if divisible **
    >[,+>>,+>,+<<<]
   ]
   <[
    ** proved to be prime **
    [->+]*-
    ** print a prime number **
    <+[-
     <<<<++++[-<Y++++++++++++>]<Y.,+
    <<+]*
    ** print a comma **
    -<<<+<N-[>+++[-<<+++++++++++>>]<<.,+<]>[-<<]
   >>>>>>X>Y]
  >>F]
 <<<<*<<<<N<]
 >>[*
  ** do increment **
  >X,+>>>>>>+>X+[----[-[----[-[
            ++++++                  <-   * else *
      ]<[ ->      >>>>---->->+>+ <<<<<]  *  10  *
     >]<[ ->+++++         >+       <<<]  *   9  *
    >]<[  ->+             >-       <<<]  *   5  *
   >]<[   ->              >+       <<<]  *   4  *
   >>++++>[+[--
     -[-<+]*<M++>+[-->++]  ** 4 or 9 **
    ]
     -[-<+]*<M- >+[-->++]  ** 4 or 5 or 9 or 10 **
   ]
  >>]<[
   ** extend digits **
   ->*+>>>>>>>*-
  <<]
  +[-<+]*-
  ** decide the next C and the initial leftmost X **
  <M[<C++++>>>]>[>X++++++++>]<X-<<<C+
 <]
<N]

おわりに

ということで、2018年のBrainf**k納めでした。
来年も良いおBFを!!

2018年Brainf**k納め～シクシク素数列～