usakdsteen

ゆうさくですてぃーん

2020年10月26日(Mon)の独り言

の呟きは 26

 < の独り言 | の独り言 | の独り言 > 
  •  #


    https://projecteuler.net/problem=650

    パッと見の問題文は
    しんどそうに見える…

    •  #

      これの考察メモ消えてると思ったら
      ブラウザクラッシュのやつか・・

    •  #

      shower time中に考察しようと思ってたのに脱線して関係ない数学のこと考えてた・・・ダメぽ

  •  #

    shower time

  •  #

    眠気で考察できんし
    寝るかな

  •  #

    うーん、いいアイデアがわかない

  •  #

    まぁだいたいイイカンジに出来たような気がする

    f:id:neetsdkasu:20201027013928p:plain
  •  #

    素因数分解
    なんかダサい感じのコードが出来上がったが・・・
    うーん、どうしたらスマートになるのか・・・

    f:id:neetsdkasu:20201027013845p:plain
    •  (UPD ) #

      takeWhile ( (<=n).(^2) ) [2..]

      ここおそらく普通に[2..√n]とかにしたほうがよさそうな気がする

      •  #

        まぁn<4のとき壊れるかもだけど

      •  #

        2乗計算と比較計算がnが大きい時にコスト高そうだよなあ

        •  #

          平方根計算ってどのくらいのコストなんだろう?
          変わりになるもの自前実装なら整数範囲だしテキトーに二分探索?

          •  (UPD ) #

            まぁそれ実装するくらいなら
            組み込みの平方根計算の関数で十分だよなあ
            おそらくそのほうが速い

            •  #

              floor.sqrt.fromIntegralな感じ?

              •  #

                それにしたら速度減したが・・・?

                f:id:neetsdkasu:20201027013852p:plainf:id:neetsdkasu:20201027013857p:plain
                •  #

                  メモリコストが上がってるぽいし
                  無限リストと違って有限リストだと実体リスト作ってしまって
                  その生成コスト分で速度減、か?

                •  (UPD ) #

                  うん!?自前実装のやつのほうが速い・・・?
                  メモリコストも微増だし・・・?

                  f:id:neetsdkasu:20201027013903p:plainf:id:neetsdkasu:20201027013909p:plainf:id:neetsdkasu:20201027013915p:plain
                  •  #

                    いあ、速度はメモリが原因だったと分かってるわけだし
                    何故この実装だとメモリコストが発生しない・・・?

                  •  #

                    まぁどのみち元のtakeWhileより高速化したわけじゃないし
                    意味ねえな

  •  (UPD ) #

    空しさ無限大

  •  #

    ideone死亡

    f:id:neetsdkasu:20201027013922p:plain
    •  #

      しかたない
      作業するしかないか

      •  (UPD ) #

        娯楽ができなくて悲しい

    •  #

      (omitted)

  •  (UPD ) #

    累乗の和のやつ
    x^0+x^1+x^2+x^3+...+x^n
    x進数と置いたときこれ
    111111111111...111(x)
    になるわけで
    つまり
    10000000..000(x) - 1(x)
    みたいなことすると
    全桁がx-1の値でならぶわけで
    2進数なら10000(2)-1(2)=1111(2)
    だし
    7進数なら10000(7)-1(7)=6666(7)
    10進数なら10000(10)-1(10)=9999(10)
    16進数なら10000(16)-1(16)=FFFF(16)
    各桁の数値が揃うわけでこういうのから(x-1)で割ると11111111...111(x)というのが出来るわけで
    つまり (x^(n+1) - 1) / (x-1) = x^0+x^1+x^2+...+x^n ということになる

    •  #

      まぁ、普通は
      S(n)=x^0+x^1+x^2+x^3+...+x^n
      とか置いて
      x*S(n) - S(n) = x^(n+1) - 1
      となって
      (x-1)*S(n) = x^(n+1) - 1
      となるからx-1>0のとき
      S(n) = (x^(n+1) - 1) / (x-1)
      になる
      とか導くんだろうな・・・

      •  (UPD ) #

        まぁx-1<0でも成り立つのかな?式的には・・・
        x-1=0はつまりx=1のときであり全部1の和になるから単純にS(n)=n+1になるが

  •  #

    宇宙、巨大すぎる

 < の独り言 | の独り言 | の独り言 >