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]]