2016年4月30日土曜日

160430

整数列のLINKS の編集(6)

https://oeis.org/A255684
https://oeis.org/A271634
https://oeis.org/A271635
https://oeis.org/A272138
https://oeis.org/A272139
https://oeis.org/A272140
https://oeis.org/A272183
https://oeis.org/A272184
https://oeis.org/A272185
https://oeis.org/A272186
のLINKS を編集しました。

2016年4月29日金曜日

160429(3)

OEIS のb-file の提出の際の注意事項(2)

When you create a b-file there is no need to add a line to the Extensions field, because the b-file is already signed in the Links section.
と返事があった。
b-file の提出の際、EXTENSIONS に自身を加えなくてよいようだ。

160429(2)

Ruby


戦後で素数の年

素数の年(1945~2100)を求めてみた。

require 'prime'

p Prime.each(2100).select{|i| i >= 1945}

出力結果
[1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099]

160429

OEIS のb-file の提出の際の注意事項(1)

https://oeis.org/SubmitB.html
上記にb-file についていろいろ載っていますが、特に重要なのは、以下の部分です。

Question: what size of b-file is acceptable?
Answer: 100, 1000, 10000, 20000 terms are usual. But remember that the numbers cannot have more than about 1000 digits, or some of the programs will fail.

100, 1000, 10000, 20000 terms が普通といっているだけで、
the numbers cannot have more than about 1000 digits の制約の方がきついようです。
実際、1000 terms のファイルを送ったが、桁が多すぎてダメだったことがある。

2016年4月27日水曜日

160427(3)

整数列のLINKS の編集(5)

https://oeis.org/A118067
のLINKS を編集しました。

160427(2)

整数列のLINKS の編集(4)

https://oeis.org/A061006
のLINKS を編集しました。

160427

OEIS のDATA の編集の際の注意事項

DATA を追加したいときの注意事項です。

1. When you add terms to the Data section, you must add a line to Extensions field.
2. When all the Data fits in the Data section you should not create a b-file, because the b-file is created automatically by the system from the Data field itself.
3. Links are in alphabetical order (apart some exceptions).

2016年4月26日火曜日

160426

Ruby


Wilson's theorem

オンライン整数列大辞典の
A061006(http://oeis.org/A061006/list)
と比較し、答え合わせしてみる。

def A061006(n)
  ary = [0]
  (2..n).each{|i|
    j = 1
    (1..i - 1).each{|k|
      j *= k
      j %= i
    }
    ary << j
  }
  ary
end
ary = A061006(94)

# OEIS A061006のデータ
ary0 =
[0,1,2,2,4,0,6,0,0,0,10,0,12,0,0,0,16,0,18,0,0,0,
 22,0,0,0,0,0,28,0,30,0,0,0,0,0,36,0,0,0,40,0,42,0,
 0,0,46,0,0,0,0,0,52,0,0,0,0,0,58,0,60,0,0,0,0,0,
 66,0,0,0,70,0,72,0,0,0,0,0,78,0,0,0,82,0,0,0,0,0,
 88,0,0,0,0,0]
# 一致の確認
p ary == ary0

2016年4月25日月曜日

160425(4)

整数列のCOMMENTS の編集

https://oeis.org/A270814
のCOMMENTS を編集しました。

160425(3)

Ruby


Number of partitions of n into parts that are powers of 3

オンライン整数列大辞典の
A062051(http://oeis.org/A062051/list)
と比較し、答え合わせしてみる。

def A062051(n)
  ps = Array.new(n + 1){0}
  ps[0] = 1
  return ps if n == 0
  ary = (0..Math.log(n, 3).to_i).map{|i| 3 ** i}
  ary.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A062051(69)

# OEIS A062051のデータ
ary0 =
[1,1,1,2,2,2,3,3,3,5,5,5,7,7,7,9,9,9,12,12,12,15,
 15,15,18,18,18,23,23,23,28,28,28,33,33,33,40,40,
 40,47,47,47,54,54,54,63,63,63,72,72,72,81,81,81,
 93,93,93,105,105,105,117,117,117,132,132,132,147,
 147,147,162]
# 一致の確認
p ary == ary0

160425(2)

Ruby


Number of partitions of n into parts that are powers of 2

オンライン整数列大辞典の
A018819(http://oeis.org/A018819/list)
と比較し、答え合わせしてみる。

def A018819(n)
  ps = Array.new(n + 1){0}
  ps[0] = 1
  return ps if n == 0
  ary = (0..Math.log(n, 2).to_i).map{|i| 2 ** i}
  ary.each{|num|
    (num..n).each{|i|
      ps[i] += ps[i - num]
    }
  }
  ps
end
ary = A018819(59)

# OEIS A018819のデータ
ary0 =
[1,1,2,2,4,4,6,6,10,10,14,14,20,20,26,26,36,36,46,
 46,60,60,74,74,94,94,114,114,140,140,166,166,202,
 202,238,238,284,284,330,330,390,390,450,450,524,
 524,598,598,692,692,786,786,900,900,1014,1014,
 1154,1154,1294,1294]
# 一致の確認
p ary == ary0

160425

整数列のLINKS の編集(3)

https://oeis.org/A067593
https://oeis.org/A062051
のLINKS を編集しました。

2016年4月23日土曜日

160423

整数列のLINKS の編集(2)

https://oeis.org/A270814
のLINKS を編集しました。

2016年4月22日金曜日

160422(2)

Ruby


2乗すると回文数になるが、回文数でない数

オンライン整数列大辞典の
A251673(http://oeis.org/A251673/list)
に載っている。

def palindrome?(str)
  str == str.reverse
end

def A251673(n)
  ary = []
  i, cnt = 0, 0
  while cnt < n
    i += 1
    if !palindrome?(i.to_s)
      if palindrome?((i * i).to_s)
        ary << i
        cnt += 1
      end
    end
  end
  ary
end

p A251673(20)

出力結果
[26, 264, 307, 836, 2285, 2636, 22865, 24846, 30693, 798644, 1042151, 1109111, 1270869, 2012748, 2294675, 3069307, 11129361, 12028229, 12866669, 30001253]

160422

Ruby


Numbers whose cube is a palindrome

3乗すると回文数になるが、回文数でないものは、
オンライン整数列大辞典のA002780 のCOMMENTS を見ると、
2201^3 = 10662526601
しか知られていないようだ。

def palindrome?(str)
  str == str.reverse
end

def A002780(n)
  ary = [0]
  i, cnt = 0, 1
  while cnt < n
    i += 1
    if palindrome?((i * i * i).to_s)
      ary << i
      cnt += 1
    end
  end
  ary
end

p A002780(22)

出力結果
[0, 1, 2, 7, 11, 101, 111, 1001, 2201, 10001, 10101, 11011, 100001, 101101, 110011, 1000001, 1001001, 1100011, 10000001, 10011001, 10100101, 11000011]

2016年4月20日水曜日

160420(5)

Ruby


xx…x の累乗(4)

5乗の場合を出力してみた。

(1..9).each{|i|
  (0..20).each{|j|
    p (i.to_s * j).to_i ** 5
  }
}

出力結果
0
1
161051
16850581551
1692662195786551
169342410709747836551
16935003133160595268336551
1693507934088807600450473336551
169350869616759132246099002523336551
16935087723754847838236041084523023336551
1693508779996274280851496214990939728023336551
169350878075835323206320174770104489491778023336551
16935087808345611271994614642076918999475012278023336551
1693508780842181916713238327490728039407949330217278023336551
169350878084294399566461752273535538281764297447882267278023336551
16935087808430202035597554573489813544683229013192433402767278023336551
1693508780843027824349269250961235584006503073701502142288607767278023336551
169350878084302858642822063032396992328405222781078426391640840657767278023336551
16935087808430286626361157682602584463750444546054971125675286626361157767278023336551
1693508780843028670256905282053887449575776050398821317871598164236481566157767278023336551
169350878084302867101898423343325035140476553370929228268046876323053735033616157767278023336551
0
32
5153632
539218609632
54165190265169632
5418957142711930769632
541920100261139048586769632
54192253890841843214415146769632
5419227827736292231875168080746769632
541922807160155130823553314704736746769632
54192280959880776987247878879710071296746769632
5419228098426730342602245592643343663736896746769632
541922809867059560703827668546461407983200392896746769632
54192280986949821334823626479703297261054378566952896746769632
5419228098697420786126776072753137225016457518332232552896746769632
541922809869766465139121746351674033429863328422157868888552896746769632
54192280986976890379176616030759538688208098358448068553235448552896746769632
5419228098697691476570306017036703754508967128994509644532506901048552896746769632
541922809869769172043557045843282702840014225473759076021609172043557048552896746769632
54192280986976917448220969025724398386424833612762282171891141255567410117048552896746769632
5419228098697691747260749546986401124495249707869735304577500042337719521075717048552896746769632
0
243
39135393
4094691316893
411316913576131893
41150205802468724281893
4115205761358024650205781893
411522427983580246909465020781893
41152261316872469135802057613170781893
4115226316872428024691357983539094670781893
411522633539094650246913580242798353909670781893
41152263372427983539135802469135390946502059670781893
4115226337427983539094691358024691316872427983559670781893
411522633744650205761316913580246913576131687242798559670781893
41152263374483539094650205802469135802468724279835390948559670781893
4115226337448539094650205761358024691358024650205761316872448559670781893
411522633744855761316872427983580246913580246909465020576131687448559670781893
41152263374485594650205761316872469135802469135802057613168724279837448559670781893
4115226337448559650205761316872428024691358024691357983539094650205761337448559670781893
411522633744855966872427983539094650246913580246913580242798353909465020576337448559670781893
41152263374485596705761316872427983539135802469135802469135390946502057613168726337448559670781893
0
1024
164916224
17254995508224
1733286088485428224
173406628566781784628224
17341443208356449554776628224
1734152124506938982861284696628224
173415290487561351420005378583896628224
17341529829124964186353706070551575896628224
1734152990716184863591932124150722281495896628224
173415299149655370963271858964586997239580695896628224
17341529915745905942522485393486765055462412572695896628224
1734152991582394282714356047350505512353740114142492695896628224
173415299158317465156056834328100391200526640586631441692695896628224
17341529915832526884451895883253569069755626509509051804433692695896628224
1734152991583260492133651712984305238022659147470338193703534353692695896628224
173415299158326127250249792545174520144286948127824308625040220833553692695896628224
17341529915832613505393825466985046490880455215160290432691493505393825553692695896628224
1734152991583261358343071008823180748365594675608393029500516520178157123745553692695896628224
173415299158326135912343985503564835983847990651831529746480001354807024674422945553692695896628224
0
3125
503284375
52658067346875
5289569361832971875
529195033467961989221875
52921884791126860213551721875
5292212294027523751407729176721875
529221467552372288269059382885426721875
52922149136733899494487628389134447926721875
5292214937488357127660925671846686650072926721875
529221493986985385019750546156576529661806322926721875
52922149401080035224983170756490371873359413368822926721875
5292214940131818489728869773408525123149841656928993822926721875
529221494013419998645192975854798557130513429524632085243822926721875
52922149401344381361242358042155667327135090666226354383647743822926721875
5292214940134461951091466409253861200020322105317194194651899272743822926721875
529221494013446433258818946976240601026266321190870082473877627055522743822926721875
52922149401344645707378617758133076449220139206421784767735270707378618022743822926721875
5292214940134464594552829006418398279924300157496316618348744263239004894243022743822926721875
529221494013446459693432572947890734813989229284153838337646488509542921980050493022743822926721875
0
7776
1252332576
131030122140576
13162141234436220576
1316806585678999177020576
131686584363456788806585020576
13168717695474567901102880665020576
1316872362139919012345665843621465020576
131687242139917696790123455473251029465020576
13168724273251028807901234567769547325109465020576
1316872427917695473252345679012332510288065909465020576
131687242797695473251030123456790122139917695473909465020576
13168724279828806584362141234567901234436213991769553909465020576
1316872427983473251028806585679012345678999176954732510353909465020576
131687242798353251028806584363456790123456788806584362139918353909465020576
13168724279835384362139917695474567901234567901102880658436213998353909465020576
1316872427983539028806584362139919012345679012345665843621399176954798353909465020576
131687242798353908806584362139917696790123456790123455473251028806584362798353909465020576
13168724279835390939917695473251028807901234567901234567769547325102880658442798353909465020576
1316872427983539094584362139917695473252345679012345679012332510288065843621399242798353909465020576
0
16807
2706784157
283207724127657
28448573524584562657
2846137896798731888912657
284626597659030124674932412657
28462787848230589340771105367412657
2846280065648870735660185935409717412657
284628019373147727617233142507578453217412657
28462802065397381838271096885352724008888217412657
2846280207820564277128623177361146154888313238217412657
284628020794864688648413488289386777624176531356738217412657
28462802079614551474199396570136666158329404392961791738217412657
2846280207962735973513522670461311791901612547206557266141738217412657
284628020796286405612288099716643296245491030024725228200309641738217412657
28462802079628768643838168300905486460397297159701146505444630744641738217412657
2846280207962878145209910413385496250063506579281585112364307608935094641738217412657
284628020796287827329251977171501637082253721485545899709224542329251978594641738217412657
28462802079628782861007807075479686365020068079052989889467950346322545682413594641738217412657
2846280207962878287381606801131263865605989432505207539501063850361564124709986763594641738217412657
0
32768
5277319168
552159856263168
55465154831533703168
5549012114137017108103168
554926182667406385752852103168
55492867984222047451561110292103168
5549289295601963245440172114684692103168
554928954531998853963318594257650428692103168
55492895702917915634941827972823113007868692103168
5549289572788971870824699486866783911666582268692103168
554928957303868990160719532591576481774797202326268692103168
55492895730636617046859393515216176395319683652559766268692103168
5549289573066158884993818698499212518416852498772206134166268692103168
554928957306640860302460668264114210232180048304289657741878166268692103168
55492895730664335748276854815497767616725092719050822198513099318166268692103168
5549289573066436072007993361445584644617182340090377876001287066673718166268692103168
554928957306643632172602414943521487708174566885129293846127792172602417718166268692103168
55492895730664363466978272282341783947699029619468576944016528645701027959857718166268692103168
5549289573066436349195007536114074751483135700858608951887360043353824789581534257718166268692103168
0
59049
9509900499
995009990004999
99950009999000049999
9999500009999900000499999
999995000009999990000004999999
99999950000009999999000000049999999
9999999500000009999999900000000499999999
999999995000000009999999990000000004999999999
99999999950000000009999999999000000000049999999999
9999999999500000000009999999999900000000000499999999999
999999999995000000000009999999999990000000000004999999999999
99999999999950000000000009999999999999000000000000049999999999999
9999999999999500000000000009999999999999900000000000000499999999999999
999999999999995000000000000009999999999999990000000000000004999999999999999
99999999999999950000000000000009999999999999999000000000000000049999999999999999
9999999999999999500000000000000009999999999999999900000000000000000499999999999999999
999999999999999995000000000000000009999999999999999990000000000000000004999999999999999999
99999999999999999950000000000000000009999999999999999999000000000000000000049999999999999999999
9999999999999999999500000000000000000009999999999999999999900000000000000000000499999999999999999999

160420(4)

Ruby


xx…x の累乗(3)

4乗の場合を出力してみた。

(1..9).each{|i|
  (0..20).each{|j|
    p (i.to_s * j).to_i ** 4
  }
}

出力結果
0
1
14641
151807041
1523548331041
15240969373571041
152415180613625971041
1524157293095656149971041
15241578417924106081389971041
152415789666209420210333789971041
1524157902149062642981252857789971041
15241579026977594878838591678097789971041
152415790275262917238226794695930497789971041
1524157902758116140832190306355738454497789971041
15241579027586648376771833571101966163694497789971041
152415790275871970736168267033379058070416094497789971041
1524157902758725194330132601737631458619112940094497789971041
15241579027587257430269775948788303612254229538180094497789971041
152415790275872579789666209419295839963420210333790580094497789971041
1524157902758725803383630544124371284956561499771376314580094497789971041
15241579027587258039323273891175125743036122542295381801554580094497789971041
0
16
234256
2428912656
24376773296656
243855509977136656
2438642889818015536656
24386516689530498399536656
243865254686785697302239536656
2438652634659350723365340639536656
24386526434385002287700045724639536656
243865264431641518061417466849564639536656
2438652644404206675811628715134887964639536656
24386526444129858253315044901691815271964639536656
243865264441386374028349337137631458619111964639536656
2438652644413951531778692272534064929126657511964639536656
24386526444139603109282121627802103337905807041511964639536656
243865264441396118884316415180612857796067672610881511964639536656
2438652644413961276634659350708733439414723365340649281511964639536656
24386526444139612854138088705989940559304983996342021033281511964639536656
243865264441396128629172382258802011888577960676726108824873281511964639536656
0
81
1185921
12296370321
123407414814321
1234518519259254321
12345629629703703654321
123456740740748148147654321
1234567851851852592592587654321
12345678962962963037037036987654321
123456790074074074081481481480987654321
1234567901185185185185925925925920987654321
12345679012296296296296370370370370320987654321
123456790123407407407407414814814814814320987654321
1234567901234518518518518519259259259259254320987654321
12345679012345629629629629629703703703703703654320987654321
123456790123456740740740740740748148148148148147654320987654321
1234567901234567851851851851851852592592592592592587654320987654321
12345679012345678962962962962962963037037037037037036987654320987654321
123456790123456790074074074074074074081481481481481481480987654320987654321
1234567901234567901185185185185185185185925925925925925925920987654320987654321
0
256
3748096
38862602496
390028372746496
3901688159634186496
39018286237088248586496
390184267032487974392586496
3901844074988571156835832586496
39018442154549611573845450232586496
390184422950160036603200731594232586496
3901844230906264288982679469593034232586496
39018442310467306812986059442158207434232586496
390184423106077732053040718427069044351434232586496
3901844231062181984453589394202103337905791434232586496
39018442310623224508459076360545038866026520191434232586496
390184423106233649748513946044833653406492912664191434232586496
3901844231062337902149062642889805724737082761774104191434232586496
39018442310623380426154549611339735030635573845450388504191434232586496
390184423106233805666209419295839048948879743941472336532504191434232586496
3901844231062338058066758116140832190217247370827617741197972504191434232586496
0
625
9150625
94879400625
952217706900625
9525605858481900625
95259487883516231900625
952598308184785093731900625
9525986511202566300868731900625
95259868541380887631458618731900625
952598688843164151863283036118731900625
9525986891860996799274119798811118731900625
95259868922039323273891746684956561118731900625
952598689223822588020118941472336534061118731900625
9525986892241655235482395981938728852309061118731900625
95259868922419981710105166895861911294010059061118731900625
952598689224203246456332876086019661636945587559061118731900625
9525986892242035893918609967992689757658893461362559061118731900625
95259868922420362368541380887059899977137631458619112559061118731900625
952598689224203627114769090077732053097850937357110196612559061118731900625
9525986892242036274577046181984453589397576588934613625971612559061118731900625
0
1296
18974736
196741925136
1974518637029136
19752296308148069136
197530074075259258469136
1975307851851970370362469136
19753085629629641481481402469136
197530863407407408592592591802469136
1975308641185185185303703703695802469136
19753086418962962962974814814814735802469136
197530864196740740740741925925925925135802469136
1975308641974518518518518637037037037029135802469136
19753086419752296296296296308148148148148069135802469136
197530864197530074074074074075259259259259258469135802469136
1975308641975307851851851851851970370370370370362469135802469136
19753086419753085629629629629629641481481481481481402469135802469136
197530864197530863407407407407407408592592592592592591802469135802469136
1975308641975308641185185185185185185303703703703703703695802469135802469136
19753086419753086418962962962962962962974814814814814814814735802469135802469136
0
2401
35153041
364488705441
3658039542829441
36593567465944069441
365948848653315956469441
3659501660722670416080469441
36595029781435778701417320469441
365950310988568817925011429720469441
3659503123059899405797988111553720469441
36595031243773205304091458619112793720469441
365950312450906264288982534064929125193720469441
3659503124522236854138088925560128029249193720469441
36595031245235542752629172404215820759030489193720469441
365950312452368601737540009147143118427069042889193720469441
3659503124523699191586648376772053132144490169166889193720469441
36595031245237005090077732053040716973022405121170406889193720469441
365950312452370064074988568815729311752171925011431182806889193720469441
3659503124523700653924096936442615455180704160951074531306806889193720469441
36595031245237006552415180612711476909029730224051211705532546806889193720469441
0
4096
59969536
621801639936
6240453963943936
62427010554146983936
624292579793411977383936
6242948272519807590281383936
62429505199817138509373321383936
624295074472793785181527203721383936
6242950767202560585651211705507721383936
62429507694500228623722871513488547721383936
624295076967476909007776951074531318947721383936
6242950769697243712848651494833104709622947721383936
62429507696994911751257430307233653406492662947721383936
624295076969971592135345221768720621856424323062947721383936
6242950769699738395976223136717338454503886602627062947721383936
62429507696997406434385002286236891595793324188385667062947721383936
624295076969974086818472793781435760490169181527206216067062947721383936
6242950769699740890659350708733424783182075903063557384520067062947721383936
62429507696997408929068129858253315043475957933241883859167560067062947721383936
0
6561
96059601
996005996001
9996000599960001
99996000059999600001
999996000005999996000001
9999996000000599999960000001
99999996000000059999999600000001
999999996000000005999999996000000001
9999999996000000000599999999960000000001
99999999996000000000059999999999600000000001
999999999996000000000005999999999996000000000001
9999999999996000000000000599999999999960000000000001
99999999999996000000000000059999999999999600000000000001
999999999999996000000000000005999999999999996000000000000001
9999999999999996000000000000000599999999999999960000000000000001
99999999999999996000000000000000059999999999999999600000000000000001
999999999999999996000000000000000005999999999999999996000000000000000001
9999999999999999996000000000000000000599999999999999999960000000000000000001
99999999999999999996000000000000000000059999999999999999999600000000000000000001

160420(3)

Ruby


xx…x の累乗(2)

3乗の場合を出力してみた。

(1..9).each{|i|
  (0..20).each{|j|
    p (i.to_s * j).to_i ** 3
  }
}

出力結果
0
1
1331
1367631
1371330631
1371700960631
1371737997260631
1371741700960260631
1371742071330590260631
1371742108367626890260631
1371742112071330589890260631
1371742112441700960219890260631
1371742112478737997256519890260631
1371742112482441700960219519890260631
1371742112482812071330589849519890260631
1371742112482849108367626886149519890260631
1371742112482852812071330589849149519890260631
1371742112482853182441700960219479149519890260631
1371742112482853219478737997256515779149519890260631
1371742112482853223182441700960219478779149519890260631
1371742112482853223552812071330589849108779149519890260631
0
8
10648
10941048
10970645048
10973607685048
10973903978085048
10973933607682085048
10973936570644722085048
10973936866941015122085048
10973936896570644719122085048
10973936899533607681759122085048
10973936899829903978052159122085048
10973936899859533607681756159122085048
10973936899862496570644718796159122085048
10973936899862792866941015089196159122085048
10973936899862822496570644718793196159122085048
10973936899862825459533607681755833196159122085048
10973936899862825755829903978052126233196159122085048
10973936899862825785459533607681755830233196159122085048
10973936899862825788422496570644718792870233196159122085048
0
27
35937
36926037
37025927037
37035925937037
37036925926037037
37037025925927037037
37037035925925937037037
37037036925925926037037037
37037037025925925927037037037
37037037035925925925937037037037
37037037036925925925926037037037037
37037037037025925925925927037037037037
37037037037035925925925925937037037037037
37037037037036925925925925926037037037037037
37037037037037025925925925925927037037037037037
37037037037037035925925925925925937037037037037037
37037037037037036925925925925925926037037037037037037
37037037037037037025925925925925925927037037037037037037
37037037037037037035925925925925925925937037037037037037037
0
64
85184
87528384
87765160384
87788861480384
87791231824680384
87791468861456680384
87791492565157776680384
87791494935528120976680384
87791495172565157752976680384
87791495196268861454072976680384
87791495198639231824417272976680384
87791495198876268861454049272976680384
87791495198899972565157750369272976680384
87791495198902342935528120713569272976680384
87791495198902579972565157750345569272976680384
87791495198902603676268861454046665569272976680384
87791495198902606046639231824417009865569272976680384
87791495198902606283676268861454046641865569272976680384
87791495198902606307379972565157750342961865569272976680384
0
125
166375
170953875
171416328875
171462620078875
171467249657578875
171467712620032578875
171467758916323782578875
171467763545953361282578875
171467764008916323736282578875
171467764055212620027486282578875
171467764059842249657064986282578875
171467764060305212620027439986282578875
171467764060351508916323731189986282578875
171467764060356138545953360768689986282578875
171467764060356601508916323731143689986282578875
171467764060356647805212620027434893689986282578875
171467764060356652434842249657064472393689986282578875
171467764060356652897805212620027434847393689986282578875
171467764060356652944101508916323731138597393689986282578875
0
216
287496
295408296
296207416296
296287407496296
296295407408296296
296296207407416296296
296296287407407496296296
296296295407407408296296296
296296296207407407416296296296
296296296287407407407496296296296
296296296295407407407408296296296296
296296296296207407407407416296296296296
296296296296287407407407407496296296296296
296296296296295407407407407408296296296296296
296296296296296207407407407407416296296296296296
296296296296296287407407407407407496296296296296296
296296296296296295407407407407407408296296296296296296
296296296296296296207407407407407407416296296296296296296
296296296296296296287407407407407407407496296296296296296296
0
343
456533
469097433
470366406433
470493429496433
470506133060396433
470507403429369396433
470507530466392459396433
470507543170096023359396433
470507544440466392332359396433
470507544567503429355422359396433
470507544580207133058986322359396433
470507544581477503429355295322359396433
470507544581604540466392318385322359396433
470507544581617244170096021949285322359396433
470507544581618514540466392318258285322359396433
470507544581618641577503429355281348285322359396433
470507544581618654281207133058984912248285322359396433
470507544581618655551577503429355281221248285322359396433
470507544581618655678614540466392318244311248285322359396433
0
512
681472
700227072
702121283072
702310891843072
702329854597443072
702331750891653443072
702331940521262213443072
702331959484224967813443072
702331961380521262023813443072
702331961570150891632583813443072
702331961589113854595338183813443072
702331961591010150891632394183813443072
702331961591199780521262002954183813443072
702331961591218743484224965708554183813443072
702331961591220639780521262002764554183813443072
702331961591220829410150891632373324554183813443072
702331961591220848373113854595336078924554183813443072
702331961591220850269410150891632373134924554183813443072
702331961591220850459039780521262002743694924554183813443072
0
729
970299
997002999
999700029999
999970000299999
999997000002999999
999999700000029999999
999999970000000299999999
999999997000000002999999999
999999999700000000029999999999
999999999970000000000299999999999
999999999997000000000002999999999999
999999999999700000000000029999999999999
999999999999970000000000000299999999999999
999999999999997000000000000002999999999999999
999999999999999700000000000000029999999999999999
999999999999999970000000000000000299999999999999999
999999999999999997000000000000000002999999999999999999
999999999999999999700000000000000000029999999999999999999
999999999999999999970000000000000000000299999999999999999999

160420(2)

Ruby


xx…x の累乗(1)

2乗の場合を出力してみた。

(1..9).each{|i|
  (0..20).each{|j|
    p (i.to_s * j).to_i ** 2
  }
}

出力結果
0
1
121
12321
1234321
123454321
12345654321
1234567654321
123456787654321
12345678987654321
1234567900987654321
123456790120987654321
12345679012320987654321
1234567901234320987654321
123456790123454320987654321
12345679012345654320987654321
1234567901234567654320987654321
123456790123456787654320987654321
12345679012345678987654320987654321
1234567901234567900987654320987654321
123456790123456790120987654320987654321
0
4
484
49284
4937284
493817284
49382617284
4938270617284
493827150617284
49382715950617284
4938271603950617284
493827160483950617284
49382716049283950617284
4938271604937283950617284
493827160493817283950617284
49382716049382617283950617284
4938271604938270617283950617284
493827160493827150617283950617284
49382716049382715950617283950617284
4938271604938271603950617283950617284
493827160493827160483950617283950617284
0
9
1089
110889
11108889
1111088889
111110888889
11111108888889
1111111088888889
111111110888888889
11111111108888888889
1111111111088888888889
111111111110888888888889
11111111111108888888888889
1111111111111088888888888889
111111111111110888888888888889
11111111111111108888888888888889
1111111111111111088888888888888889
111111111111111110888888888888888889
11111111111111111108888888888888888889
1111111111111111111088888888888888888889
0
16
1936
197136
19749136
1975269136
197530469136
19753082469136
1975308602469136
197530863802469136
19753086415802469136
1975308641935802469136
197530864197135802469136
19753086419749135802469136
1975308641975269135802469136
197530864197530469135802469136
19753086419753082469135802469136
1975308641975308602469135802469136
197530864197530863802469135802469136
19753086419753086415802469135802469136
1975308641975308641935802469135802469136
0
25
3025
308025
30858025
3086358025
308641358025
30864191358025
3086419691358025
308641974691358025
30864197524691358025
3086419753024691358025
308641975308024691358025
30864197530858024691358025
3086419753086358024691358025
308641975308641358024691358025
30864197530864191358024691358025
3086419753086419691358024691358025
308641975308641974691358024691358025
30864197530864197524691358024691358025
3086419753086419753024691358024691358025
0
36
4356
443556
44435556
4444355556
444443555556
44444435555556
4444444355555556
444444443555555556
44444444435555555556
4444444444355555555556
444444444443555555555556
44444444444435555555555556
4444444444444355555555555556
444444444444443555555555555556
44444444444444435555555555555556
4444444444444444355555555555555556
444444444444444443555555555555555556
44444444444444444435555555555555555556
4444444444444444444355555555555555555556
0
49
5929
603729
60481729
6049261729
604937061729
60493815061729
6049382595061729
604938270395061729
60493827148395061729
6049382715928395061729
604938271603728395061729
60493827160481728395061729
6049382716049261728395061729
604938271604937061728395061729
60493827160493815061728395061729
6049382716049382595061728395061729
604938271604938270395061728395061729
60493827160493827148395061728395061729
6049382716049382715928395061728395061729
0
64
7744
788544
78996544
7901076544
790121876544
79012329876544
7901234409876544
790123455209876544
79012345663209876544
7901234567743209876544
790123456788543209876544
79012345678996543209876544
7901234567901076543209876544
790123456790121876543209876544
79012345679012329876543209876544
7901234567901234409876543209876544
790123456790123455209876543209876544
79012345679012345663209876543209876544
7901234567901234567743209876543209876544
0
81
9801
998001
99980001
9999800001
999998000001
99999980000001
9999999800000001
999999998000000001
99999999980000000001
9999999999800000000001
999999999998000000000001
99999999999980000000000001
9999999999999800000000000001
999999999999998000000000000001
99999999999999980000000000000001
9999999999999999800000000000000001
999999999999999998000000000000000001
99999999999999999980000000000000000001
9999999999999999999800000000000000000001

160420

新たな整数列(2)

https://oeis.org/A272066
https://oeis.org/A272067
https://oeis.org/A272068
が追加されました。

2016年4月19日火曜日

160419

Ruby


99…9 の累乗

http://www004.upp.so-net.ne.jp/s_honma/relax/integer13.html
を見て、99…9 の累乗の各桁の数字の和を計算してみた。

5乗までは規則正しい。

(1..6).each{|i|
  (0..15).each{|j|
    m = ('9' * j).to_i ** i
    p [m.to_s.split('').map(&:to_i).inject(:+), m]
  }
  p ''
}

出力結果
[0, 0]
[9, 9]
[18, 99]
[27, 999]
[36, 9999]
[45, 99999]
[54, 999999]
[63, 9999999]
[72, 99999999]
[81, 999999999]
[90, 9999999999]
[99, 99999999999]
[108, 999999999999]
[117, 9999999999999]
[126, 99999999999999]
[135, 999999999999999]
""
[0, 0]
[9, 81]
[18, 9801]
[27, 998001]
[36, 99980001]
[45, 9999800001]
[54, 999998000001]
[63, 99999980000001]
[72, 9999999800000001]
[81, 999999998000000001]
[90, 99999999980000000001]
[99, 9999999999800000000001]
[108, 999999999998000000000001]
[117, 99999999999980000000000001]
[126, 9999999999999800000000000001]
[135, 999999999999998000000000000001]
""
[0, 0]
[18, 729]
[36, 970299]
[54, 997002999]
[72, 999700029999]
[90, 999970000299999]
[108, 999997000002999999]
[126, 999999700000029999999]
[144, 999999970000000299999999]
[162, 999999997000000002999999999]
[180, 999999999700000000029999999999]
[198, 999999999970000000000299999999999]
[216, 999999999997000000000002999999999999]
[234, 999999999999700000000000029999999999999]
[252, 999999999999970000000000000299999999999999]
[270, 999999999999997000000000000002999999999999999]
""
[0, 0]
[18, 6561]
[36, 96059601]
[54, 996005996001]
[72, 9996000599960001]
[90, 99996000059999600001]
[108, 999996000005999996000001]
[126, 9999996000000599999960000001]
[144, 99999996000000059999999600000001]
[162, 999999996000000005999999996000000001]
[180, 9999999996000000000599999999960000000001]
[198, 99999999996000000000059999999999600000000001]
[216, 999999999996000000000005999999999996000000000001]
[234, 9999999999996000000000000599999999999960000000000001]
[252, 99999999999996000000000000059999999999999600000000000001]
[270, 999999999999996000000000000005999999999999996000000000000001]
""
[0, 0]
[27, 59049]
[54, 9509900499]
[81, 995009990004999]
[108, 99950009999000049999]
[135, 9999500009999900000499999]
[162, 999995000009999990000004999999]
[189, 99999950000009999999000000049999999]
[216, 9999999500000009999999900000000499999999]
[243, 999999995000000009999999990000000004999999999]
[270, 99999999950000000009999999999000000000049999999999]
[297, 9999999999500000000009999999999900000000000499999999999]
[324, 999999999995000000000009999999999990000000000004999999999999]
[351, 99999999999950000000000009999999999999000000000000049999999999999]
[378, 9999999999999500000000000009999999999999900000000000000499999999999999]
[405, 999999999999995000000000000009999999999999990000000000000004999999999999999]
""
[0, 0]
[18, 531441]
[45, 941480149401]
[72, 994014980014994001]
[99, 999400149980001499940001]
[126, 999940001499980000149999400001]
[153, 999994000014999980000014999994000001]
[180, 999999400000149999980000001499999940000001]
[207, 999999940000001499999980000000149999999400000001]
[234, 999999994000000014999999980000000014999999994000000001]
[261, 999999999400000000149999999980000000001499999999940000000001]
[288, 999999999940000000001499999999980000000000149999999999400000000001]
[315, 999999999994000000000014999999999980000000000014999999999994000000000001]
[342, 999999999999400000000000149999999999980000000000001499999999999940000000000001]
[369, 999999999999940000000000001499999999999980000000000000149999999999999400000000000001]
[396, 999999999999994000000000000014999999999999980000000000000014999999999999994000000000000001]
""

2016年4月13日水曜日

160413(2)

Ruby


Zagier's problems(11)

m = 3, n = 3006 のときの計算結果を残しておく。

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

(3005..3007).each{|i| p u(3, i)}

出力結果
(8789763072261216644847961892862474902881953191719492947103692284723618653011510640270176657813209781676960562568105922686702611192815615865871973641400995128973065418357485925282338491787518734891452258625661645106127580575821415774945751907044192435875274520801913570189458902998779666136405398242289587266908111690414311600615142058820980962502098383212842718090779883355302819069636587110119761448133394934238086972036678263518933150885666820523009986601926574855856864641710854919180392524663903599989161359083499536758536374013479941456621589916161537339824360300524646707240534081534231408237700333387319688446761400589423351439511403531011015941223861008475659830379840875555291999870441449206615984329601926506539860097353985353771641777226213922221397997346622700052349344401033797960008754363753499454113990412302918048095183360226648316626403550131637578035135866586192530984344796522005496611873059352648047194190683129432860385170396116384638109225633803740856212628938303212868433702400796807233913785940496441437975606582103908657649181303034784808196958988327571803434288352209479937609066009045054484401489575272807428745015534340192486679145585021312559263567742581412375566985046272538262300085100422726092360319208389472832540195181317184439567306318123235132320462920407151725747995122315342507921075116047536003651637617030455292513893602569835774016816222324006877448589401892396007719685479861865646911056541917753653159813660814779813032361954689819584744010715425731296507161180752269735141944079680594352489280084954372457775554556085461487055115091669188618274940411633120945455714665265713035429248486880739701419052878472296904861024170201850086156668617423099328947942056020144294786581623455056938218969712579845902923837659547256061710195426428478309698643145875254411287706797175119102443578474392505765196484930892826128962063275077918160893895362227770594210641970913619169656884147758232220461010811802597163523360105915383172016185763471801724854478919607570365455845960889135924107410271536757448424659975013552983034428765432117473049225572381062931714603891754548184987033949440016936419408687014117697067445280231102146320716054762314640243312373877929902023351477803979789696313171861356539108759678513936421408479773855281330934953662215735786482875818355673529024799525038772462779167991572145972618022404859608048255416324926899764282806443567403838825829521600486343663575277578667627201251234827760129979048375345188785507086161694673778433442095750401465973821735753267160759464748340273074390363589865124909729166235828847790049141653681054639106003378615571287782392207391942138629231467470601711932875346508399633996475944750707912879157346363360848819342452880064473753712583870743501710744566663214826346828679965001367445843547615306851298818934717345898328905631070135999542399966199663689954424241620790425633124931535955976924796608722467219810287702234735486081000481195431584343335171272443350408817471513699480414621660518972703312101099583153845089279006653875161483813335420737306953401142770827321699098553139390326207479869201642518740131957403716096690249731/36063)
2668494861972540640088607624237263567681655033744320618211489470092957601225239802147903540921906044466012827366934583102703618743025598769339390825666136448201478660980321218001432747397894572947637214921518569950456001240294294228523852284633073244571995408337855813512634363874628803073199449713999613016253960856531512771455973553193799445482270787882773781874691344177998264254457818657519163908972472329164025938858659651484839225659879311988805075080655262181669174868963518793495994078896462067519213153181532306919740189131988928793765987085548808973982801039027276752325253918641404075590934928393493258405941959865549945951822401843024753461634413488791996307441255964250230324445554197746359785468071518394597821417774695465291659639214784676947418765134034231621486262152714281401464812738636456863443035404028404054638826786399020926211699644369603903965098047795000482244494410064284830323741610591268745025577051827267833412167585709783293360812311668673259617317954638737238052747248920033941943671693266119024439807441036160394740424600326001560678263638326912223729383307711667840064894607296231511527029869982532591926812833259771754732721473550022933771487694536155797861018068662176130658579179202832352146387061451694061469844862567930148119858865157811361048719350031864630848757310216784829619905966826942348715534384593135226069631793513265139345205558350381704892468515316726213430630963437100664189676056854214860304252747116708732281581471672273691284897040658791680948932551845877704342490568457836692789043437117083052756873723946053800521374853663532120662746871557982890632247120480467131793919249158327099970203304709970882667248106377204390790825289547495326440711849724285271720342308322654336894472062251721595321177100755827619211727690084006918805963766516251655246831820021101910842111251862666942984922736445780484570191700817978546456372883038043670234890275289194434076137220173887679596165274621228057383217799807381326388637178813821748477685830271493668802940555829353834708781955410021860959872853862926676364403444285049725987428255614654380437327546448635069054247177326638275580486446110578023281240082919311238967263719845973825151953529145908877508429449916363636795401071655716317148464140720102003907994738518651350538709537358725524470916642411085685068254492526022396486022553497551498517572305282200139546841594742485274630333742535863511349541510520094582951861569963216028638980076487643223837877695956140411020255181747615902772209882021279272371749485093720848937840442732560227443973761689617596337092024035991236072690284490947776822135493161092589901020367780974563833028231726359724175683530221167439650531191119609988250080246579220512641424100790792907737705679358927862632378320205393386485545254343608254272798046137445408705176020843540133482147644308841321820119095385502715819030162656646476384180768758453993009975839401297541843357853751824159382857248588590178473861247173121395412579674438909105679058005571751753312115640267170677790515939657934036241420268030256820444129615880562575227993877527139296140855456692849289035638075990313068738870
(1054309822269915110600442730220874120418883909712601485949540111838389206814941328897751389237514766468736053635117934948300292209233714505057116985716351392015712892784829152950378116347371024253379035865907932276745914497295805740057725378005151238584750804492905009325767279989557092689671471478553422044804900467564177613151333645393959462528082133538864325857316066266630714450245460313852922352778003529821972829864844472080571163064766515787572780954923571187772037084499682569529045684731227869245587880322735171773685034279787637846069895174082784822206769540275547944842411371121567825208350671613969636370705594166623272159165385539211023251809869071382605077252438835410787569362526740862220163417137293681055635349817158235417962045099427076192473803532909194136355483992102854761158742839209102871139160769378323316770258057528325439581043057198875095639784873663191997505294414123777154202091596731889704962810680556169500401858844278189068242667064637465267940576955340242307241080422917628017497442225579343397806253828041565251487331103528876652318834978896916572585255808645478387855275155702576917882090384385519452876762056843082804274875616919898579385277539552830106281715510858862571225824189084021050653858174032429127438252431301386903584296356823915396893436141481428816153784879971347670135021806918875123857314910733875075289805058997305038682780322058050205676633203387062577672755161268299917543798090893692920138012637370122220689061984326972394241848600027005483127766393473741990927525088901606409720424653191830586347646564010405416499670063587823785881044877874358255541695292304155269777522935809985439617648480096446585464454557666403549991039005282571679104051438232154369361506317448455434138026233030773136311757279949002967416099267782820918536192608448772444981594265054667914398687496954144507412749142708077774638741601111894050084698831666000660341059012655997131698556900064375227970676832243946177041798853913208723122514465070194479800605024229549059816567757532802768828334941333365578506757576993753873201706319691875217370816559416071283945456711770282657940365028857790095909586683792919158575288031901198696646189115723951086377883392631854243969004962116470528905981635518190655618988492250549212902165908602013620009168472093959946319572459750682135626518218640807373135154548928868924006403132175343883730680497260613052500815716177224794110804355992054958535969123302392446067575116520932643953546020989503599539649188230608485211269526447693009576212357867841061081044172327508841706066965693218843377810344704407820677282349997435703170807353280769114358208695546048486848275546937210087785314945136863383969540883643575352103939875220196871487507448783444951553943605878193023433588032019772758103600360086663321461117967817378751602019463380489159210280484855811366956351720861626716264451293030442633085100559006735880731039428128135563129866100465188105629581586994438495981255698860571809423467160638858173021567939423857542509059068869862060193947626634283584066478140890425817332847070847530214018501825682992520923829027237139182053016969833512850948063819171/36087)

160413

Ruby


Zagier's problems(10)

m = 5, n = 196 のときの計算結果を残しておく。

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

(190..200).each{|i| p u(5, i)}

出力結果
(14096922886878560361335788817154728199798428416254259239690126227412717494279242744885446032320006077757571420585333094476837266931412679357223627408073913710663264928402597278964770272621778099851913481302243430074505739640018230274303208289030498671883402934119131578330068074908960836562780185014295700732017844/5705)
(124986505056204611409009555132533466163901413328921120429053202544167993963952358227335809779686077744167837827204340115494700960030565447866788610852515859477162518308957099770037857047229094294860960786374202220231297888906516948302554246934333006937003041061039838632339276873281118924934440104513661400483694808/1147)
(27703965204891092190861560363395388039986658437725672403625445307986004215898496854365631405464858723553599285347435970756381438683067982505528628800625855347124348948156445916183446125518040658290849780845314245998005214264657113911688456155021139123548857215083084441870785851658653894097623547062189581304563768132/5765)
(1228148091233815050052958419210126612524844315005562951783519373592877523355790891395756160550693916540899220202237801122612252644741224118051699654375408165019080020843100055139056546466390902769491377489958122318550666429362907760791683976744901000112970574765397994203294380055335653394969971676475314692575636516479/5795)
(54445193056153811412056862596370167876223873867082957601678911375022525503157093226353797320000307546461886455892884704571408839383761689187751753837083021804115367916578903837399928129550224273788323022818256933895270089423673457676885432114780252007469796438030281822903616814653961900360170376807076804109794516249413/5825)
(2413616947402411616676741451517267513528638802008443525312198879373539437285699820243147938542481339297423963802129347301094141782063408826084261649771864134686014205444511491443301872478590618968853867861245510959115122584957961052517803983012396993907227859643363768391025750830073959352608287561703251067127503684705229/5855)
18181540761540712867149487897053111408341145153247021925742297078013378875918440895079511284629222125948897573866467613788397445534812254595922136833868755211587284257245954094057967606737047389560734422923576883191584992444803051004333753987804237556089739248567296230384275913141809451316512176176377053312906111739000
(4743358565932963848095491665985122216650207829948956324154504038186089524765496114993915291969756350781023801019272206655357377755866659520010906834744364101420092177060177807314020268372200539994761360652698124737441342421527858536862221380708754404696710971290364464165568190402315407515194885444978408637736425531193116524/5915)
(42055689326087115762783402823125733699826295093344726808790573319464007329213101151235893565233316965204569718371598113197970569412479945738957000670791549732822027499394896866257172662185531178825309459166679779923773314959820184133293532950727048075258277284458499371731392536785755174046448700085118409447913062966683916919/1189)
(9321881216165652840273527917467630283950547748371610933737455857725642086131629624711182672950147237203302293120429774901540426519471243432702750308438234254139399789921208901254874816723162779833911372678185485081404386352193067105351817762135529682005488932497168730911200884508027219942175578078870222502568940488317547673957/5975)
(413249530804383173485275814472324437620635643432036662479799372337212013144150979354876931502961993685566541310681669294760175877220158686677328394523077300538238183248829631436826842120471524918631177941266315869588930609048606478273028565442188335846010022617201120108944030409468018235323923914203958076324506866736290311266247/6005)

2016年4月12日火曜日

160412(3)

Ruby


Zagier's problems(9)

m = 7 のとき、n = 26 と非常に小さいので、計算結果を残しておく。

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

(0..30).each{|i| p u(7, i)}

出力結果
1
(10/9)
(12173/17)
(1248801/25)
(301500013/33)
(47068369985/41)
(8954530878371/49)
(3616616044683269/133)
(1961307671216691883/455)
(347559287308451008967/511)
(62140698954891656421190/567)
(11067012620150133414337963/623)
(1974249851740493659523015623/679)
(351951838629631165144467430043/735)
(62758674512597558743883263610439/791)
(11189954786512984420393651687875941/847)
(1995221638416328054526045855047718383/903)
(355758150892408390230576747504182000459/959)
(9061863319798195260695461954546882409601/145)
(11310428571396007320666762754450306819217990/1071)
(2016696277341169111795798300521062697437592955/1127)
(51369491523983014450494440607772389176868751201/169)
(64115828922334414331872309869748783481829146350651/1239)
(2286429018304177791698795890230227079657492052657499/259)
(2038402280444992115457711912936851219673442797789253973/1351)
(121152109309790470247346317829552539155749638441881956677/469)
44296575390001702400727108630616445125994678211370369389
(11555181554561385935252392348829213521467268425671827881007431/1519)
(27471209267637854163021521429848295616923998565176365935567890/21)
(367367999320644246065591385425231039259955915933569408248236141643/1631)
(9357623280737482868324329801122570121966749493440849706709392542081/241)

160412(2)

Ruby


Zagier's problems(8)

30 以下のm に対し、
U(m, n) = 0 mod ((m + 1)mn + m) となる10^3 以下のn を探してみたが、
新たなものは見つからなかった。

require 'prime'
require 'matrix'

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

def U(m, n)
  i = m * ((m + 1) * n + 1) * u(m, n)
  j = i.denominator
  return i.to_i if j == 1
  i
end

def berlekamp_massey(s, q)
  b, c = [1], [1] + [0] * (s.size - 1)
  l, m, a = 0, -1, 1
  s.size.times do |n|
    d = (0..l).inject(0) {|sum, i| (sum + c[i] * s[n - i]) % q}
    next if d == 0
    t = c[0..l]
    (0...[s.size - n + m, b.size].min).each do |j|
      c[n - m + j] = (c[n - m + j] - d * a * b[j]) % q
    end
    b, l, m, a = t, n + 1 - l, n, mod_inv(d, q) if 2 * l <= n
  end
  c[0..l]
end

def euclid(a, b)
  return [0, 1] if a == 0
  q, r = b.divmod(a)
  x, y = euclid(r, a)
  [y - q * x, x]
end

# x^(-1) (mod n)
def mod_inv(x, n)
  euclid(x, n)[0]
end

# x % n1 = r1, x % n2 = r2, |x| <= n1 * n2 / 2 となる x
def chinese(n1, r1, n2, r2)
  x = (n1 * (r2 - r1) * mod_inv(n1, n2) + r1) % (n = n1 * n2)
  2 * x > n ? x - n : x
end

# f を多項式として f=0 が数列 s を生成する漸化式の特性方程式となっているか
def test(f, s)
  (0..s.size - f.size).all? do |i|
    f.each_with_index.inject(0) {|sum, (fj, j)|
      sum + fj * s[f.size + i - j - 1]
    } == 0
  end
end

# 数列 s を生成する漸化式の特性方程式を返す
def polynomial(s)
  f, n = [], 1
  Prime.each do |q|
    c = berlekamp_massey(s, q)
    if c.size != f.size then
      f, n = c, q if c.size > f.size
      next
    end
    f = (0...f.size).map {|i| chinese(n, f[i], q, c[i])}
    return f if test(f, s)
    n *= q
  end
end

def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end

(1..30).each{|i|
  a = (0..70).map{|j| U(i, j)}
  ary0 = a[0..i].reverse
  v = Vector.elements(ary0)
  b = polynomial(a)[1..-1].map{|i| -i}
  ary1 = [b]
  (1..i).each{|j|
    c = Array.new(i + 1, 0)
    c[j - 1] = 1
    ary1 << c
  }
  a = Matrix[*ary1]
  p [i, b]
  (1..10 ** 3).each{|n|
    mod = (i + 1) * i * n + i
    p n if (power(a, n, mod) * v)[i] % mod == 0
  }
}

出力結果
[1, [3, -1]]
[2, [5, 2, 1]]
[3, [7, 39, 47, -1]]
[4, [9, 244, 974, 44, 1]]
[5, [11, 1205, 12240, -6915, 1862, -1]]
196
[6, [13, 5466, 120994, -573455, 736546, -1401, 1]]
[7, [15, 23919, 1050959, -22723953, 110533535, 1824095, 118911, -1]]
26
[8, [17, 102824, 8460428, -660176392, 9869354006, 6085682408, 1508966588, -39688, 1]]
[9, [19, 437409, 64949424, -16192124931, 648337672368, 2952342946923, 3894121358913, 4763358099, 11078999, -1]]
[10, [21, 1847350, 483413545, -358291324370, 35009923530009, 762890018040083, 4188043855001225, -182235342002781, 6583812979820, 4453415, 1]]
[11, [23, 7759499, 3523969075, -7414855062747, 1655869761962031, 138648674320218931, 2635123530005084591, -1688681444362225434, 408664303524650140, -41645279399229, 1396175079, -1]]
[12, [25, 32449572, 25323785876, -146587296887370, 71319047071085059, 20099366524056007707, 1162024896470173371206, -5204260952032364622193, 6971648686749725994911, 8477140085006196408, 52958171121812826, 241715044, 1]]
[13, [27, 135207449, 180156871817, -2804879528372090, 2868400112861466014, 2492560689703083279930, 399389082850915473829565, -8926182043784021011110336, 53094778469801586326939455, 3128041494206498361326341, 105597156449033922867753, 301538303449199466, 226596128072, -1]]
[14, [29, 561631994, 1272408593694, -52388587804787871, 109563669085217616395, 276083782428714928966760, 114419065428338081579334996, -10468526084576268156997237369, 234390509230588509337272646276, 153424296348875510087886554231, 36722885401600458559804957166, 1720582478121209830781787, 713152249213442249617, -43297518782, 1]]
[15, [31, 2326762335, 8938922445535, -960571324607253025, 4021508312094118185631, 28098845330083486840967327, 28572394941552938109249498399, -9391029866089300888998320603105, 700667210683556452385756293760063, 3110005804419901172431450191758655, 4209154221628873287039480122665663, -14418872031546554023899152599361, 58689887152771403100622098175, -1759326656669521249921, 45736987649023, -1]]
[16, [33, 9617285712, 62545084121816, -17358074283665720208, 143039972119814721572476, 2679564075937303669672760528, 6415359896444135473788729612520, -6907456119305774955804889300474960, 1566825755535442411011263856161033958, 35816981658086098063925438131056321680, 225500682943244250904816988922008540168, -15530000025888621561116852250088897744, 521404514838801819415405779219688028, -3107756130838235032682789117488, 14994509199253822401823992, -5171381626384, 1]]
[17, [35, 39671305145, 436257179818040, -310008803636947199623, 4960757197260488487925460, 242773210547872333552259186021, 1324295112182451699815856166600394, -4363437479618022368501295269458939756, 2803634075970619263852891559265494318356, 276192628838986292498439882489348674430309, 6965625678463465208753167218723002645480619, -4620631309137082753926772114771202028120789, 1099082364967202515220948071220482721597232, 111514822222202097430316891987657961539, 63509526685299141560432641841349488, -13038746933043068727180655, 11181822035300270, -1]]
[18, [37, 163352434734, 3035347600432035, -5483352175642569201270, 168525285671345885804336862, 21111120663788472650084288824179, 255476921859062437593949054028795616, -2445426940718932476008794975741660304175, 4209547444358562525826465510219653897123103, 1577034837517910141814357057175949581552545088, 142085605912370280239491343390682656623734410463, -627155545723849654644133035196349683650443828766, 855031172075310637453020264972368407113733074903, 4474287103242990877612440100264298095080792487, 17660592940556734104819327959068387708713660, 4938119184824946106741841351313842022, 466883028316202113015226128881, 886349882096658, 1]]
[19, [39, 671560011459, 21075944758600939, -96204908762379350733151, 5627807292645114966712061052, 1775408164885289172297821447021812, 46631243225027993034934722755755085272, -1244943080840553777420534228311997038019063, 5490113826664352415532136668126358739292538767, 7131683541248525923952460949892622626850079498864, 2099563884259161786823613525488704694896604209397914, -48877528095396482081566878764733449679003021189084196, 321013235322298636586608290451177420155750415632135436, 24340068980214041589807399784070362876599663933001886, 822940585664951397307635428416847725622360060212332, 1393013356539636402395987786150357038618928807, 123972522973841259438323331152023173999576, 1125618445234955946788827920514, 3243775901948708124, -1]]
[20, [41, 2756930575580, 146090323000082110, -1676304091251820140507720, 185250523385580096841161863748, 145238554921778505243156068327169341, 8129619529588844130155364032128315940841, -585970068390114889642119074038871146438778925, 6382488002779150273932948195654123641791635993430, 26784653740114006828747574640011406178549629168981162, 24005319059233782296713266398218163277894369391654926896, -2508957684634098052278464585484486920678819318569854388505, 69262029317912981070794957046174095338303279322999634911432, 46365912349438088971444446930915889349603479059561578703915, 10984200533063298251903997817276922194733615260858349978556, -3056426216134415781452329430830517144888502088811197774, 1297114645624223933392815921716156038308768220380370, -10327998255514435812954411211966797448283492, 20652638432558829230819157018728540, 245432414580664255, 1]]
[21, [43, 11303415362337, 1011156063807341396, -29035399664747608561690625, 6023711112900136395040156907688, 11609654655472455600089795524802844941, 1363760272943888489406903273303816976519316, -258457383899007671626646725347504163331647810783, 6746000232774468888091807408250179386355061938375459, 86506449066302193205709474408126459835928886005781792141, 222904534370827669806218961010277884194518907649487169652104, -92921274753107240269259377948247474796376249254674371803683057, 9682936583105386826410845686557689131096901605094859118000055365, 42577456341780419848291721987896989011847079620246626542863679162, 58366104601062041025374888336482134439975255926955213450172693122, -390773395206202922064828748815897117103164096961837783799637737, 1582429335753544083633104422656978078808322414673282526823534, -578451604946024310072069713170669686817797558620582008, 410937114622497185581008633822950431758593429575, -39246412659908403203222371946053336, 1098260202508469941676, -1]]
[22, [45, 46290177200850, 6989702077681491630, -500329172292866779827100455, 193822660841954559871723693585764, 910024743391317951203645021099276455315, 221421564995894029946521509657035313365949175, -107957097521408185327042740428298868114075500468590, 6583182695330724075962456693433738328751384879379444673, 246660492871004909815536774445471563149270063142495584386796, 1743577068422193619412504827501290437012369366870716339580671678, -2648190132348149916648597266946794838400369283872971746390698777016, 955823014414894746780984078736586734245190815958566258896507588582262, 22578250025148213864539183836864407003616497174927509505731734250384547, 153207019602842468310705683987800988280091876452216498318568800479455334, -12401992259283144628513778379921203407089737145552208698348176823716022, 423205257443890713468979355951488942902569850269036648726119802561657, 3725354962289136961902404504818727663398748425247191170811302608, 191381107857982731322107317587073882501110180991835046265401, 28287915681866800257845035082718893345978832415666, 1255140906768948796325962733401935553146, -25447595746049660337, 1]]
[23, [47, 189368906733719, 48262145117157829095, -8582409546039438773469947445, 6180022475187740343388390465458699, 70148253828584196583082322106445911749027, 34958574079132006352399164891456528910141999539, -43059805894566220882713053004027329882395535305112915, 6004113743807914249641565318277378279220466767948259610865, 633668743787930081222436844007768545854196806586917623904513169, 11817472644499080340314799703499093195002850692252712835613235903172, -60897524596924779998380567879954792428574021370879491822963717332710176, 70994037752631297846379514901303689121949234902526371363739936156721230092, 7781537563495837382949659016369576787193970152522252236094187199588920123084, 230617396751754553915730834670982580636006326247940838423231524925977110278014, -155408455724654079133519208864206555696405739832313751989131529815042944206859, 36711685193001388177253221408626080190829392709931992989168683198410155841045, 16720998449380848150425324936166240256913805509820058469188719949734553143, 7145617309650842005914703391309576928624278087693185723371364345467778, 157639260692784761681594730199560270734548741053804579865020274, 2202274928441642540077161109623622045532900978898521010, 538799588570563981127024111858913732751, 428137880853210350788575, -1]]
[24, [49, 773942488393224, 332899565197796971624, -146626836535520177399107858276, 195488340779588474151164151261005634, 5329769096045062653316703059226338664853234, 5387587102681763207881059900060695573889494628084, -16510061463182995203662979745434395594380739835919458366, 5168092481131519539073411971756426435408911392060701696858959, 1490329668666500327219062959371162049637704515375394813198831511344, 70957168703375909682354184055609331353295037547634488166459441825777919, -1171416174268555828637919284340143363799161569315960867860113119257812528756, 4164105661526105758763124610336630349138522062674015151042800812485607308569344, 1894344669091196757337562008722632906491919192484809889864876050926547625321183744, 221631210232845965096000809735829504415548830472249676303368562270124934871695884674, -971862020689019847865790519855860825920869429360898162204962986274352150391938939801, 1337916105912198094492893799166168465462703993399972052270797639482684181895642950099, 10554135803751241368713649468058990037910693121226978529816402857130714968432875424, 44246562068139946260455740969952712394475093231613608721597016534273447983070599, 1054400739096283923888328815087945737509114844288940418551646777629280344, 53284369000770778876181686373292710503822136085492383017823882683394, -88313367814420078608872772511917626294947974856181165931, 101948006541519240536592016579351812272561844, -19909113326518817564056, 1]]
[25, [51, 3160265160942525, 2294143089007307344325, -2496073097038403622530432834700, 6140618263216255425706329504422517810, 399893855788791630411501930615028512463812470, 813018048698651762365691424021358496965069520568075, -6118359698602843115419258930973199065310967866955189653525, 4231830753272835813750786615920234309112628924050711968917133150, 3250236751820304390762294688928383339077096201296674306453774598090535, 384185888031444224917049845448297319864652968055361159084362832533507737210, -19384158447553934461833955089809042357629709194032001466314948976771977349049700, 200248252690199991014113965021441914307791509598165944805811725024834995266090910275, 346358576778642561750262029043469463607844349901357593393685354215189503538200550382850, 147290447702653168520537391585259691554250626303739772149060328642585570831539969463582080, -3520517566350636553132154344702505162400827844988986145061326993856416765209712742179428735, 24516904475122681987227218127584998704916814879286753371535700077579333844999749711065618000, 2081057599920877127912408879617949703509753383119176120997847894611203435868249292666425125, 71649742455055163111505339081230175240317441153884242105184127653579971100730620346959125, -1658732822901410766166224038991430694059511392201323708258321051148698069795216304105, 70373535656252333805272440284063417189649457319506574482971920374898672468422555, -60639870890945673920905267654561365900159037873228086150965744132595600, 18320934009643867343986367644974029972505103844818645887125825, 70226891908729804576148514840485841886348925, 190003007093768693711386707, -1]]
[26, [53, 12893881856649326, 15796601004381080116454, -42354589571409437627748852792097, 191695425789572736248086448497644259313, 29675730816235152199119973530089562367377499514, 120447437321372378537580945000261441524328139815675518, -2201226351505324329877258956863496322312285410981412407034702, 3317989101643086937109281651237268921971658763308922316828165690586, 6641466533928020081847148587436322995379380202600946772704564681863563706, 1902739217936104646234474834716787322265399579317134767819780918681987516790666, -282127626289259051276586589016936857780421651612904281306159309146842176696904128359, 8132911737802233112051946643453120332582418174549029115589606812900002650283939255639492, 49838399753321603169431375438922392592822374046440514865873057476299725051675831710901301351, 71945040330620289610205100667732128920231173082924056297337185218495884688230398343539852919393, -8197434704933614643676214084309985335651824822871971232536213449130214014114690199158678144514267, 257249280611993044804098010701705145299147035631567572739521261073303843999483047747633306351591909, 174229395457762409896366834936626378327219981156504853783165215385880430286878508457642743431358151, 41070131310857685349739613090291082783471461983890135142050411685725645226617741730480447688507119, -25554016697583656638203270615792665452895824775019608235479311024261073508674797955929485801334, 11548706380485453970032496018937354756077784378113221442951218702258687009358940449244972615, -263783993016482013694033736965064053491023689549877926134569833079531735550309641026, 26572396246339508455101426287285202768387996015913772006578627249737861057434, 126478768125525998161944656961828075010181487289534878667435082, 10814102781516050720730308012048971569475907677628, -318216630678434010968848, 1]]
[27, [55, 52567364492497539, 108685769302676508926283, -716604286440946606141311095985063, 5951331911176167136128535299290245340049, 2180933036789564299478457925023032660969745019197, 17556119771150508431843534481868036419459758608559352045, -771688439179072547876740950665631774007453407903949120914099426, 2504488928817891861617358491773469475504063769217686151915882928407058, 12824016977134296167104684149538606557455968673570327363649063866957924165778, 8721742817294238638441877018626388080802812284340673353515370770195956318980462106, -3676782691580106836341304389800304288892667153911772133068359148732676751135849944185690, 285694158786283810672556854592064534826653497373152915142300722808911130030755046083655275145, 5853491521035643836096559663761140474282553774165447001470269177712839302760607972654203924576625, 27087439601813787986436013562275292551921301038781672533989219981703945894830520927833640948895869815, -13245890010614349328874424078280538669179040287981546816575705303300965799133540462135515815445739616388, 1703120089154601359767800162624243036733181760566170316519211412482163158237261813370520535514165324918917, 7452619518023863346075294319405262763679747109967067539512510970395388646418571602065072892566158975586843, 10294505810435577631095354540330398988289126777444551094337316185349880802137225531699926342701783052748671, -91363089941652697541869672687902186270887355253118443488010639047081901331387074783941510098738757311763, 396019823748137912742380002953093805762080182917335597856843695797808282756324182230418009243844213996, 307347127033643766693191733149165721226442815082593946427875587097398811000861140028594250029928, 1420629233634177746167126154207350423588790789758030115081486990787852786349054606613029665, 35120688372033493947342424610491353100414811475206836424558515974278844249766944, 228622747894471300890877956645859210982143770639350258808650352500979, -9324190417397050277313796403873310749193145409382, 95072546416901053083094605509, -1]]
[28, [57, 214163336821290724, 747263162551002618658396, -12092371916710866655865676921844322, 183852888667610393635402367448070554514602, 158906670121063128975356159659773587055159258642972, 2522247726727113605983329987026118552109175334385705296484, -264429362390355393679865558102018343404838062099888091016819410043, 1828210857761320601157687462356856680452532366497108310119807198662148750, 23564498356338272772859568742231262072006768168945087810957765682272134864643297, 37361916889082756668433416036225348726147805783688280936391267789217353043840480440478, -43535909872749939435776130853931465507410431684852792727753141518947906525031993433350076534, 8850305734160964438587394886493687980567697917238384268249516667710275089253817601757413565417948, 577679252905311012964121199287051368628605794778028452402690755864079313456126954508646303619421990972, 8163733012733475968702183245471516013859805486870231206997901289755444620382511198988694112484283639675618, -15745963792889968200644602026382947542825407569242440559673261493894233577633527622169665325344317190721334247, 7663897187307726948403846675088302099785565232941860278677981092441761235710901901211368500564359823909857983890, 184960271501253853952332654784468711727634963174975089930971638978976679172587946139364886121507826933269510119244, 1315561265128794118868800087634454606002092518125188295377752074390513186090396245581220009705840883809746515410301, -115761986687887073759260011992218829803282823305794506150658826944426731641919164384427098181698709254157336908164, 4017524791586960904760722980558801791237197340758858287238043599523681697554194039192380600641403194751916030903, 158620382033501967656966205251617819104184279067362834919235529927506661653525951498248047201729452049696220, 7012765296592159365546589923485195487224686192126254796145128800250426171156186115057887102707087417523, 11642117190126362156341637903268188378904524967970045080230583784764340433969241523349499403799, 22709728306408400376409537724770860699822924111140047544094464908327136069823895773287, 4726329333544831359592428196899069137214100005697893850553904418844166, 1468871092819452217498194067419631515497452123787426738, 2329109716004396510104234700, 1]]
[29, [59, 871950728486688449, 5134392361983513083740549, -203562880051482546860512576772908926, 5654528907001940601365372464576742614268586, 11489563507326475608382157261013921881294005446538510, 357726053876155621381030742915140407334755884919638308536210, -88797532117327780975143595451849317777609528506474617332028785434075, 1295551087755276104082578602512152213877678425857810615973172575652370462865, 41450448240371052380583073267890154985860862620819793572750767279734854818621888971, 150792341273942589519521335946024404093141735477002962039257271089234486217730242017194114, -474039194889700905459453462096965090553970617662362984704615856005225996766914487544031024832775, 245671748747617815744443801886519459266195867980970867211796398401780924093486863280739270158494537410, 49043004716223148161337881602975452226149186002537194453179927602360429132571700426590093927817283233605410, 2030516341996371188496363171061309875812233878804454463175565291749723377592060909424741021205362320676575061217, -14413630177559477483712879512035658499791924375932072566284378535598370619006121829900484301343686573622939139483784, 24846979122955965340937407860389422078322330682960328615777909019148269563277658463792716098477937109265637941483979487, 2923290872619675379817782739411862427306028931826977030666844880390387569683405369546412212778142005561361568775685096705, 96163003612630624781323061639810281048457334907989841885119361620713002089061696307024410726084597948413568224673550747790, -65386630028333565958288763708902997430487788098993758445312039820442767375762518040810376199977544814650343494086185827005, 15387740125053279634834594633792784350968561412189724111667663135870221122841886372381140322070022979995430611508350346460, 11924839760825693566642360969857815469463227017732484876946627727707294586434506974085397175966348343080279772559143485, 5735286092313293127613096898863256247247678414219776124902759926787898453213967404018541360138071254506103344539945, -30470094036573011369661737098756509210657127528787718014989868343086259167801667763812085429121259160313300, 55758341003727470199887340433343023765272905164910670428783053625186523077251280278760360221188178996, -30214065100865402771990466653996726139740920132895390334251484467850978954668718787471940, 4155974877471328284774714199356507980459048643201578812823693670987898114720, 537450682705295103249759377686198195017743364251467615, 53195387694665601640167086197355, -1]]
[30, [61, 3547937446945840890, 35256502486447271501663750, -3419239756587830671240803706248732655, 173212362774588903866015287352475937431120267, 825031766988185402644627639263983093185039116021093740, 50152794204826693666876354391690515553748573193815840086282556, -29287275674010289818409999887716161088638179646253879653734630670401429, 894155413307028070284828582772816836504466650108346544403808215088417155212841, 70145490337373511430673394242976656128250242864052477677558463088103191946719246868958, 577327033294576960926209715177951350353332908206845964609709771881958796774286874419151179522, -4794356780457021352818775434203957355936950102612832132506950419529539392148078093206544201620066711, 6192511877384252206774931723208732693775072276976004518958032674574521232120822070580756898780961010178907, 3651293397181377451551010435376879090042867066117050011911069981061391667297760597351067705941486593234307903092, 427316729140641810399139194593885040806497686513105207959792573707513979294992607750577157237290550170062883596923208, -10537123476235162128354850694637316842586393147052982318295360306011555286989134765275947120807409993113659643726165880669, 60799218332642851594951450795369517994703986386685389706861768746632958915530163793135788276773206495056505305578812608068456, 31585509056182757530980677776396015949349820609121725161461545636805278128251554017271347632204529949744046680124560196335515903, 4392663573557873934891345222475474470405730357676076569953356762919658672116270392998486492901336762764223238449864063440050941860, -19190085716259079234230644368450529368382980091138457559153423160100124569554977269303584159909210365874116583194981109724087724189, 26581310322880854860234547352915792342039968815592722677007406074797757154336853336083436432944828579462615251411229057030491058030, 257874711002926200892262018669371264210895335145068842801959368952831830858772854353070977347771986551613206162640482373338190681, 1151526706817257247762044568139601689023180556616531500948884016959427251687350447701563392318209651391741330408639906879633698, -2256299403760998989377254166271644529782249273095872401080444885818476420375064275851626368559935734365513071579509203657, 9326775284867113303276528216577366524583574483060217294785936220619567165891420437837797251164265022442644167879197, -726725413178630425787941715833138301175948750116929434636877647643560340774500669975965368888303311782320, 32024900390444381514071069706701990227058042540490379988142748163922936567185868872207870950570, -148555603838563576604335110675495795547646366084987897383603801502064268857555, 251188571777330027974239263968976270336141258724806082980730, 504339480337015169496219774151, 1]]

160412

Ruby


Zagier's problems(7)

9 以下のm に対し、
U(m, n) = 0 mod ((m + 1)mn + m) となる10^6 以下のn を探してみた。

m = 1 のとき、解なし。
(http://math.stackexchange.com/questions/1736156/are-there-any-number-n-such-that-a-n-0-mod-2n-1-where-a-0-1-a-1)
m = 2 のとき、2755452, 4570452
m = 3 のとき、3006, 401781, 528531
m = 4 のとき、見つからず。
m = 5 のとき、196
m = 6 のとき、見つからず。
m = 7 のとき、26
m = 8 のとき、見つからず。
m = 9 のとき、見つからず。

その際使ったコードは以下のとおりです。
(一部haruya さんのコード(http://d.hatena.ne.jp/haruya12/20160131) を使用しています。)

require 'prime'
require 'matrix'

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

def U(m, n)
  i = m * ((m + 1) * n + 1) * u(m, n)
  j = i.denominator
  return i.to_i if j == 1
  i
end

def berlekamp_massey(s, q)
  b, c = [1], [1] + [0] * (s.size - 1)
  l, m, a = 0, -1, 1
  s.size.times do |n|
    d = (0..l).inject(0) {|sum, i| (sum + c[i] * s[n - i]) % q}
    next if d == 0
    t = c[0..l]
    (0...[s.size - n + m, b.size].min).each do |j|
      c[n - m + j] = (c[n - m + j] - d * a * b[j]) % q
    end
    b, l, m, a = t, n + 1 - l, n, mod_inv(d, q) if 2 * l <= n
  end
  c[0..l]
end

def euclid(a, b)
  return [0, 1] if a == 0
  q, r = b.divmod(a)
  x, y = euclid(r, a)
  [y - q * x, x]
end

# x^(-1) (mod n)
def mod_inv(x, n)
  euclid(x, n)[0]
end

# x % n1 = r1, x % n2 = r2, |x| <= n1 * n2 / 2 となる x
def chinese(n1, r1, n2, r2)
  x = (n1 * (r2 - r1) * mod_inv(n1, n2) + r1) % (n = n1 * n2)
  2 * x > n ? x - n : x
end

# f を多項式として f=0 が数列 s を生成する漸化式の特性方程式となっているか
def test(f, s)
  (0..s.size - f.size).all? do |i|
    f.each_with_index.inject(0) {|sum, (fj, j)|
      sum + fj * s[f.size + i - j - 1]
    } == 0
  end
end

# 数列 s を生成する漸化式の特性方程式を返す
def polynomial(s)
  f, n = [], 1
  Prime.each do |q|
    c = berlekamp_massey(s, q)
    if c.size != f.size then
      f, n = c, q if c.size > f.size
      next
    end
    f = (0...f.size).map {|i| chinese(n, f[i], q, c[i])}
    return f if test(f, s)
    n *= q
  end
end

def power(a, n, mod)
  return Matrix.I(a.row_size) if n == 0
  m = power(a, n >> 1, mod)
  m = (m * m).map{|i| i % mod}
  return m if n & 1 == 0
  (m * a).map{|i| i % mod}
end

(1..9).each{|i|
  a = (0..24).map{|j| U(i, j)}
  ary0 = a[0..i].reverse
  v = Vector.elements(ary0)
  b = polynomial(a)[1..-1].map{|i| -i}
  ary1 = [b]
  (1..i).each{|j|
    c = Array.new(i + 1, 0)
    c[j - 1] = 1
    ary1 << c
  }
  a = Matrix[*ary1]
  p [i, v, a]
  (1..10 ** 6).each{|n|
    mod = (i + 1) * i * n + i
    p n if (power(a, n, mod) * v)[i] % mod == 0
  }
}

出力結果
[1, Vector[4, 1], Matrix[[3, -1], [1, 0]]]
[2, Vector[51, 10, 2], Matrix[[5, 2, 1], [1, 0, 0], [0, 1, 0]]]
[3, Vector[2395, 219, 18, 3], Matrix[[7, 39, 47, -1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]]]
3006
401781
528531
[4, Vector[441221, 19620, 972, 28, 4], Matrix[[9, 244, 974, 44, 1], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]]]
[5, Vector[320160441, 7408255, 154000, 4360, 40, 5], Matrix[[11, 1205, 12240, -6915, 1862, -1], [1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0]]]
196
[6, Vector[947687003440, 10353349563, 124825895, 1172628, 19401, 54, 6], Matrix[[13, 5466, 120994, -573455, 736546, -1401, 1], [1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0]]]
[7, Vector[10849848134049807, 62681716148597, 329478589895, 2110500091, 8741607, 85211, 70, 7], Matrix[[15, 23919, 1050959, -22723953, 110533535, 1824095, 118911, -1], [1, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0]]]
26
[8, Vector[515038338884349001737, 1398347293343723656, 4149291508997544, 10350461259304, 35725792824, 64181272, 369672, 88, 8], Matrix[[17, 102824, 8460428, -660176392, 9869354006, 6085682408, 1508966588, -39688, 1], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0]]]
[9, Vector[93786705206867081003177917, 135131992303972351151403, 178716120071486628960, 275056422056846730, 321805755708813, 604220806080, 465906573, 1587420, 108, 9], Matrix[[19, 437409, 64949424, -16192124931, 648337672368, 2952342946923, 3894121358913, 4763358099, 11078999, -1], [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]]

2016年4月10日日曜日

160410(3)

Ruby


Zagier's problems(6)

haruya さんのコード(http://d.hatena.ne.jp/haruya12/20160131)
を使って、数列U の特性方程式を求めると次のようになった。
(ただし、多項式は係数を並べた配列で表現している。)

[1, -3, 1]
[1, -5, -2, -1]
[1, -7, -39, -47, 1]
[1, -9, -244, -974, -44, -1]
[1, -11, -1205, -12240, 6915, -1862, 1]
[1, -13, -5466, -120994, 573455, -736546, 1401, -1]
[1, -15, -23919, -1050959, 22723953, -110533535, -1824095, -118911, 1]
[1, -17, -102824, -8460428, 660176392, -9869354006, -6085682408, -1508966588, 39688, -1]
[1, -19, -437409, -64949424, 16192124931, -648337672368, -2952342946923, -3894121358913, -4763358099, -11078999, 1]
[1, -21, -1847350, -483413545, 358291324370, -35009923530009, -762890018040083, -4188043855001225, 182235342002781, -6583812979820, -4453415, -1]

160410(2)

Ruby


Zagier's problems(5)

U にあたるものを実験しながら作ってみた。

def f(n)
  return 1 if n <= 1
  (1..n).inject(:*)
end

def u(m, n)
  i = (0..n).inject(0){|s, k| s + f(m * n + k).to_r / (f(m * n - m * k) * f((m + 1) * k + 1))}
  j = i.denominator
  return i.to_i if j == 1
  i
end

def U(m, n)
  i = m * ((m + 1) * n + 1) * u(m, n)
  j = i.denominator
  return i.to_i if j == 1
  i
end

(1..10).each{|i| p (0..24).map{|j| u(i, j)}}
(1..10).each{|i| p (0..24).map{|j| U(i, j)}}

出力結果
[1, (4/3), (11/5), (29/7), (76/9), (199/11), (521/13), (1364/15), (3571/17), (9349/19), (24476/21), (64079/23), (167761/25), (439204/27), (1149851/29), (3010349/31), (7881196/33), (20633239/35), (54018521/37), (141422324/39), (370248451/41), (969323029/43), (2537720636/45), (6643838879/47), (17393796001/49)]
[1, (5/4), (51/14), (277/20), (1497/26), (4045/16), (43721/38), (118141/22), (638471/25), (6900995/56), (37295141/62), (201554637/68), (544632231/37), (1177345345/16), (15906858593/43), (85965651921/46), (929170680307/98), (5021529726405/104), (27137921296481/110), (73330918307761/58), (792606555396977/122), (2141747185756205/64), (11574673402485763/67), (125106329323279427/140), (676113834597852597/146)]
[1, (6/5), (73/9), (2395/39), (26149/51), (286723/63), (1046406/25), (34383331/87), (376562651/99), (4124144989/111), (15055945217/41), (18321502422/5), (1805922599993/49), (59335680780827/159), (649847528402837/171), (7117164655305731/183), (5196504361583310/13), (853685877677323571/207), (9349613086538467867/219), (14628208463635117451/33), (373820804592843820033/81), (4094105312070579316998/85), (44838858887431435924777/89), (1473232694136663467311579/279), (16134922735374295426616581/291)]
[1, (7/6), (243/11), (4905/16), (441221/84), (9706233/104), (214166697/124), (4726434631/144), (104267890033/164), (575171734653/46), (16920175995685/68), (559988733543713/112), (24710827624432425/244), (136303509835451075/66), (3007365527824818089/71), (265415060476370716153/304), (5856051170156218402567/324), (32301611378151143865201/86), (1425389302791240028347285/182), (5241572023931088771464221/32), (1387784767942506927630863145/404), (7654933774760962651071049129/106), (56298846379180337755702684413/37), (3726490884475354742481271093249/116), (82220360363618816911119260568461/121)]
[1, (8/7), (872/13), (30800/19), (1481651/25), (320160441/155), (14303597201/185), (632753150096/215), (28063941736416/245), (1244046819273791/275), (55148150118255993/305), (2444859860324379899/335), (21676245687786483441/73), (4804712672638069513601/395), (212997271287348543216227/425), (9442431469459570812240492/455), (418593237257656800568818557/485), (18556719346361354985123320363/515), (164528039005459940946753641082/109), (36468572364202560186290146533498/575), (323338597034469891385772441777774/121), (71669828219779330954419394272463557/635), (453886354076044140415025026313070028/95), (140849065966787010746842233489220761528/695), (6243998291342823607143198136571738632484/725)]
[1, (9/8), (6467/30), (97719/11), (124825895/174), (3451116521/72), (473843501720/129), (13892727393211/50), (3722832354082018/171), (330619364192637931/192), (19614632135295958439/142), (5233079174973134534939/468), (77578054424217659547456/85), (10350287680004192659267865/138), (1227459569883088583600797523/198), (81882723163731202870397380888/159), (29132003643569951998302290674129/678), (863715590276647665754619878161943/240), (230468527479333002597974532269296647/762), (20498984710697000958807078261654745741/804), (1823276328091360164035074022035632129149/846), (162170902238114180371163365934396012251817/888), (4808083141026376388630645128443464176386227/310), (106913449328270614245368842491626794433919374/81), (114112682782742401221498163990969826086554412961/1014)]
[1, (10/9), (12173/17), (1248801/25), (301500013/33), (47068369985/41), (8954530878371/49), (3616616044683269/133), (1961307671216691883/455), (347559287308451008967/511), (62140698954891656421190/567), (11067012620150133414337963/623), (1974249851740493659523015623/679), (351951838629631165144467430043/735), (62758674512597558743883263610439/791), (11189954786512984420393651687875941/847), (1995221638416328054526045855047718383/903), (355758150892408390230576747504182000459/959), (9061863319798195260695461954546882409601/145), (11310428571396007320666762754450306819217990/1071), (2016696277341169111795798300521062697437592955/1127), (51369491523983014450494440607772389176868751201/169), (64115828922334414331872309869748783481829146350651/1239), (2286429018304177791698795890230227079657492052657499/259), (2038402280444992115457711912936851219673442797789253973/1351)]
[1, (11/10), (46209/19), (8022659/28), (4465724103/37), (1293807657413/46), (518661438624693/55), (174793411667965457/64), (515038338884349001737/584), (181163947386176653214257/656), (9318830205506037846622983/104), (23212245303284868932655427373/800), (8308538381612887460327404311377/872), (2965401558243638825595575915138699/944), (1059841112828460144356737772557905821/1016), (378546262274221323803046299807145727787/1088), (135245341646806611776768752141187647720673/1160), (6039246784049866362336004131840524645509213/154), (17260103082702448587399430715897692567830284987/1304), (3083031009429017764677322806099449025463759518733/688), (2202789474139810162249748866502901072982904998321405/1448), (196733946434713193587628380799376721768378411991659421/380), (281127995768849933952434422866250185772438121212994731307/1592), (50215777312314628834696305254457702238981370606946330243373/832), (5125512225049376532128690593738813756858658012015112550734407/248)]
[1, (12/11), (176380/21), (51767397/31), (67135645120/41), (11918731692919/17), (30561824672982970/61), (19857346674609625440/71), (15014665811552483461267/81), (93786705206867081003177917/819), (68254082605708675916908061296/909), (48382209702384034966235090259067/999), (34794212090651687712978763123190218/1089), (24826501160479241396695493078891857030/1179), (17789428163904432084351323109865284484846/1269), (12718316540886128783733071854567602844617154/1359), (9103548603182325055758247469335316966493759994/1449), (6512194352582229649951655678555440574784042852379/1539), (1553301114265427814172941683861566408905467435314942/543), (3333971239159690878362227054802423742149983172341920259/1719), (2385484971604224864516234862714188805787273553827637636176/1809), (568928268435511124410652013385573854626812480971550780809889/633), (1221196309021127356558929592785195303364375549163225429501141509/1989), (873758013389420925175253137897920305751311885957706240700566283646/2079), (208389200015806255519448229650676439085027964865470716797780641996850/723)]
[1, (13/12), (676063/23), (670541695/68), (2039260161407/90), (992233919906433/56), (1825414401676678659/67), (11338991545128842076851/390), (3546391386864465585047379/89), (4826768444379726302646441741/100), (11884266409237776928712446583571/185), (25082456173446867997531106031789854/305), (145268085315175686173723817369275021269/1330), (20683009715062239295106529519220570898657/144), (29737404634631517999428117136643599042420624/155), (212571532141417706479502950979348764619819117181/830), (304892632314065272058289481527025222428461239401952/885), (873005406669864319827933219287817237076045224891891893/1880), (625572823359585750188563058595614431711167452739370292373/995), (51201240603327890861210134539287060162998608401782506525809/60), (2567590646756112061879370386802811251864850983639156389918101579/2210), (3678155424897510961866819717255539980992433254589714722237697729227/2320), (2634767054772379555236636827236085122327873600670627536268141229361301/1215), (7549106200718645399348303323571499862700443001140193578587045676822020227/2540), (5407513606480782081476231360615523908328248286891919710376857493360509982808/1325)]
[1, 4, 11, 29, 76, 199, 521, 1364, 3571, 9349, 24476, 64079, 167761, 439204, 1149851, 3010349, 7881196, 20633239, 54018521, 141422324, 370248451, 969323029, 2537720636, 6643838879, 17393796001]
[2, 10, 51, 277, 1497, 8090, 43721, 236282, 1276942, 6900995, 37295141, 201554637, 1089264462, 5886726725, 31813717186, 171931303842, 929170680307, 5021529726405, 27137921296481, 146661836615522, 792606555396977, 4283494371512410, 23149346804971526, 125106329323279427, 676113834597852597]
[3, 18, 219, 2395, 26149, 286723, 3139218, 34383331, 376562651, 4124144989, 45167835651, 494680565394, 5417767799979, 59335680780827, 649847528402837, 7117164655305731, 77947565423749650, 853685877677323571, 9349613086538467867, 102397459245445822157, 1121462413778531460099, 12282315936211737950994, 134516576662294307774331, 1473232694136663467311579, 16134922735374295426616581]
[4, 28, 972, 19620, 441221, 9706233, 214166697, 4726434631, 104267890033, 2300686938612, 50760527987055, 1119977467087426, 24710827624432425, 545214039341804300, 12029462111299272356, 265415060476370716153, 5856051170156218402567, 129206445512604575460804, 2850778605582480056694570, 62898864287173065257570652, 1387784767942506927630863145, 30619735099043850604284196516, 675586156550164053068432212956, 14905963537901418969925084372996, 328881441454475267644477042273844]
[5, 40, 4360, 154000, 7408255, 320160441, 14303597201, 632753150096, 28063941736416, 1244046819273791, 55148150118255993, 2444859860324379899, 108381228438932417205, 4804712672638069513601, 212997271287348543216227, 9442431469459570812240492, 418593237257656800568818557, 18556719346361354985123320363, 822640195027299704733768205410, 36468572364202560186290146533498, 1616692985172349456928862208888870, 71669828219779330954419394272463557, 3177204478532308982905175184191490196, 140849065966787010746842233489220761528, 6243998291342823607143198136571738632484]
[6, 54, 19401, 1172628, 124825895, 10353349563, 947687003440, 83356364359266, 7445664708164036, 661238728385275862, 58843896405887875317, 5233079174973134534939, 465468326545305957284736, 41401150720016770637071460, 3682378709649265750802392569, 327530892654924811481589523552, 29132003643569951998302290674129, 2591146770829942997263859634485829, 230468527479333002597974532269296647, 20498984710697000958807078261654745741, 1823276328091360164035074022035632129149, 162170902238114180371163365934396012251817, 14424249423079129165891935385330392529158681, 1282961391939247370944426109899521533207032488, 114112682782742401221498163990969826086554412961]
[7, 70, 85211, 8741607, 2110500091, 329478589895, 62681716148597, 10849848134049807, 1961307671216691883, 347559287308451008967, 62140698954891656421190, 11067012620150133414337963, 1974249851740493659523015623, 351951838629631165144467430043, 62758674512597558743883263610439, 11189954786512984420393651687875941, 1995221638416328054526045855047718383, 355758150892408390230576747504182000459, 63433043238587366824868233681828176867207, 11310428571396007320666762754450306819217990, 2016696277341169111795798300521062697437592955, 359586440667881101153461084254406724238081258407, 64115828922334414331872309869748783481829146350651, 11432145091520888958493979451151135398287460263287495, 2038402280444992115457711912936851219673442797789253973]
[8, 88, 369672, 64181272, 35725792824, 10350461259304, 4149291508997544, 1398347293343723656, 515038338884349001737, 181163947386176653214257, 65231811438542264926360881, 23212245303284868932655427373, 8308538381612887460327404311377, 2965401558243638825595575915138699, 1059841112828460144356737772557905821, 378546262274221323803046299807145727787, 135245341646806611776768752141187647720673, 48313974272398930898688033054724197164073704, 17260103082702448587399430715897692567830284987, 6166062018858035529354645612198898050927519037466, 2202789474139810162249748866502901072982904998321405, 786935785738852774350513523197506887073513647966637684, 281127995768849933952434422866250185772438121212994731307, 100431554624629257669392610508915404477962741213892660486746, 35878585575345635724900834156171696298010606084105787855140849]
[9, 108, 1587420, 465906573, 604220806080, 321805755708813, 275056422056846730, 178716120071486628960, 135131992303972351151403, 93786705206867081003177917, 68254082605708675916908061296, 48382209702384034966235090259067, 34794212090651687712978763123190218, 24826501160479241396695493078891857030, 17789428163904432084351323109865284484846, 12718316540886128783733071854567602844617154, 9103548603182325055758247469335316966493759994, 6512194352582229649951655678555440574784042852379, 4659903342796283442518825051584699226716402305944826, 3333971239159690878362227054802423742149983172341920259, 2385484971604224864516234862714188805787273553827637636176, 1706784805306533373231956040156721563880437442914652342429667, 1221196309021127356558929592785195303364375549163225429501141509, 873758013389420925175253137897920305751311885957706240700566283646, 625167600047418766558344688952029317255083894596412150393341925990550]
[10, 130, 6760630, 3352708475, 10196300807035, 9922339199064330, 18254144016766786590, 22677983090257684153702, 35463913868644655850473790, 48267684443797263026464417410, 71305598455426661572274679501426, 100329824693787471990124424127159416, 145268085315175686173723817369275021269, 206830097150622392951065295192205708986570, 297374046346315179994281171366435990424206240, 425143064282835412959005901958697529239638234362, 609785264628130544116578963054050444856922478803904, 873005406669864319827933219287817237076045224891891893, 1251145646719171500377126117191228863422334905478740584746, 1792043421116476180142354708875047105704951294062387728403315, 2567590646756112061879370386802811251864850983639156389918101579, 3678155424897510961866819717255539980992433254589714722237697729227, 5269534109544759110473273654472170244655747201341255072536282458722602, 7549106200718645399348303323571499862700443001140193578587045676822020227, 10815027212961564162952462721231047816656496573783839420753714986721019965616]