問題 オイラーのφ関数で、n/φ(n)が最大となるものをn 考え方 実際に試す。

問題 euler28のように渦巻き状に数を並べていく。 対角線上の数値について、素数の割合が10%以下になる最小の幅を求める。 考え方 幅がiのとき、新たに追加された部分の4つ角の数値は、法則性から (i-1)*(i-1) - (i-2) (i-1)*(i-1) - (i-2) + i-1 (i-1)*(i-1…

問題 2の平方根の連分数展開を1000項まで考える。 i項まで展開したときの分子と分母のうち、分子の桁数の方が分母の桁数を超えるものはいくつあるか。 考え方 多倍長で実際に計算する。

問題 10000000未満の数で、以下の操作をしたとき、89が出現するものはいくつあるか。 ・各桁を2乗したものの和を取る ・その和をまた各桁を2乗したものの和を取ることを繰り返す これを繰り返すと1または89のどちらかが出現し、繰り返すことがわかっている。…

問題 ある暗号化された文がバイトごとに区切られたものが与えられる。 あるアルファベット3文字によってXORを取ったものであることがわかっている。 元の文のasciiコードの数値の和を求める。 考え方 3文字をどういう風に使ってXORとるか書かれていない。 考…

問題 自然数をn乗したものがn桁になるものはいくつあるか。 考え方 自然数をaとすると、 10^{n-1} を満たすので、変形すると、 (n-1)/n を満たさなければいけない。aは自然数なので、右側の不等式から、1〜9までを調べればよい。 各aについて、nを1から(n-1)…

問題 あるパスコードがあったとして、ランダムに左から3つ選んで入力するセキュリティシステムがある。 50回分の入力に成功している3つの数字のリストが与えられる。 可能なパスコードのうち、一番短いものを見つける。 考え方 パスコードを見てみると、同じ…

問題 五角数とはPn=n(3n-1)/2であらわされる数をいう。 あるPk,Pjについて、その和と差が五角数になるもののうち、差D=|Pk-Pj|の最小値を求める。 考え方 五角数の判定は、あるaが五角数ならば3n^2-n-2a=0の解nが整数になるはずなので、n=(1+sqrt(1+24a))/6…

問題 bouncy数とは、数字の各ケタについて、増加列でも減少列でもない数字をいう。 1からnまでの数で初めにbouncy数の割合が99%となるnを求める。 考え方 各桁ごとに分解した数字列を求め、それをソートする。 そして、もとの数字列と昇順ソートしたもの＆降…

問題 a^bのaとbが複数与えられる。 与えられたa^bの中で一番大きいものを返す。 考え方 対数をとっても大小関係は変わらないので、b*log(a)を使って比較する。

問題 80*80の配列に数字が入っている。 各マスで右または下に移動できるとき、左上から右下までの経路で数字の和が最小となるものを見つけ、その和を返す。 考え方 ダイクストラ。