151217

Ruby


周期性をもつ差分方程式

Lyness の周期5の漸化式
Xn = (1 + Xn-1) / Xn-2
や
Todd の周期8の漸化式
Xn = (1 + Xn-1 + Xn-2) / Xn-3
が知られているが、
Xn = (1 + Xn-1 + … + Xn-k-1) / Xn-k
とするとどうなるか調べてみた。

def f(m, k)
  i = 0
  ary = []
  a = (1..k).map{|i| i.to_r}
  while i < m
    j = a.shift
    a << (a.inject(:+) + 1r) / j
    ary << a[0]
    i += 1
  end
  ary
end

(2..20).each{|k| p f(50, k)}

出力結果
[(2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1), (2/1), (3/1), (2/1), (1/1), (1/1)]
[(2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1), (6/1), (5/1), (4/1), (5/3), (4/3), (1/1), (2/1), (3/1)]
[(2/1), (3/1), (4/1), (10/1), (9/1), (8/1), (7/1), (5/2), (37/18), (113/72), (57/56), (79/35), (526/185), (18963/4181), (67304/6441), (37562/4503), (177765/20777), (494764/79163), (5851931/2532313), (98046897/45144158), (261614425/190777398), (74481337/67916388), (1690057423/692495764), (1696378550597/623559343589), (6029565661142/1139261940115), (13712628104169/1312968619795), (621174943307012/77915302440773), (71980376442658082/7925102517572309), (1220041251046289217/226572524776683353), (6808715737286399320/3033736421891847407), (278630559500696573527/125418050577090731281), (11019507432146370995407/9223863798245458847158), (174204079984755385555873/140835077573252800580346), (18366442192414548442209701/7291487386385377749456456), (552874077649080643363207827/206415147079612715612646856), (35031590414511209797116628687/5629503952292954716675146899), (2432185804023615805583578312666/242223132110381300183165448179), (111800777414205821245942921389435/14121346654349647407737981310541), (31467586462712162138370474484598024/3347136459697471197497855062579761), (703778898330217990181025180098953342/154427996208554466480441541821046029), (21044531098292478509443342252430712933/9237271794359226423000234872368818649), (840719233011935293567051450687190733580/386154171803116477271422619215887566927), (102774074027276961211036742400189999374357/96498847037682201795763591985878555422823), (153505051230391161880444022117277167545766697/107289719999554203025706844826175619523766318), (6551158666190530259293789258635118527240565843/2630906210874893189352752426289855056847134514), (4670274020677296004976968730204360232289761203/1698658846312210834513988490328246524328954620), (1024793296700404240309241466269964459609807605927/142295113198168366911437876741346856134778695620), (44280370177323083058111703560019096793231770612066637/4713384019048658109138418101328393700395574116574189), (53208185402841696667952365361990974226230438558034239406/6512005409394100834299349070617100585185219669235785399), (31041951558547504289487999239332201730951839756840461459/3312201568295082377106282008491510404674854370037177521)]
[(2/1), (3/1), (4/1), (5/1), (15/1), (14/1), (13/1), (12/1), (11/1), (17/5), (101/35), (212/91), (67/39), (34/33), (29/11), (305/101), (21609/5353), (24232/3551), (19365/1139), (5962/493), (407863/30073), (40032259/3201219), (23678969/2877084), (16769363/6016060), (5509076/1749305), (225522763/110530873), (222443977807/161660170817), (222758941797/177082499507), (353972569208/111822367397), (1935169695505/689430561482), (100853774248107/21421069674086), (15685576217810201/1668146858901517), (259432691560573495/15478911347646841), (150120874090465188/13703206952236957), (868625797836432311/56930697912867217), (24801147593323800016/2187638189780123137), (1650734362004120825743/280633075963062985609), (66731777348512460990099/25172256322007377816735), (181322640015427341663047/54983217614871951438645), (461783233266974395426496/291531263074097863423011), (4966393354804454269651457/3905925741310579428754271), (398194484238274426532709448/238900923088369554285038401), (219703123115287524035768176239/66035215855836770262830455121), (2097649253016897543774282086705/781707561339154230112761109933), (9594532980452702089000597314615/1527594147535644205881615871504), (118476215614325953767110974358611/10071004155645849088014615561904), (6794453192625747551379716903409577/451992118641775570678966797603364), (1722202174404452221138729428624127613/155870029742938731278207837535913404), (307883385315341368517088370641861585967/18308255175573818625070518968581598817), (3243911589633974059182254961707061360341/366038326102779659249537873064130965835)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (21/1), (20/1), (19/1), (18/1), (17/1), (16/1), (13/3), (113/30), (601/190), (430/171), (277/153), (141/136), (319/104), (4911/1469), (274220/67913), (734578/129215), (597699/59555), (7259/277), (5232/319), (9897979/522203), (435146276/22444907), (4288585149/265047341), (1394714030/142643449), (9823251/3150833), (9125176/2187521), (11037348003/3900565109), (2803598661805/1465986624158), (19367769632641/13739356654074), (68367123252181/46289903464458), (8500619088125/2070449734014), (4445476173929/1456227524196), (6505938068183537/1420783209883404), (4357062722866631743/533314911671863245), (38415545546363972614/2419232702733846215), (124431813615337562157/4995781842590209481), (2685911975576458516652/191489025388969414375), (12660050488810499073021/563691278508118406875), (249585179705928846763144/13221355438950108177113), (86418649445756523242652171/7267352150783297119598899), (669852722023857534790602575/114174944518871734044858419), (9318151120963631762902679902/3131226964506626785007329643), (146093045818621497020706561414/32489980102234546359332109211), (3158186133577781329643002601875/1572451205690144722947699736583), (44396647043841361969600140719532/29678477064707427742033124594837), (1627136922041558026704248019140725/1084352328742923529767976010636879)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (28/1), (27/1), (26/1), (25/1), (24/1), (23/1), (22/1), (37/7), (884/189), (109/27), (84/25), (66/25), (43/23), (263/253), (1434/407), (30541/8177), (102438/24089), (22849/4251), (20275/2574), (122057/8514), (1308700/33927), (4022029/188571), (77677948/3128271), (220558425/8276611), (1085395622/43344553), (2499134339/129713773), (7573449840/692917589), (1161700341/347252165), (5416649638/1040242955), (706681167591/191905994789), (17496656858228/6809429995275), (118663634680513/64596100617975), (1419394710600430/957145190663537), (964964001057105/551488011650293), (135361465413876/25834153340599), (312758183314675/92736223826777), (6792659013187538/1449944314499657), (1063963357669548179/141161476573659571), (460790468957642689650/33768741361571174909), (26264645198452128448827/1046191031416240369085), (60934689161564109314716/1759855266127988043425), (1348681984100949428219/78544057359952706175), (4688936173881504297262/152394319894506884775), (141518713259124534328759/5105681520430454148325)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (36/1), (35/1), (34/1), (33/1), (32/1), (31/1), (30/1), (29/1), (25/4), (157/28), (1175/238), (4753/1122), (3697/1056), (2705/992), (355/186), (181/174), (579/145), (3268/785), (843311/184475), (30195706/5584775), (124525599/17571841), (106978208/10000385), (19098139/960275), (17544726/321275), (939774/34933), (4930061/157681), (3377266564/98426441), (3675997132415/106993155557), (503717856447862/16756409879135), (274057925977363/12615080900707), (24256523141784/2059561175761), (2104646128265/600486766783), (986284288889/157931775210), (3653084227343/798817783830), (1750041678929763/530258922731860), (4024625492365502513/1682453205673541140), (3006474016625505038885/1657779763597075379006), (12514645783961352095447/7856198506227328470466), (6892101526051222757209/3323718248677041966696), (1743648286669829289295/265816550027471657832), (120558131450428231983/32305336704985333567), (506642449752424694390/103139712575977235419), (887302178890067432377573/121632593422628847204567)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (45/1), (44/1), (43/1), (42/1), (41/1), (40/1), (39/1), (38/1), (37/1), (65/9), (1297/198), (5539/946), (4636/903), (3775/861), (591/164), (145/52), (478/247), (731/703), (10753/2405), (388827/84305), (35543684/7184083), (71980753/12839402), (59882361/8750450), (20581303/2231025), (6097304/428475), (13961272/519825), (39211801/524127), (260430827/7860443), (17793750715/464561859), (1481401452296/34899858633), (59541685382071/1352252187481), (198124113728064/4773396939311), (49082531414165/1431425105803), (9043853561306/382592869229), (5076732198275/409260190436), (4010554996521/1108191537188), (105768014411469/14526261397709), (10575203480835413/1926836263675381), (638118911064394707/156335259776964524), (18586034242483801423/6138928183120343476), (1049591022426036275263/459392253868133445936), (299435351427685633699/163427444503884344976)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (55/1), (54/1), (53/1), (52/1), (51/1), (50/1), (49/1), (48/1), (47/1), (46/1), (41/5), (1013/135), (9712/1431), (4167/689), (1168/221), (1911/425), (92/25), (17/6), (551/282), (1123/1081), (4672/943), (210755/41533), (13178457/2459564), (19893179/3372492), (5569655/811176), (1370693/159432), (74350/6279), (50795/2737), (2321796/65569), (61682753/618773), (52496695/1311664), (2262904677/49232368), (350497121729/6857841247), (3303082390088/61067180071), (8578482044499/160810078205), (235929608704/4934897945), (4525978821/119895323), (1897330398/75532165), (126532341793/9827968985), (598280851568/161589842729), (2264131599763/272318616685)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (66/1), (65/1), (64/1), (63/1), (62/1), (61/1), (60/1), (59/1), (58/1), (57/1), (56/1), (101/11), (6052/715), (4019/520), (3515/504), (12107/1953), (10216/1891), (4193/915), (3308/885), (4905/1711), (1084/551), (138/133), (3847/707), (847407/152813), (35211085/6080747), (4645064/743515), (15759828/2239795), (129504763/15460639), (57309134/5354461), (51962535/3467611), (32134822/1352145), (20253919/443085), (4851479/37398), (25258555/530886), (5360669132/98787113), (119905448203/1987220773), (2901982675264/44933445971), (45205837486055/689931936553), (307078493073838/4963963519093), (104387653076331/1962402384031)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (78/1), (77/1), (76/1), (75/1), (74/1), (73/1), (72/1), (71/1), (70/1), (69/1), (68/1), (67/1), (61/6), (4357/462), (50789/5852), (45089/5700), (39539/5550), (34137/5402), (3209/584), (2641/568), (18799/4970), (13969/4830), (9277/4692), (4721/4556), (24239/4087), (1600626/265777), (1380405411/221287673), (15189134204/2290025221), (684560325/93830209), (595266286/71039097), (1113163495/109545633), (1006391144/76274721), (759917189/40621221), (714638050/23873021), (7506827607/129590413), (7245441684/43796717), (6385155074/114432319), (408759419185/6466262269), (335553277583612/4782495219453)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (91/1), (90/1), (89/1), (88/1), (87/1), (86/1), (85/1), (84/1), (83/1), (82/1), (81/1), (80/1), (79/1), (145/13), (1217/117), (7718/801), (17337/1958), (5141/638), (9035/1247), (4690/731), (284/51), (1171/249), (12991/3403), (9670/3321), (643/324), (327/316), (14713/2291), (229541/35293), (31447476/4696403), (471197773/66903483), (6995384/918861), (12236231/1436565), (90316598/9080175), (2912729/237850), (13389561/831410), (350768873/15212461), (2333404792/62811485), (224540343/3108905)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (105/1), (104/1), (103/1), (102/1), (101/1), (100/1), (99/1), (98/1), (97/1), (96/1), (95/1), (94/1), (93/1), (92/1), (85/7), (4141/364), (56759/5356), (51506/5253), (46355/5151), (8261/1010), (661/90), (2864/441), (26751/4753), (7365/1552), (1169/304), (2614/893), (8699/4371), (4421/4278), (27037/3910), (2459863/351985), (1683302712/235039019), (1560038824/208816361), (1359206763/170540045), (669643433/76587731), (54210676/5460521), (612020421/52060360), (2058279447/140460584)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (120/1), (119/1), (118/1), (117/1), (116/1), (115/1), (114/1), (113/1), (112/1), (111/1), (110/1), (109/1), (108/1), (107/1), (106/1), (197/15), (22052/1785), (81187/7021), (74284/6903), (33749/3393), (30414/3335), (18091/2185), (15944/2147), (5188/791), (4411/777), (2653/555), (2108/545), (8651/2943), (5762/2889), (5853/5671), (77354/10441), (8119065/1086061), (3416549738/447583931), (11928791159/1507723777), (5236551450/626752679), (1544605569/171073681)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (16/1), (136/1), (135/1), (134/1), (133/1), (132/1), (131/1), (130/1), (129/1), (128/1), (127/1), (126/1), (125/1), (124/1), (123/1), (122/1), (121/1), (113/8), (14401/1080), (226727/18090), (10995/938), (3357/308), (58019/5764), (12079/1310), (10789/1290), (123745/16512), (107489/16256), (91487/16002), (75737/15750), (60237/15500), (14995/5084), (9993/5002), (15217/14762), (108063/13673), (12961192/1627313), (1393557885/171847133)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (16/1), (17/1), (153/1), (152/1), (151/1), (150/1), (149/1), (148/1), (147/1), (146/1), (145/1), (144/1), (143/1), (142/1), (141/1), (140/1), (139/1), (138/1), (137/1), (257/17), (18497/1292), (154997/11476), (143672/11325), (132497/11175), (3283/298), (61/6), (2038/219), (89277/10585), (26279/3480), (2077/312), (5308/923), (48377/10011), (5501/1410), (4111/1390), (19186/9591), (9733/9453)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (16/1), (17/1), (18/1), (171/1), (170/1), (169/1), (168/1), (167/1), (166/1), (165/1), (164/1), (163/1), (162/1), (161/1), (160/1), (159/1), (158/1), (157/1), (156/1), (155/1), (154/1), (145/9), (2341/153), (41606/2873), (96917/7098), (89903/7014), (165945/13861), (10150/913), (4624/451), (62677/6683), (112151/13203), (99110/13041), (8623/1288), (7351/1272), (60949/12561), (48546/12403)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (16/1), (17/1), (18/1), (19/1), (190/1), (189/1), (188/1), (187/1), (186/1), (185/1), (184/1), (183/1), (182/1), (181/1), (180/1), (179/1), (178/1), (177/1), (176/1), (175/1), (174/1), (173/1), (172/1), (325/19), (58484/3591), (137327/8883), (128538/8789), (79895/5797), (14832/1147), (10273/851), (47156/4209), (171971/16653), (155500/16471), (13921/1629), (12310/1611), (107169/15931)]
[(2/1), (3/1), (4/1), (5/1), (6/1), (7/1), (8/1), (9/1), (10/1), (11/1), (12/1), (13/1), (14/1), (15/1), (16/1), (17/1), (18/1), (19/1), (20/1), (210/1), (209/1), (208/1), (207/1), (206/1), (205/1), (204/1), (203/1), (202/1), (201/1), (200/1), (199/1), (198/1), (197/1), (196/1), (195/1), (194/1), (193/1), (192/1), (191/1), (181/10), (36101/2090), (54973/3344), (51661/3312), (628951/42642), (586721/42230), (32053/2460), (4231/348), (66069/5858), (140627/13534), (127227/13400)]