2024年7月2日火曜日

Fixed Day Number

前回のブログのアルゴリズムに, 年初から前月末までの総日数を計算する式:
(367 * month - 362) // 12
があった. monthを1から12まで変えて値を計算すると.
[0, 31, 61, 92, 122, 153, 183, 214, 245, 275, 306, 336]
が得られる. 演算子「//」で小数点以下を落しているが, その落された値を調べると, ( (4777 - 367 * month) // 12 の図も右に示す.)

のような図になる. どちらも2月は30日あるとする.

まず左の図に注目する. 1月から2月は下がり, 2月から3月は上がり, 4月へは下がり, ... 8月と9月へは下がり, ... つまり大の月の後は下がり, 小の月の後は上がるらしい.

計算して見ると下がる量は0.4167, 上がる量は0.5833である.

もう一度式を見ると, monthが1増えると, 367 / 12 つまり 30.5833 増える. これと30及び31の差であった. これで納得できるが, Calendrical Calculation にはこういう説明があった.
(7 * m - 2) // 12 + 30 * (m - 1)
この第2項 30 * (m - 1) はすべて小の月として前月末までの総日数.

第1項はm = 1, 2, ..., 12について,
0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6
  31 30 31 30 31 30 31 31 30 31 30
である(上の行), 下の行は1月から11月までの日数で, こうして見ると, 大の月の 上で上の行の値は1増える. つまり小の月とした時の誤差を得ている.

そこで上の第1項と第2項を足すと, (367 * m - 362) // 12になるのであった.

2月を30日にしたという発想がよかったのだ. 一方, 年末から計算する方の式はこう導く.

欲しい値は1月, 2月, ..., 12月で, 2月も30日とするから
[367, 336, 306, 275, 245, 214, 184, 153, 122, 92, 61, 31]
である. 30の倍数の列
[360, 330, 300, 270, 240, 210, 180, 150, 120, 90, 60, 30]
に誤差の列
  [7, 6, 6, 5, 5, 4, 4, 3, 2, 2, 1, 1]
  
を足したものだ. これは7から年初からの計算の誤差を引いたのもだ. つまり,
7-(7 * m - 2) // 12
でこれを(13 - m) * 30 に足す. これを一纏めにしたい.

まず下の計算の1行目のように, 床関数を天井関数にする. そして1を足して床関数に戻す. しかしmの値によっては, 整数になることがあり, 1を足すと失敗する. 従って, 2行目のように, 1の代りに 11/12を足してみる. 3行目はそれに30日の倍数を足したところ. 最後に分数の外に ある部分を分子に足す. すると(4777-367m)//12が得られる.

どうだろうか.

2024年7月1日月曜日

Fixed Day Number

私の好きな本に, Edward M. ReingoldとNachum DershowitzのCalendrical Caluculation がある. 随分昔に購入したもので, 手元にあるのは2004年のThird Printing.

要するに暦に関するアルゴリズムが満載で面白い. この本では暦の変換の基準は, Fixed Day Numberといい, Gregorian暦が過去に遡って使われたとして, その1年1月1日(の正子)を 第1日とするものである. いちいちfixed day numberといわず, R.D.と いうらしい. (Rata Die)

似たようのものに, -4712年1月1日正午から起算するユリウス日があるが, これは途中でJulian暦 からGregolian暦になるので変換が面倒である.

Calendrical Caluculationにある, Gregorian暦の年月日からそのR.Dを計算する アルゴリズムを見てみよう. 本書のアルゴリズムはCommon Lispで記述されているが, 今日はPythonに翻訳する.
def fixeddaynumber(year, month, day):
    return (365 * (year - 1) + (year - 1) // 4
            - ((year - 1) // 100) + (year - 1) // 400
            + (367 * month - 362) // 12
            + (0 if (month <= 2) else
               (-1 if leap_year (year) else -2))
            + day)
     
最初の365 * (year - 1)は前年までがすべて平年であったとしての, 前年の 最後の日までの総日数である. しかし, 4年に一度閏年があるから, その分を足す. + (year - 1) // 4. Gregorian暦では, 100で整除される年は平年に するのであったからそれを引く. - ((year - 1) // 100). しかし400で 整除されるなら閏年にするからそれを足す. + (year - 1) // 400. 前年末までの総日数はこれで計算出来た.

次は前月末までの日数を計算する. 目標としては, 1月なら0. 2月なら31, 3月は 平年なら59, 閏年なら60, ... 閏年の補正は後でやることにし, 本書にあるアルゴリズム は(367 * month - 362) // 12というものだ. monthを 1から12まで変えてこの値を計算すると:
print(list(map (lambda m:(367*m-362)//12, range(1,13))))
[0, 31, 61, 92, 122, 153, 183, 214, 245, 275, 306, 336]
    
3月からは, 平年なら2, 閏年なら1多いことがわかる. 従ってこの関数の month番目を使い, monthが1, 2ならこの値そのまま, 3以降はこの値から 平年は2, 閏年は1を引いて使う.

これで前年末までと前月末までの総日数が分ったから, 後はdayを足せばよい.

閏年の補正に本書ではこういう式を使う.
def leap_year (year):
    return (year % 4) == 0 & ((year % 400)
                              in [100, 200, 300])
    
これで1年1月1日を計算すると:
print (fixeddaynumber (1, 1, 1))
1
 
なるほど. また, おととし, 開業150年と話題になった鉄道開通の日, 1872年10月14日(明治5年には日本は まだ旧暦を使っていたが, これは太陽暦に換算してある)のR.D.を計算してみる.

各々の項の値は682915, 467, -18, 4, 275, -1, 14で, R.D.は683656 である.

ところで私は何度も暦の計算のプログラムを書いたが, その年の終までの日数を計算し, その月の前までの日数を引いて日を足すのが好きだ. 上のアルゴリズムに year - 1が4回もあるのが気に食わないのである.

それで普通は年末から今月0日までの日数を引くことになるが, 大体はそこは定数の 表を利用する. しかし, Calendricalの本にあるような式が使えないかと 考えた. Calendricalの式と同様, 1,2月は特別扱いにしてもよいとして, 定数など を変えてテストした. 欲しい値は:
[[365, 366], [334, 335], 306, 275, 245, 214,
 184, 153, 122, 92, 61, 31]
    
である. 左端が1月と2月で, かっこ内は左が平年, 右が閏年. 右端が12月. その結果, (4777 - 367 * m) // 12がよいらしかった. つまり
print(list(map (lambda m:(4777 - 367 * m) // 12,
                range(1,13))))
[367, 336, 306, 275, 245, 214, 184, 153, 122, 92, 61, 31]
    
1月, 2月は平年は2を引き, 閏年は1を引く.

ここで使う定数4777は非常にクリティカルで, 4776や 4778に変えてみると, 前者は7月が小さく, 後者は2月が大きい.
print(list(map (lambda m:(4776 - 367 * m) // 12,
                range(1,13))))
[367, 336, 306, 275, 245, 214, 183, 153, 122, 92, 61, 31]

print(list(map (lambda m:(4778 - 367 * m) // 12, 
                range(1,13))))
[367, 337, 306, 275, 245, 214, 184, 153, 122, 92, 61, 31]

これを利用して書いたfixed day number関数は次の通り:
def fixeddaynumber2(year, month, day):
    return (365 * year + year // 4 - (year // 100)
            + year // 400 - (4777 - 367 * month) // 12
            + (0 if (month > 2) else
               (-1 (year % 400 == 0)
                if (year % 100 == 0) else
                (year % 4 == 0) -2))
            + day)
こちらで鉄道記念日を計算したのと, 本年6月30日の値の7で割った剰余とを見ると:
print (fixeddaynumber2 (1872, 10, 14))
683656

print ((fixeddaynumber2 (2024, 6, 30)) % 7)
0       
だから, R.D.を7で割った剰余が曜日になるわけだ. つまり, R.D.1の日, 1年1月1日は月曜であった.

年末から月始めまでの日数を今回のように式で計算すると, 実引数に0月とか13月が与え られても計算してしまう恐れがある. 表なら範囲外としてエラーに出来る. それを 心配したとしても, 日の値に範囲外が与えられる可能性はあるのだから, まぁ我慢することに しよう.

2022年9月20日火曜日

満月の十五夜

今年は9月10日が中秋の名月, つまりお月見であった. 幸いよく晴れて, 満月が堪能出来た.

ところで新聞が「今年の中秋の名月は満月」と報じた. 私はもちろん旧暦の15日が満月にならない方が普通で, たまには満月になることも知っていたから, この新聞記事をみて何とも思わなかったが, どの程度すれすれに満月なのかと天文年鑑を見ると満月は18時59分であった.

旧暦の15日が満月にならないのは, 新月の時点のある日を旧暦の1日とするからである. 仮に1朔望月を29.5とし, 月齢14.75を満月とすれば, ある日の朝0.25日までに新月があればその日が1日で, 15日の晩には月齢が14.75に達する. そうでないと, 月齢が14.75になるのは, 旧暦16日になる.

ところが月の公転には遅速があり, 満月は太陽と月の黄経の差が180度の時のことだから, 月齢14.75からプラスマイナス1日くらいずれ得る.

そこで新月から満月, 満月から新月の経過時間の変化を見てみたいと思った. 2013年から2022年の天文年鑑から, 新月と満月の日時を書き出し, パソコンに入力して新月と次の満月, 満月と次の新月の経過時間を計算した.

10年間にある朔望月は, 19年7閏法を考えると, 120+3.5回だから, 日時データは247, 間隔は246あった. 最大値は15.601, 最小値は13.907, 平均値は14.767.

最後の10個は
... 14.32 15.278 14.071 15.497 13.958
15.579 14.009 15.497 14.216 15.256
である.

それを絵にしたのが下だ. 赤は新月から満月, 青は満月から新月までの経過時間である. 縦軸の単位は日.

図を見ると, 時々赤と青が同じになり, つまり新月から満月までと満月から新月までが同時間になり, その中間は一方は増えて減り, 他方が減って増える.

その理由は多分こうであろう. 月の公転軌道も楕円であり, 長軸の一方が近地点, 他方が遠地点である. 近地点では公転速度が速く, 遠地点では遲いのは常識だ.

近地点と遠地点の近くに新月と満月の場所があれば, 新月から満月も満月から新月もほぼ同時間になる. しかし, 新月と満月がその中間くらいにあると, 近地点側を通る方は経過時間が短かく, 遠地点側は長い. それがこの図の謎解きであろう.

2022年の新月と満月の日の月の地心距離を天文年鑑から調べ, 新月から満月までやその逆の経過時間がどの地心距離からどの地心距離であったかの図を描いてみた. それを下に示す. 横軸は経過時間(単位は日)で, 縦軸は地心距離(単位は万km).

これを見ると, 上の推論が正しいことが分る. 左上から右下へ来る矢印は, 遠地点から近地点までの経過で14.8日くらい掛ることで, 15.7日くらいの水平の矢印は, 中間から中間への遠地点側を通る経過, 14.0日くらいの水平の矢印は, 近地点側を通る経過である.

十五夜が満月になるというのには, こういう仕掛けがあったわけだ. その後, 国立天文台暦計算室のページを見付けた.

2022年9月8日木曜日

切頭八面体

久し振りに切頭八面体について書きたい. TAOCPにおやという記述があった.

a: 切頭八面体の基本的な置き方は, (htmlでは式が書き難いから言葉で述べると) 0,1,2,3の, 同じもののない3つ組である.

b: 体心立方格子のVolonoi領域である.

bはなるほどそうらしいと思うが, そしてそういう言い方もあるのかと思うが, aはすぐには分らなかった. その組を作ってみると,
((0 1 2) (0 1 3) (0 2 1) (0 2 3) (0 3 1) (0 3 2) 
(1 0 2) (1 0 3) (1 2 0) (1 2 3) (1 3 0) (1 3 2) 
(2 0 1) (2 0 3) (2 1 0) (2 1 3) (2 3 0) (2 3 1) 
(3 0 1) (3 0 2) (3 1 0) (3 1 2) (3 2 0) (3 2 1))
になり, たしかに24個あって, 切頭八面体の頂点の数と同じである.

それぞれの3つ組を(x, y, z)と思い, 高さ(z) 別に絵を描くと, 下の図の上段のようになる. z=0, つまり底の面に点が6個あるから, これは六角形を床に置いた図らしいと分る. 六角形にしてはいびつだが, それは直交 座標のためらしいから, x軸とy軸の角度を60度にしてもう一度描いたのが中段の図である.

なるほど六角形が現れる.

そこでx軸とz軸, y軸とz軸の角度も60度にしたグラフ用紙を作って, 上に点を 書き込むことにした. つまり, x軸y軸z軸は正四面体の3本の辺に沿っている. それが上の赤緑青の線である. 赤はz=0の平面座標で, その三角形の中心を起点とした緑のz=1の平面座標が出来, その三角形の中心を起点とした青の z=2の平面座標が出来る. 同様にしてz=3の座標が出来るが, それはz=0のと一致する.

黒線で描いたのが六角形を底にした切頭八面体である.

これを確認するため, 別の切頭八面体の絵もある. 左上Aは, 私が通常に描く切頭八面体 である. その中心を通る直交するx軸(赤), y軸(緑), z軸(青)も描いてある.

私の描画プログラムは, 頂点の座標を座標軸に平行移動したり, 座標軸に沿って回転 したり出来る. BはAの図を, z軸について45度回転したものだ. Cはそれを右下の 5,12の辺が, xyz軸の中心に来るように移動したもの. Dはそれを右下の六角形が 底に来るように, x軸について回転したものである. 最後のEは, 座標軸の中心に 切頭八面体の中心が来るように移動した.

この時, 各頂点の直交座標での位置は次の通りである. (左は頂点の番号順, 右は高さ別)
     0 (-2.121 0.408 -0.577)      9 (-1.414 0.0 1.732)	
     1 (-1.414 0.0 -1.732)	  11 (-0.707 1.225 1.732)	
     2 (-1.414 1.633 -0.577)	  16 (-0.707 -1.225 1.732)	
     3 (-0.707 1.225 -1.732)	  18 (0.707 1.225 1.732)	
     4 (-2.121 -0.408 0.577)	  20 (0.707 -1.225 1.732)	
     5 (-0.707 -1.225 -1.732)	  22 (1.414 0.0 1.732)	
     6 (-0.707 2.041 0.577)	  1 (-1.414 0.0 -1.732)	
     7 (0.707 1.225 -1.732)	  3 (-0.707 1.225 -1.732)	
     8 (-1.414 -1.633 0.577)	  5 (-0.707 -1.225 -1.732)	
     9 (-1.414 0.0 1.732)	  7 (0.707 1.225 -1.732)	
     10 (-0.707 -2.041 -0.577)	  12 (0.707 -1.225 -1.732)	
     11 (-0.707 1.225 1.732)	  14 (1.414 0.0 -1.732)	
     12 (0.707 -1.225 -1.732)	  4 (-2.121 -0.408 0.577)	
     13 (0.707 2.041 0.577)	  6 (-0.707 2.041 0.577)	
     14 (1.414 0.0 -1.732)	  8 (-1.414 -1.633 0.577)	
     15 (1.414 1.633 -0.577)	  13 (0.707 2.041 0.577)	
     16 (-0.707 -1.225 1.732)	  21 (1.414 -1.633 0.577)	
     17 (0.707 -2.041 -0.577)	  23 (2.121 -0.408 0.577)	
     18 (0.707 1.225 1.732)	  0 (-2.121 0.408 -0.577)	
     19 (2.121 0.408 -0.577)	  2 (-1.414 1.633 -0.577)	
     20 (0.707 -1.225 1.732)	  10 (-0.707 -2.041 -0.577)	
     21 (1.414 -1.633 0.577)	  15 (1.414 1.633 -0.577)	
     22 (1.414 0.0 1.732)	  17 (0.707 -2.041 -0.577)	
     23 (2.121 -0.408 0.577))	  19 (2.121 0.408 -0.577)    
各頂点の直交座標(x,y,z)を, 斜方座標(a,b,c)に変換するには, 例えば
(define (tcood x y z)
(let* ((c (/ (* z 3) (sqrt 6)))
       (b (/ (* (- y (/ (* c (sqrt 3)) 6)) 2) (sqrt 3)))
       (a (- x (/ b 2) (/ c 2))))
(list a b c)))
しかしこれで変換すると0.707や2.121が出るので, 正規化すると, 先程の24個の 直交座標は
((-3 1 -1) (-1 1 -3) (-3 3 -1) (-1 3 -3) (-3 -1 1) (1 -1 -3)
 (-3 3 1) (1 3 -3) (-1 -3 1) (-3 -1 3) (1 -3 -1) (-3 1 3)
 (3 -1 -3) (-1 3 1) (3 1 -3) (1 3 -1) (-1 -3 3) (3 -3 -1)
 (-1 1 3) (3 1 -1) (1 -3 3) (3 -3 1) (1 -1 3) (3 -1 1))
なるほど, 最初に書いた座標は0,1,2,3であったが, 今回のは. 切頭八面体の中心に座標の 中心を置いたので, -3,-1,1,3で構成されていた.

2022年9月6日火曜日

Wolframの対数表

学生の頃から気になっていたことがある. 高木貞治先生の「解析概論」のp.215の脚注に 「Wolframノ表ニハ1000以下ノ素数ノ自然対数ノ50桁ノ表ガ掲ゲラレテヰル. コノ表ハ既ニ少年がうすガ愛用シタモノデアル.」と書いてあったことだ. また, 岩波文庫の「近世数学史談」のp.65に 「Wolframの計算した10000以下の素数及び若干の特殊の数の自然対数の表が 附いていたのである.」と書いてあるのも見付けた. 1000までの素数か10000までの 素数かに違いはあるが, とにかくそういう対数表が存在していたらしい.

学生の頃にそんな数表を探すのは夢のまた夢であったが, 長生きはするもので, この歳に なってインターネットを検索していたら, 関係のあるウェブページがあった.

そのひとつは A reconstruction of the Mathematical Tables Project’s table of natural logarithmsという文献で, その図1は, Wolframが計算したものを, Schulzeが1778年(Gaussの生まれた翌年)に 出版したものの最後のページの写真. これを見て, 1000までの方が違っているのが分かった. しかも最後は10009で精度は48桁であった. また6個の素数には対数が記入 されていず, Wolframが病気で計算できなかったらしい. その図2はVegaが欠けている値を計算して 追加して1794年に出版したものの最後のページの写真がある. いずれにしても, Gaussが所持していたWolframの数表はこういうものであったらしい.

もうひとつは, New Information Concerning Isaac Wolfram's Life and Calculationsである. これによると, Isaac Wolframはオランダの砲兵の士官であった.

Wolframは何年もかけてこの数表を作ったらしいが, 現代は便利な世の中で, 自然対数も 簡単に得ることが出来る

そのひとつは, 別のWolframだが, WolframAlphaである. このページを開くと入力用窓があり, そこに「ln(2)」といれると, 2の自然対数が64桁くらい表示される. 0.6931471805599453094172321214581765680755001343602552541206800094 私もこの数表を作ってみたくなった. しかし. WolframAlphaは手動でしか使えないから, 別の方法が必要だ. あれこれ探していたら, Python3でも値が得られることが分った.
from decimal import *
getcontext().prec = 55
Decimal(2).ln() => 
Decimal('0.6931471805599453094172321214581765680755001343602552541')
これを使うと, Wolframの対数表みたいなものはすぐ作れる. 10000までの素数は 1229個あるが, 最初の20個の素数と, 10000未満の最後の19個の素数に対して 作た対数表はこんなようだ.
2から9973までの素数に対する自然対数の表は, 私の計算機にある.

2022年4月12日火曜日

mex関数

mex関数についてブログに全回書いたのは, もう2年も前だった. その頃, Schemeでの実装も 出来ていたが, なんとなく気に入らなかった.
最近, もう少し気持ちよくしたいと思い, やった書き直したので, ブログに記録して おく. まずinsertion. (ins n t)は, nを, 木tに挿入する関数である.
(define (ins n t)  ;inserts n in a tree t, returns a new tree
  (if (null? t) (list '() (list n n) '())
      (let ((lt (car t)) (l (caadr t)) (r (cadadr t))
            (rt (caddr t)))
  (define (insr t)
    (let ((lt (car t)) (m (caadr t)) (s (cadadr t))
          (rt (caddr t)))
      (if (null? rt)
        (if (= s (- n 1)) (begin (set! l m) lt)
            (begin (set! l n) t))
        (list lt (list m s) (insr rt)))))
  (define (insl t)
    (let ((lt (car t)) (m (caadr t)) (s (cadadr t))
          (rt (caddr t)))
      (if (null? lt)
        (if (= m (+ n 1)) (begin (set! r s) rt)
            (begin (set! r n) t))
        (list (insl lt) (list m s) rt))))
  (cond ((<= l n r) t)
        ((= n (- l 1))
          (if (null? lt) (list lt (list n r) rt)
              (let ((lt (insr lt)))
                (list lt (list l r) rt))))
        ((< n (- l 1)) (list (ins n lt) (list l r) rt))
        ((= n (+ r 1))
          (if (null? rt) (list lt (list l n) rt)
              (let ((rt (insl rt)))
                (list lt (list l r) rt))))
        ((> n (+ r 1)) (list lt (list l r) (ins n rt)))))))
一方, これを使う(mex ms)は次のようだ.
(define (mex ns) (let ((t '()))
 (for-each (lambda (n) (set! t (ins n t))) ns)
  (if (null? t) 0
      (begin (while (not (null? (car t))) (set! t (car t)))
             (if (< 0 (caadr t)) 0 (+ (cadadr t) 1))))))
全回と似たような図だが, 8 4 12 2 6 10 14 7 3 5 1 11 13 15 9 の順に挿入した時の木構造の移り代りの図を示す.
左上の A [8,8] 8 は, 左のAが図の記号, 右の8が今回挿入したn, 中央が(最初は空だった)木にnが挿入された, 新しい木 のように見る.

2021年10月31日日曜日

クイーン支配問題

前回のクイーン支配問題のブログは, 8×8の大きさのチェス盤に, 5個の クイーンを置き, 盤面のすべての場所が支配できる配置の数を計算するものであった. 4860という解が得られたが, どう考えても, 90度の回転や, 左右の反転で同じになる 仲間が沢山含まれている筈である.

そこで次の課題は, 本質的に異なる配置の数を知ることである. 前回のすべての配置の それぞれに, 回転や反転を施し, それで一緒になる配置を仲間とするプログラムを書き, 実行すると, 638という答が出た.

クイーン支配の配置は, かなりランダムらしいから, 回転で仲間が4倍になり, 反転で また2倍になって, 仲間は8人がほとんどになりそうである. しかし, 反転するとどうなるか. 左右反転では, 偶数の列に奇数のクイーンを置くから, クイーンの奇数個を中央の列に置き, 残りの偶数個を, 左右対称の位置に置けばいいわけだが, 中央の列が存在しないから, 左右や上下の反転で一緒になるものはない. 一方, 対角線で反転することを考えると, 対角線には中央があるから, そこに奇数個を置くと, 対称になり得る. この対角線の 中央を通る, もう一方の対角線で, もう一回反転できるかというと, 対角線の長さ が8という偶数なので, そういう反転はあり得ない.

従って, 4人の仲間のグループと, 8人の仲間のグループとで, グループは638あり, メンバーの総数は, 4860人ということになる.

4人と8人のグループはそれぞれ何個あるかは, いわゆる鶴亀算で得られる. a+b=638, 4a+8b=4860 だから a=61, b=577である.

そこで, その638の配置をすべて図示したのが次である. 1行に16個, 縦に20行あって, 最初のページに320個, 次のページに318並んでいる. 638個の配置には, 0番から637番 の番号があり, 最初のページの左上が0, そこから右へ1,2,3,...と続く. 次のページの最下行の右端が, 637番である.

これらの図は, 小さ過ぎるので, それぞれの図で, 各クイーンがどのように全盤を支配する かを示す図を描いた. 下の20の図は, 上の図の左端の配置の一つ置きに描いたもので, 塗りつぶしの丸がクイーン, それから四方八方に出る破線が支配領域である. 8×8 のすべての盤面が破線で蔽われているのが分る.

最後に4人仲間の配置はどれかという話題である. 合格発表のような下の番号が, 2回対称軸を持つ61の4人組である.

(20 25 29 30 59 128 129 137 141 149 163 165 171 180 182 183 204 215 219 229 232 238 242 258 259 261 267 276 283 288 289 365 368 372 391 393 441 468 470 473 474 511 516 517 518 524 526 530 551 568 569 574 582 584 592 594 605 617 620 623 633)

この表の0, 15, 30, 45番目を選び(20, 183, 289, 524番になる), 上と同じように 示したのが, 下の図である. 対角線で反転するのが分る. 中のふたつは面白い.