戦績->[LINK]

以下問題要約と手法
#001: 1000以下で3の約数or5の約数の数 : #{3の約数}+#{5の約数}-#{15の約数}
#002: 4000000以下のフィボナッチ数列のうちの偶数項の総和 : 直接計算
#003: 600851475143の最大の素因数: 素数を列挙して試し割り
#004: 3桁の数2つを掛けて出来る最大の回文数: 直接計算
#005: 1-20までの全ての整数で割り切れる最小の整数: コードなし。電卓計算？
#006: 1-100にわたる∑n^2と(∑n)^2の差 : 直接計算 O(n^2)
#007: 小さい方から10001番目の素数: 200000以下の素数を列挙してその10001を表示
#008: 提示された数字の列から連続する5つの数字の積をつくったときの最大値: 直接計算(なぜかlogを使った)
#009: a+b+c=1000を満たすピタゴラス数(a^2+b^2=c^2)の積(abc): 手計算。下参照。
#010: 200000以下の素数の総和: 素数列挙による直接計算
#011:
#012: 約数の数が500個を超える最初の三角数: 素因数分解による直接計算
#013: 提示された100個の数(各々50桁)の総和の上10桁: 整数配列による直接計算
#014: コラッツ問題で最長の周期を持つ1000000以下の初期値: DPによる計算 O(n)
#015: 20*20の格子において、右移動と下移動のみで左上隅から右下隅まで行く方法の数: 40C20の計算
#016: 2^1000の10進表示における各桁の数字の総和: 整数配列による直接計算
#017: 1-1000までの数をイギリス英語で表記したときの文字数の総和: 直接計算
#018: 与えられた「整数の三角形」を頂上から底辺まで下る時の、ルート上の数の総和の最小値: DPによる計算 O(n^2)
#019: 20世紀において月始めが月曜日だった回数: ツェラーの公式による計算
#020: 100!の各桁の総和: 整数配列による直接計算
#021: 10000以下の友愛数の総和: 検索によるインチキ
#022:
#023:
#024: "0123456789"の順列を辞書順に並べた時の1000000番目: 特殊記数法(階乗進法?)による直接計算
#025: 桁数が1000を超える最初のフィボナッチ数列の項数: log10による桁数評価
#026: 分母が1000以下で最長の周期を持つ単位分数の分母: 直接計算
#027: オイラーの素数生成式 n^2+n+41 にならって n^2+an+b の形の式を考える時、|a|, |b|<=1000の範囲で最も多くの素数を連続して生成できる式のa*bの値: シミュレーションによる直接計算
#028: 1001*1001の整数螺旋における対角線上の数の総和: 公式を用いた直接計算
#029: 2<= a, b <=1000 における相異なるa^bの値の数: setを用いた直接計算
#030: 自分自身の各桁の数字の5乗の和として書けるすべての数の総和: 1000000以下の全探索
#031:
#032: a*b=cを満たし、a,b,cの各桁の数字に1-9が全て1回ずつ登場するときのa*b*c: 順列と組み合わせを用いた逆生成
#033: 二桁同士の真分数のうち49/98=4/8のように分子の1桁目と分母の2桁目をキャンセルしても結果が変わらないもののを総乗し、それを規約分数にしたときの分母の値。
#034: 0, 1, 2, 145=1!+4!+5!以外で各桁の階乗の和が自分自身に等しい数
#035: 各桁の数字を循環させても素数になるものは1000000以下にいくつあるか？: シミュレーション
#036: 1000000以下で10進表記でも2進表記でも回文数になるものの数: シミュレーション
#037: 左右それぞれから1桁ずつ数字を削っていっても素数になるような数の総和: 適当に大きな数以下の素数を列挙してシミュレーション
#038:
#039:
#040: チャンパーノウン定数の小数点以下i桁目をd(i)とする時のd(1)*d(10)*d(100)*d(1000)*d(10000)*d(100000)*d(1000000)の値
#041: 最大のパンデジタル素数
#042:  
#043:  
#044:  
#045:  
#046:  
#047:  
#048: ∑{n:1->1000}n^n の下10桁: 合同算術と冪剰余による計算
#049: 1487, 4817, 8147 のような4桁の素数による等差数列の始めの3項を連結した数
#050: 1000000以下の素数で、最も多くの個数の連続した素数の和で書けるもの
#051: 「いくつかの桁の数がすべて同じ」という性質を持つ素数の集合(例 (13, 23, 43, 53, 73, 83)) のうち、大きさが8のものについて、その「集合の最小値」の最小値 : パターンマッチングとハッシュ
#052:
#053: 1<=n<=100において、nCrが1000000を超える組(n, r)の数
#054: not solved
#055:
#056: a, b <100 における a^bの各桁の総和の最大値
#057:

#072: 区間(0,1)上にある分母が1000000以下の既約分数の数 : ファレイ数列

#075: 周長 L<=1500000 の、各辺が整数長の直角三角形のうち、ユニークな(=他に同じ周長の直角三角形が存在しない)ものの数 : 原始ピタゴラス数とハッシュ
#076: "100" を2つ以上の整数の和で表す方法の数 : DP
#077: 正の整数のうち、素数の和で表す方法の数が最初に5000を超えるものの値 : DP

#080: N=1-100のうち、√Nが無理数になるものについて、その「100桁目までの数字の総和」の総和 : BigInt

#086: 整数要素を持つ80*80の行列を右上から左下に移動する際、各セルの数値をコストとしたときの最小の総コスト: ダイクストラ法

#098: 互いにアナグラムになる2つの英単語の組で、同じ文字に同じ数字(異なる文字に同じ数字を与えてはいけない)を与えるとどちらも平方数になるようなものを"平方アナグラム"と呼ぶことにする。与えられた単語リストの中から平方アナグラムを探し出し、対応する平方数のうち最大のものを求める。 : ソートと置換(tr)とハッシュ
#118: 素数の組のうち、全体を通じて1-9までの数字が1回ずつ登場するようなもの(例:{2,5,47,89,631})の個数 : ビット列, ビット演算
#119: 整数 N の各桁の数字の和を S(N)とするとき、数列Aを, A={N|N=S(N)^M となるような整数Mが存在, A[n] < A[n+1]} と定義する。このときのA[30]の値。 : BigInt, 剰余

#123: n番目の素数pnについて、 (pn+1)^n+(pn-1)^n mod pn^2 >10^10 となるnの最小値: 特になし

副産物

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

ひとこと

#9 紙とペンバージョン
「a+b+c = 1000を満たすピタゴラス数(a,b,c)について abc を求めよ」

ピタゴラス数は次式を満たす
a = A^2-B^2
b = 2AB
c = A^2 + B^2
ただしA>B.
これをa+b+c=1000に代入すると A(A+B)=500.
500を25*20と書くと、A=20, A+B=25とするとA=20 > B=5で制限を満たす。
よって a = 400 - 25 = 375, b = 2*20*5 = 200, c = 400+25 = 425.
したがって abc = 375*200*425 = 31875000

#113のアルゴリズム

n+1桁の increasing number は、n桁のincreasingnumberの先頭に数字を１つ足して作られる。
足せる数字は先頭の数字以下に限られる。
よって、n+1桁で先頭の数字がaの increasing number の数は、 ∑[b=a to 9](先頭の数字がbのn桁 increasing number)
となる。
increasing number だけを数えるときはこれでよいが、問題は not bouncy number, つまり decreasing number の数も数えなければならない。
decreasing number は increasing number の反転以外に 90, 320など、うしろにゼロがつくものを許容する。
よって、上の a = 0 の場合も記録しておくことが必要。
また、 increasingかつdecreasingな数も存在するので、それを２重カウントしないように気をつける。

・・・実は、n桁で先頭がaのincreasing numberの数は (n+8-a)C(9-a)に等しい。
またn桁で後尾が0のdecreasing numberの数は(n+8)C9　-　1.

#302

nとφ(n)がともにアキレス数であるような数nを強アキレス数と呼ぶ。
10^18未満に強アキレス数はいくつあるか？

-------------------------------------------------------------------

アキレス数：　「多冪数であり」かつ「累乗数でない」
多冪数：　任意の素因数pについて、p^2でも割り切れる数
累乗数：　自然数の累乗として書ける数

素因数分解を Πp_k^d_k としたとき、
多冪数：　すべてのd_kについてd_k>1が成り立つ。
累乗数：　すべてのd_kの最大公約数が1より大きい

1より大きい自然数は自然数s, tを用いて2s+3tと書けるので、多冪数は自然数a,bを用いてa^2b^3と書ける。

オイラーのトーティエント関数φ(n) = #{x<n| gcd(n,x)=1}
<性質>
・素数pについて、φ(p)=p-1
・素数冪p^kについて、φ(p^k) = p^k-p^(k-1) = p^(k-1)φ(p)
・gcd(a,b)=1をみたす自然数a,bについて、φ(ab)=φ(a)φ(b)

自然数nの素因数分解をΠp_k^d_kと書くと、上記より

φ(n) = Π(p_k-1)p_k^(d_k-1) = nΠ(1-1/p_k)

が成り立つ。
上式を見ると、φ(n)がアキレス数か否かはΠ(p_k-1)にかかっているような感じで、
これを知るにはどうしてもnを因数分解する必要がありそうな気がする。
10^18以下のアキレス数をまずリストアップして因数分解してみたくなる。

適当に取った数が多冪数になるかどうか？
多冪数 = gcd{d_k}>1.　3つ以上の集合の公約数は、2つ選んでそのgcdで置き換える、という手続きを繰り返して得られる。
[gcd{n} > 1] => [{n}中のどの2つも互いに素でない] (gcd{n}=s>1ならばsは任意の2つの公約数となるので)
よってP(gcd{n}>1) < P({n}中のどの2つも互いに素でない).
全自然数から任意に選んだ2数が互いに素になる確率は1/ζ(2) ～ 0.6[LINK]
よって
P({n}中のどの2つも互いに素でない) ～ 0.6^(#{n}^2/2) -> 多冪数になる確率は極めて少なそう。
リストアップできないくらい多い、ということは無いと思う。

M以下の多冪数をリストアップする手続き
(1) 多冪数は、bを無平方数に限定すればn=a^2b^3と一意に書ける。 n<M -> b^3<M -> b < M^(1/3)
(2) B := {b| b ∈ {M^(1/3)未満の無平方数} }
　　(2-1) N = M^(1/3)として、 A := {p^2 | p ∈ {N^(1/2)以下の素数}}
　　(2-2) C := {n | n ∈ {N以下の自然数}/{Aの倍数}} はN以下の無平方数の集合。
　　N=1000000としたとき#Cはおよそ300000.
(3) a = √(n/b^3)なので、 a = 1 -> floor(√(M/b^3))として a^2b^3を列挙していく。
　　ただしb=1のときはn=a^2で明らかに累乗数なのでやるだけ無駄。

速くて小さいProblem 117
------------------------------------------
#include <iostream>
#include <vector>
using namespace std;

//Problem 117
#define N 50
#define L 4

int main(){
  vector<unsigned long long> Rest(L+1, 0);
  
  Rest[0] = 1;
  for(int i=1; i<=N; ++i){
    Rest[i%(L+1)] = 0;
    for(int j=L; 1<=j; --j)
      Rest[i%(L+1)] += Rest[(i-j+L+1)%(L+1)];
  }
  cout << Rest[N%(L+1)] << endl;
}
----------------------------------------

長さが1〜LのL種類のブロックを使って長さNの列を作る方法の数を数える。
領域計算量はO(L), 時間計算量はO(N*L).