スポンサーサイト

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

F#雑記 カプレカ数

 Gushwellさんの記事を見て、カプレカ数を求めるプログラムを書いてみました。 
 
カプレカ数の定義としては、「2乗して前の部分と後ろの部分(1以上)に分けて和を取ったとき、元の値に等しくなるもの」というものを採用してます。 
 
まず数字kを前の部分と後ろの部分に分けて、足してnになるかどうかを求める関数を定義します。 
 
> let rec kaprekarSub n k baseN = 
    let p1 = k / baseN 
    if p1 = 0I then 
        None 
    else 
        let p2 = k - p1 * baseN 
        if p1 + p2 = n && p2 > 0I then  
            Some(sprintf "%A + %A = %A" p1 p2 n) 
        else 
           kaprekarSub n k (10I*baseN) ;; 
 
val kaprekarSub : 
  System.Numerics.BigInteger -> 
    System.Numerics.BigInteger -> System.Numerics.BigInteger -> string option 
 
(使用例) 
 
> kaprekarSub 9I 36I 10I;; 
val it : string option = Some "3 + 6 = 9" 
 
> kaprekarSub 70I 367I 10I;; 
val it : string option = Some "3 + 67 = 70" 
 
> kaprekarSub 71I 367I 10I;; 
val it : string option = None 
 
これを使ってカプレラ数なら「分割の仕方を表す文字列」を返す関数を定義します。 
 
> let kaprekar n = 
    let n2 = n*n 
    let res = kaprekarSub n n2 10I 
    if res.IsSome then 
        Some((sprintf "%A : %A * %A = %A -> " n n n n2) + res.Value) 
    else 
        None ;; 
 
val kaprekar : System.Numerics.BigInteger -> string option 
 
(使用例) 
 
> kaprekar 297I;; 
val it : string option = Some "297 : 297 * 297 = 88209 -> 88 + 209 = 297" 
 
> kaprekar 142857I;; 
val it : string option = 
  Some "142857 : 142857 * 142857 = 20408122449 -> 20408 + 122449 = 142857" 
 
> kaprekar 1428587I;; 
val it : string option = None 
 
ではこれらを使って1から10000000までのカプレラ数を求めてみます。 
全コードは以下の通りです。(BigIntを使っているので遅いことこの上なしです。) 
 
let rec kaprekarSub n k baseN = 
    let p1 = k / baseN 
    if p1 = 0I then 
        None 
    else 
        let p2 = k - p1 * baseN 
        if p1 + p2 = n && p2 > 0I then  
            Some(sprintf "%A + %A = %A" p1 p2 n) 
        else 
           kaprekarSub n k (10I*baseN)  
 
let kaprekar n = 
    let n2 = n*n 
    let res = kaprekarSub n n2 10I 
    if res.IsSome then 
        Some((sprintf "%A : %A * %A = %A -> " n n n n2) + res.Value) 
    else 
        None          
 
 
for i in [1I .. 10000000I] do 
    let t = kaprekar i 
    if t.IsSome then 
        printfn "%s" t.Value  
         
(実行結果) 
 
9 : 9 * 9 = 81 -> 8 + 1 = 9 
45 : 45 * 45 = 2025 -> 20 + 25 = 45 
55 : 55 * 55 = 3025 -> 30 + 25 = 55 
99 : 99 * 99 = 9801 -> 98 + 1 = 99 
297 : 297 * 297 = 88209 -> 88 + 209 = 297 
703 : 703 * 703 = 494209 -> 494 + 209 = 703 
999 : 999 * 999 = 998001 -> 998 + 1 = 999 
2223 : 2223 * 2223 = 4941729 -> 494 + 1729 = 2223 
2728 : 2728 * 2728 = 7441984 -> 744 + 1984 = 2728 
4879 : 4879 * 4879 = 23804641 -> 238 + 4641 = 4879 
4950 : 4950 * 4950 = 24502500 -> 2450 + 2500 = 4950 
5050 : 5050 * 5050 = 25502500 -> 2550 + 2500 = 5050 
5292 : 5292 * 5292 = 28005264 -> 28 + 5264 = 5292 
7272 : 7272 * 7272 = 52881984 -> 5288 + 1984 = 7272 
7777 : 7777 * 7777 = 60481729 -> 6048 + 1729 = 7777 
9999 : 9999 * 9999 = 99980001 -> 9998 + 1 = 9999 
17344 : 17344 * 17344 = 300814336 -> 3008 + 14336 = 17344 
22222 : 22222 * 22222 = 493817284 -> 4938 + 17284 = 22222 
38962 : 38962 * 38962 = 1518037444 -> 1518 + 37444 = 38962 
77778 : 77778 * 77778 = 6049417284 -> 60494 + 17284 = 77778 
82656 : 82656 * 82656 = 6832014336 -> 68320 + 14336 = 82656 
95121 : 95121 * 95121 = 9048004641 -> 90480 + 4641 = 95121 
99999 : 99999 * 99999 = 9999800001 -> 99998 + 1 = 99999 
142857 : 142857 * 142857 = 20408122449 -> 20408 + 122449 = 142857 
148149 : 148149 * 148149 = 21948126201 -> 21948 + 126201 = 148149 
181819 : 181819 * 181819 = 33058148761 -> 33058 + 148761 = 181819 
187110 : 187110 * 187110 = 35010152100 -> 35010 + 152100 = 187110 
208495 : 208495 * 208495 = 43470165025 -> 43470 + 165025 = 208495 
318682 : 318682 * 318682 = 101558217124 -> 101558 + 217124 = 318682 
329967 : 329967 * 329967 = 108878221089 -> 108878 + 221089 = 329967 
351352 : 351352 * 351352 = 123448227904 -> 123448 + 227904 = 351352 
356643 : 356643 * 356643 = 127194229449 -> 127194 + 229449 = 356643 
390313 : 390313 * 390313 = 152344237969 -> 152344 + 237969 = 390313 
461539 : 461539 * 461539 = 213018248521 -> 213018 + 248521 = 461539 
466830 : 466830 * 466830 = 217930248900 -> 217930 + 248900 = 466830 
499500 : 499500 * 499500 = 249500250000 -> 249500 + 250000 = 499500 
500500 : 500500 * 500500 = 250500250000 -> 250500 + 250000 = 500500 
533170 : 533170 * 533170 = 284270248900 -> 284270 + 248900 = 533170 
538461 : 538461 * 538461 = 289940248521 -> 289940 + 248521 = 538461 
609687 : 609687 * 609687 = 371718237969 -> 371718 + 237969 = 609687 
627615 : 627615 * 627615 = 393900588225 -> 39390 + 588225 = 627615 
643357 : 643357 * 643357 = 413908229449 -> 413908 + 229449 = 643357 
648648 : 648648 * 648648 = 420744227904 -> 420744 + 227904 = 648648 
670033 : 670033 * 670033 = 448944221089 -> 448944 + 221089 = 670033 
681318 : 681318 * 681318 = 464194217124 -> 464194 + 217124 = 681318 
791505 : 791505 * 791505 = 626480165025 -> 626480 + 165025 = 791505 
812890 : 812890 * 812890 = 660790152100 -> 660790 + 152100 = 812890 
818181 : 818181 * 818181 = 669420148761 -> 669420 + 148761 = 818181 
851851 : 851851 * 851851 = 725650126201 -> 725650 + 126201 = 851851 
857143 : 857143 * 857143 = 734694122449 -> 734694 + 122449 = 857143 
961038 : 961038 * 961038 = 923594037444 -> 923594 + 37444 = 961038 
994708 : 994708 * 994708 = 989444005264 -> 989444 + 5264 = 994708 
999999 : 999999 * 999999 = 999998000001 -> 999998 + 1 = 999999 
4444444 : 4444444 * 4444444 = 19753082469136 -> 1975308 + 2469136 = 4444444 
4927941 : 4927941 * 4927941 = 24284602499481 -> 2428460 + 2499481 = 4927941 
5072059 : 5072059 * 5072059 = 25725782499481 -> 2572578 + 2499481 = 5072059 
5479453 : 5479453 * 5479453 = 30024405179209 -> 300244 + 5179209 = 5479453 
5555556 : 5555556 * 5555556 = 30864202469136 -> 3086420 + 2469136 = 5555556 
8161912 : 8161912 * 8161912 = 66616807495744 -> 666168 + 7495744 = 8161912 
9372385 : 9372385 * 9372385 = 87841600588225 -> 8784160 + 588225 = 9372385 
9999999 : 9999999 * 9999999 = 99999980000001 -> 9999998 + 1 = 9999999 
val it : unit = () 
 
スポンサーサイト

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

trackback


この記事にトラックバックする(FC2ブログユーザー)

アナザーカプレカ数

【F#】another Kaprekar

コメントの投稿

非公開コメント

なんで?

>BigIntを使っているので遅い
とありますが、最初の出だしが、まず遅いですね。
なんでですかね?
ウチ(トラックバック先)の追記バージョンも試してみてください。

No title

最初で、[1I .. 10000000I]などとするのは愚の絶頂でした。
let rec disp limit count =
if count = limit then
()
else
let strOpt = kaprekar count
if strOpt.IsSome then
printfn "%s" strOpt.Value
disp limit (count + 1I)
でやってみて、2分27秒でした。
ちなみにBLUEPIXYさんの、ひとつめので試してみたら、43秒、ふたつめのが1分でした。

あっそうか

in で大きなリストを使っているからですね。
単に、{ .. } でいいですね。
upto 形式でもいいし。

あと、
Gushwellさんのところにもいちゃもんつけてきたんですが、
1から始まらんといかんですよね?

ふたつめのが1分

表示出力をさぼっているから、そのまま比較するのはちょっとアレですね。

No title

英語版Wikipediaの定義
x^2=A*10^n+B (n >= 0, A >= 0, 0 < B < 10^n)
x=A+B
で、やっていたつもりだったのですが
A>0の場合しか考えていませんでした。
確かにA=0のときに1もOKなのですね。
この場合x^2=xとなるので1しかないので、最初に1を付け加えておけばよかったと思ってます。
プロフィール

T GYOUTEN

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

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

この人とブロともになる

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