スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#雑記 EKG Sequence

 anarchy golfに次のような問題があったのでやってみました。
EKG数列というのは初項と第2項が1,2でここより先は、前項と互いに素でない最小の自然数(ただしそこまでに数列に出てきていない自然数数)を続けていくことで作り上げていく数列です。 
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ... 
というようになります。 
こちらにはグラフもあります。)
 
では準備です。 
まず最大公約数を返す関数を定義します。 
 
> //最大公約数を求めるための補助(前提条件 m>=n) 
//返り値 m と n の最大公約数 
let rec hcfSub m n = 
    if n = 0 then 
        m 
    else 
        let r = m % n  
        if r = 0 then 
            n 
        else 
           hcfSub n r ;; 
 
val hcfSub : int -> int -> int 
 
(実行例) 
> hcfSub 18 4;; 
val it : int = 2 
 
> //最大公約数を求める 
let hcf m n = 
    if m >= n then 
        hcfSub m n 
    else 
        hcfSub n m ;; 
 
val hcf : int -> int -> int 
 
(実行例) 
> hcf 9 21;; 
val it : int = 3 
 
ではこれを利用して互いに素ならtrueそうでなければfalseを返す関数を定義します。 
 
> //ニ数が互いに素かどうかを返す 
let isCoprime m n = 
    let hcfResult = hcf m n 
    if hcfResult = 1 then  
        true 
    else 
        false;; 
 
val isCoprime : int -> int -> bool 
 
(実行例) 
> isCoprime 7 8;; 
val it : bool = true 
> isCoprime 20 8;; 
val it : bool = false 
 
次に自然数全体の数列を定義します。 
 
> let naturalNumSeq = Seq.unfold (fun n -> Some(n,n+1)) 1;; 
 
val naturalNumSeq : seq<int> 
 
(例) 
> Seq.take 15 naturalNumSeq;; 
val it : seq<int> = seq [1; 2; 3; 4; ...] 
 
では目的の数列の3項目以降をSeq.unfoldを利用して定義します。 
 
> let EKGform3 =  
        Seq.unfold 
             (fun (curSet,prevNum) -> 
                  let nextNum = Seq.find (fun x -> (not(Set.contains x curSet)) && (not (isCoprime x prevNum))) naturalNumSeq 
                  let nextSet = Set.add nextNum curSet 
                  Some(nextNum,(nextSet ,nextNum))) 
             ((Set.ofList [1;2]),2) ;; 
 
val EKGform3 : seq<int> 
 
初項と第2項を付け足して目的の数列にします。 
 
> let EKGSeq = Seq.append (Seq.ofList[1;2]) EKGform3;; 
 
val EKGSeq : seq<int> 
 
では1000項まで表示してみます。 
 
> Seq.iteri (fun i x ->  
                if i % 10 = 0 then printfn "" 
                printf " %4d" x)  
          (Seq.take 1000 EKGSeq);; 
 
    1    2    4    6    3    9   12    8   10    5 
   15   18   14    7   21   24   16   20   22   11 
   33   27   30   25   35   28   26   13   39   36 
   32   34   17   51   42   38   19   57   45   40 
   44   46   23   69   48   50   52   54   56   49 
   63   60   55   65   70   58   29   87   66   62 
   31   93   72   64   68   74   37  111   75   78 
   76   80   82   41  123   81   84   77   88   86 
   43  129   90   85   95  100   92   94   47  141 
   96   98   91  104  102   99  105  108  106   53 
  159  114  110  112  116  118   59  177  117  120 
  115  125  130  122   61  183  126  119  133  140 
  124  128  132  121  143  154  134   67  201  135 
  138  136  142   71  213  144  146   73  219  147 
  150  145  155  160  148  152  156  153  162  158 
   79  237  165  168  161  175  170  164  166   83 
  249  171  174  172  176  178   89  267  180  182 
  169  195  185  190  184  186  188  192  189  196 
  194   97  291  198  187  204  200  202  101  303 
  207  210  203  217  224  206  103  309  216  208 
  212  214  107  321  222  218  109  327  225  205 
  215  220  209  228  226  113  339  231  234  221 
  238  230  232  236  240  235  245  250  242  244 
  246  243  252  248  254  127  381  255  258  256 
  260  247  266  259  273  261  264  253  275  265 
  270  262  131  393  276  268  272  274  137  411 
  279  282  278  139  417  285  280  284  286  288 
  290  292  294  287  301  308  296  298  149  447 
  297  300  295  305  310  302  151  453  306  289 
  323  304  312  299  322  314  157  471  315  318 
  316  320  324  326  163  489  330  319  341  352 
  328  332  334  167  501  333  336  329  343  350 
  325  335  340  338  342  344  346  173  519  345 
  348  351  354  356  358  179  537  357  360  355 
  365  370  362  181  543  363  366  364  368  372 
  369  375  378  371  385  374  376  380  361  399 
  384  382  191  573  387  390  377  403  416  386 
  193  579  396  388  392  394  197  591  402  398 
  199  597  405  395  400  404  406  408  391  414 
  410  412  418  407  429  420  413  427  434  422 
  211  633  423  426  424  428  430  415  425  435 
  432  436  438  440  442  444  441  448  446  223 
  669  450  445  455  460  437  456  452  454  227 
  681  459  462  451  473  484  458  229  687  465 
  468  464  466  233  699  474  470  472  476  469 
  483  477  480  475  485  490  478  239  717  486 
  482  241  723  492  488  494  481  507  495  498 
  496  500  502  251  753  504  497  511  518  506 
  508  510  493  522  512  514  257  771  513  516 
  520  505  515  525  528  517  539  532  524  526 
  263  789  531  534  530  535  540  536  538  269 
  807  546  533  559  572  542  271  813  549  552 
  529  575  545  550  544  527  558  548  554  277 
  831  555  560  553  567  561  564  556  562  281 
  843  570  551  580  565  585  576  566  283  849 
  582  568  574  578  584  586  293  879  588  581 
  595  590  592  594  583  605  600  596  598  602 
  604  606  603  609  612  608  589  620  610  614 
  307  921  615  618  616  622  311  933  621  624 
  611  637  623  630  625  635  640  626  313  939 
  627  636  628  632  634  317  951  639  642  638 
  644  646  629  663  645  648  650  652  654  651 
  657  660  649  671  682  656  658  662  331  993 
  666  664  668  670  655  665  672  674  337 1011 
  675  678  676  680  684  686  679  693  690  667 
  696  688  692  694  347 1041  702  689  715  685 
  695  700  698  349 1047  705  708  704  706  353 
 1059  711  714  697  731  748  710  712  716  718 
  359 1077  720  722  703  740  724  726  728  707 
  721  735  725  730  732  729  738  734  367 1101 
  741  744  713  736  742  746  373 1119  747  750 
  745  755  760  752  754  756  749  763  770  737 
  759  762  758  379 1137  765  768  764  766  383 
 1149  774  772  776  778  389 1167  777  780  767 
  793  806  775  785  790  782  784  786  783  792 
  781  803  814  788  794  397 1191  795  798  779 
  817  836  796  800  802  401 1203  801  804  808 
  810  805  791  812  816  799  833  819  822  818 
  409 1227  825  815  820  824  826  828  830  832 
  834  837  840  835  845  850  838  419 1257  846 
  842  421 1263  852  844  848  854  847  858  855 
  860  856  862  431 1293  861  864  866  433 1299 
  867  870  841  899  868  872  874  851  888  873 
  876  878  439 1317  882  875  865  880  869  891 
  885  890  884  871  897  894  886  443 1329  900 
  892  896  889  903  906  898  449 1347  909  912 
  893  931  910  895  905  915  918  901  935  902 
  904  908  914  457 1371  924  913  946  916  920 
  922  461 1383  927  930  925  940  926  463 1389 
  936  923  949  962  928  932  934  467 1401  942 
  938  917  945  948  944  950  952  954  956  958 
  479 1437  957  960  955  965  970  964  966  943 
  984  963  969  972  968  974  487 1461  975  978 
  976  980  959  973  987  981  990  979 1001  988 
  982  491 1473  996  986  992  961 1023  999 1002 
  994  998  499 1497 1005  985  995 1000 1004 1006 
  503 1509 1008 1010 1012  989 1032 1014 1016 1018 
  509 1527 1017 1020 1003 1037 1054 1022 1015 1025 
 1030 1024 1026 1007 1045 1034 1028 1036 1029 1035 
 1038 1040 1027 1053 1044 1042  521 1563 1050 1043val it : unit = () 
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

typo

最小公倍数を返す関数

No title

どーもです。訂正しました。
プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。