use malachite_base::num::arithmetic::traits::{
DivRound, DoubleFactorial, Factorial, Multifactorial, Parity, Subfactorial,
};
use malachite_base::num::basic::traits::One;
use malachite_base::num::conversion::traits::ExactFrom;
use malachite_base::rounding_modes::RoundingMode;
use malachite_base::test_util::generators::common::GenConfig;
use malachite_base::test_util::generators::{
unsigned_gen_var_23, unsigned_gen_var_24, unsigned_gen_var_25, unsigned_gen_var_5,
unsigned_pair_gen_var_18, unsigned_pair_gen_var_43,
};
use malachite_nz::natural::arithmetic::factorial::{limbs_odd_factorial, subfactorial_naive};
use malachite_nz::natural::Natural;
use malachite_nz::platform::Limb;
use malachite_nz::test_util::generators::unsigned_bool_pair_gen_var_1;
use malachite_nz::test_util::natural::arithmetic::factorial::{
double_factorial_naive, factorial_naive, multifactorial_naive,
};
use rug::Complete;
#[cfg(not(feature = "32_bit_limbs"))]
#[test]
fn test_limbs_odd_factorial() {
fn test(n: usize, double: bool, out: &[Limb]) {
assert_eq!(limbs_odd_factorial(n, double), out);
let x = Natural::from_limbs_asc(out);
let n = u64::exact_from(n);
let f = if double {
double_factorial_naive(if n.odd() { n } else { n - 1 })
} else {
factorial_naive(n)
};
let zeros = f.trailing_zeros().unwrap_or(0);
assert_eq!(x, f >> zeros);
}
test(0, false, &[1]);
test(1, false, &[1]);
test(2, false, &[1]);
test(3, false, &[3]);
test(4, false, &[3]);
test(5, false, &[15]);
test(
236,
false,
&[
10618490636539735421,
4729263067195600518,
12186030463696251555,
7142237826843540900,
16119581746492108114,
5482041831095653408,
12729359642514511788,
3861260445332999633,
17654643046781915017,
2948639619901500831,
4828424310736619826,
1606991017570978140,
14449535564474352339,
9583999911344645019,
8526753984697305947,
1483125246843554788,
1239190358257616768,
14274595842916600689,
8578099838285951726,
17196912285743182036,
17502,
],
);
test(
253,
false,
&[
13440159167366384907,
17464845158472189078,
2826161362940216017,
8037578185636069543,
13742255038126785696,
4563220256937210164,
972898594381496298,
12935003271289472483,
92134269506540108,
1576249685989390350,
9293957639462726276,
13219082968020015738,
14036467266653166020,
5999133297790892927,
7879089681869446232,
2166730567576588847,
17427398953314831214,
15373827890147248358,
3930181242506798982,
16625114769217038348,
16998219128482634557,
10891990883556867133,
64,
],
);
test(
2225,
false,
&[
1017787374069377867,
12845616420474236155,
14793541814949268171,
10336267089029193949,
17681045444610962234,
12241025939672520011,
1647783948166186005,
17853335081138702500,
5765698469319069076,
5704200848184839352,
16256105179485582433,
17734124028926156842,
492655904033205979,
11085849896016490658,
3067192438194807154,
11837646166112740505,
10992580052412267512,
1773657253076351848,
17041387235381257635,
15421578608188334756,
4615954739499965896,
13499729159452430001,
414946168188809488,
5319757607719939053,
14636961330979174035,
11228840029340991417,
2679650868790992799,
6523494380304249905,
15240167682641278207,
16817584289869342383,
1314876650236886671,
17986738819629100058,
633572152189350719,
1068154426686527634,
14065257391447683248,
14043628340189386248,
2520373228683116453,
8613302832793040941,
5920151864571800853,
6631973414231062372,
2805822256823597153,
8266805345818108603,
14961584013940036942,
3521359229908934002,
12440093989655599608,
13132030287112341405,
1135400476705565545,
13470237633228184820,
11041193975860352280,
13077192932837691259,
17293836581638404804,
2171592479756569901,
8391859231746033908,
13233250271168303683,
2885150469181476635,
12827004644907825951,
4414861260039887031,
2934847053891069518,
17933902203427299124,
13612729539900541744,
9092564372087223834,
16826850061886832697,
4235092271172303688,
15237133411303617967,
2524372566060934554,
10438528715364626770,
3931468119754873441,
8873546397604882128,
3022623706864869622,
7597020790388111878,
10943741155846665560,
14197476647010604491,
9989007778547549825,
8026201480421198518,
13607446335263109565,
16903088772085727428,
15808374554425019668,
6105563595459012989,
4013715839388158058,
15900509513105858779,
3930550334470266139,
3012225684372399152,
3555814020193574494,
16008860678570397127,
15641857373385284341,
15630999159384499531,
14194771320251995975,
420469150284887121,
13013286608344133197,
8528545810586239597,
5970238577029242260,
2388798772187671996,
7239099684932389496,
15198440189583552216,
11371225490310014286,
15452238839118434215,
5822580676472517141,
13899215192394129457,
17158467603319793152,
10977162731484357791,
6619469008814683154,
11754410156367698938,
2978824074240909961,
273537313978929004,
7247845064959191752,
14411883344186220714,
784118077426499313,
12871601200579333074,
8028216077204519736,
11850247931840500366,
3779495200526023485,
5929422344052886193,
2800123978803955913,
15699871195759344930,
3086311510046848853,
7356496574230285725,
6320159507583018055,
18115938954181399640,
6284941634674233267,
9549047133838384915,
9377608933266367603,
5075665075684086144,
690014617562733994,
4759772792411992244,
6111964336140423243,
16256222171952118355,
6259909518175821262,
3521565945796344197,
17834735129730212580,
9239590528624641975,
2672544178748226145,
12588486577096010536,
1899856248989413045,
12414729356008040141,
673936303178532624,
12049353462684429624,
18170970390317199364,
3895323652602044690,
6247176993757894998,
14018764694053309664,
12148460064737427051,
12519272021732992903,
4265286318973514000,
13246207213367864932,
8092301291433872754,
18157183851941858474,
13632398639372993593,
15041229054496823587,
17438882071637825679,
16897762262634509480,
5985915708134883861,
17069291239962633754,
4604617849471294129,
7404601016313800462,
18032855475618560618,
17278074032422674715,
860111812404472121,
7676514517933742397,
12645077157634386901,
6253760177721599414,
9582459955741222618,
6555031122495818025,
9109772022144641002,
10312926431630695967,
15174450307054914476,
13667236735660909752,
8408881821411653704,
11716946339587432929,
1922786935178624187,
12807837642974514636,
2473722894595905227,
5458426645784377815,
17442014199053342412,
8890119087458894100,
14425743191525790241,
16991179320870950910,
13035467074473694191,
5787345193441130361,
4705313533091031873,
15331508321092401972,
16030846562817685004,
3052481183062108791,
10562728949964566718,
13010480725459192018,
11461359799240800435,
2183835189889431750,
1589077507581674225,
209493893234690824,
17275528419958179992,
13786253520218962997,
8418527685430488832,
4277383631769243150,
553728001632835698,
9744726741627180359,
9472249747805929122,
2320471217112438768,
10501323670386497816,
7960518975670364695,
18361982008650146784,
13597146968161371494,
15048282371199457431,
11721290689994903139,
10236837511513990756,
9365853519324508062,
9624359956681910024,
6464188517998707741,
1613104032762890885,
8208472167568412592,
12800200029551711758,
3442648414208252067,
13536931097714636227,
13680099157307486964,
14296431146446833136,
9490494350514148171,
9088818047483723317,
3574838510805215040,
17710736595066585329,
18387087888522354666,
15545394289660342510,
1906938938574314263,
4795399658629299655,
5999021877917630376,
18186518198482153992,
15325896453672651048,
10288450437885059914,
10416325383170154040,
15252545550781802698,
11203850167434393557,
10930649003967455247,
4205680756002312162,
6052457706079534658,
8809248482758461337,
17439291973136036686,
14540031682752633228,
2866851932511598749,
7403683280133267157,
4543483651640135231,
10836604478698343545,
16677730720541412608,
10783834510772171652,
686367541545890040,
3945636644088204461,
16492288623082307055,
11410592877514597108,
4262454581966561376,
3226936869596190506,
2269258247007518459,
12712674876690317000,
715200030416229478,
4476123276882470939,
11651367928687373644,
7647140969145544226,
7054163724695468332,
9303767112281912798,
2511756170805945536,
767695948141735127,
16013838828931689852,
1660339257018204036,
17879387842407650206,
7329246204095148284,
12230296804697810396,
12554402033302195954,
143442532799357566,
278975221130083403,
704260913362329426,
16783414591993586867,
6420395195518570400,
1242530744355731932,
7229248055319127476,
7329179342212070204,
8801422143729346915,
7202896809469888435,
2740513910203208596,
1605583283743774906,
18133844077322829538,
12114669632852319147,
3777413896736836346,
10534763338306711186,
14271006494232962493,
2194873499284659165,
15408899770262126114,
9187831456838158154,
9493725892599084642,
2706928395034605310,
12457405692640371251,
17219883563575417931,
11342733020178340937,
8953543935614589549,
1650319869406153528,
1699668215805423570,
4658796056608814785,
10191145295455593970,
13899311420360969158,
14471878845989945578,
11625414899748956593,
16598163026893516823,
8574589836055525845,
7512292358343960576,
17973744362666546698,
4748081966508603098,
13114442497466532636,
17717653663975693,
],
);
test(
2225,
true,
&[
18273847592806914913,
14916661124009772473,
13753012507801233945,
2177017738569174816,
16127046055767688953,
861596526990070502,
900331037467932077,
16419285249480787078,
16218119651779998807,
4449144590778508396,
5797432146873167292,
3658745141936919754,
545168142452805825,
17148224939070044052,
12094519636288888482,
1860524967909680000,
11944377795202454761,
450998278972528990,
6229559984764978492,
692524976150108183,
9064236318526181538,
6065732669816418385,
11346079520098762673,
14920005359765058322,
2824584984376391340,
16938886314725057563,
17162544784568094730,
2586797791946541382,
14296668031704924113,
9646825613588464263,
7079812537211058309,
11120058236852537534,
12100085017675020879,
14964503322387943506,
1317980653840108650,
778234578243207603,
596521671354538262,
5006607580276807142,
15407271393272502488,
15573500044631135983,
7935314468229974933,
5125906969614837712,
16281633070145926026,
10841335053186957525,
17450307718756727023,
12333034550501581052,
10335633642357417840,
2658401353173590381,
9928967891637445302,
346433133502823118,
1125969053347945942,
12869295090499245086,
7161688279795242985,
8102170348534423246,
11501976328143442721,
3139756684381179246,
272140454388501101,
17653947300704655935,
18170419175440044364,
11620223751270977055,
15199737729791407954,
7388408950276186267,
9421939597451630319,
2597904459804208335,
6415494893523120358,
11278503427630235513,
17087603759736271563,
8499727139718896059,
13078202821805789519,
6267232287377047314,
12745328769944065239,
633458985557193041,
10591869002113750048,
11717141398383033199,
10182159168145114245,
15297338266339549376,
7675716384162360916,
14044976791404615146,
4826327060564654494,
13824111753357577432,
1900118510953347559,
8934435809233468295,
16936724118164099477,
6715750096675555516,
15742093305101977345,
6770550399746614438,
16893816526813516547,
3972985572344553776,
14352636830428013583,
7235300939595407519,
6482168811103125826,
8529869224520362482,
275752241061888521,
1657885970020523479,
16055229676929243472,
1329626840527245712,
11652057338991275044,
2200299065278759357,
15923824600667998353,
14452285691076415854,
981741195753309331,
7201095575238789005,
13340345121085282794,
2680287044054356020,
9408615051995915315,
10441077296581096820,
14712361458266681524,
8124482655364073111,
14222323278853437602,
17070664871184295932,
17474138478542725542,
15177656584895433414,
2526272351085273991,
6899922232335160103,
4319287874022868518,
15816851634040015111,
12112152024215446224,
3606792321694648705,
9429172934661010546,
16821618974076073653,
12119323924085732779,
9269996314367783608,
11677711150311827044,
14826179744550864313,
14311566973567724922,
11690766935901640332,
17692848354524494381,
11471034271597096968,
1783135434038615748,
14881574202813672930,
15830300711784462210,
630062474555626774,
17060519393404392624,
14757894127409047620,
12461523429328038945,
5445397329406998939,
17884801583819720842,
1818977548627787018,
9113900825703689420,
16915916658972784066,
15622182061515094917,
16920477467185064686,
11826213325249074339,
5465014424784826852,
7335719503225494900,
15841161992748631086,
1299642982951657968,
197715083125423811,
14284377913572972912,
789668823628960978,
81036771547499486,
1988737592120412916,
13618394416444865222,
9426939251263437583,
16147835905603573032,
14670138126638825807,
13365861818007883916,
187274109266309872,
15584591815633641607,
7468625031687560535,
6620786124781371382,
13074327572766063757,
8811083685803335562,
14556428240003445098,
15168607761515723842,
8228373127931581991,
4449537695769626872,
16189599284483220268,
797498,
],
);
test(
4070,
false,
&[
8108005815282335195,
9146844186444094918,
8660083345757410800,
8098332886796284485,
18327436189098520241,
3444039843702503689,
4140780547010543813,
14037137740150481503,
1778663445558401359,
8801570388752073452,
2100918768041211855,
524703799362959113,
12962247820844726992,
14701744186225035810,
7313567667433951704,
10050831291847253075,
6522212258387665281,
9713357079840432969,
15650953094464421347,
1209849253782734984,
4490688349070706208,
3139050496689458569,
12245827531446440255,
7885981168676004558,
14154661077321356322,
5349852652757407610,
16092452000899791090,
5332211751874201060,
2010166260630364055,
9798313122251961485,
218932147329958256,
9022218650847797161,
9247716414481763471,
14400589478286751493,
155515641352761450,
16090683018468668029,
18438337824921230249,
16750617951041927284,
4466848102871550334,
17245130053737553841,
5684920055966011256,
17485566453638379463,
3876098111780047824,
16170758650201105177,
3329608698571465239,
11098790367425582117,
6479997293989211563,
9589433605206440133,
1627857831675420300,
1732996071343246956,
13677549908265537781,
13009227383550369090,
10961856472489506886,
14877397326320187840,
16507486074381907645,
14585352423433247440,
4772857464862032589,
12016886091453855080,
7931222225152140551,
13652152998550600083,
16998629316990967973,
526526529893597072,
12092338051210294623,
6819207438863426635,
11198129540720007747,
2941664361484076111,
11290270564500831896,
7141368769790257178,
4310192286254467973,
8626208125424982752,
6486300810327348993,
16817813221529065857,
1665451483178444523,
526626375466106821,
1558004989071692770,
17197912381461676471,
2028020400876381294,
6632176584976099417,
15853871790538747381,
12244096904102365064,
7885917276665675411,
15005896934276204010,
10004696875159009950,
564876699456822610,
10276340856888745756,
16929103490933678961,
11766003323021850140,
13379448244674233012,
1700622392771761597,
12998026843356148399,
14386135549950737873,
17103249986604805696,
16786552926533509269,
15192402249011372416,
3682655530759859389,
6438705993413043824,
13321028524215423815,
1823597566198742888,
4362292623191872397,
8810115919852355307,
6024401878081901215,
6718375548708698908,
65836699280473345,
5459920132720522842,
17611518624765606886,
13413230224953721533,
18269011901647493745,
11482220135864365751,
2391276440752141958,
7953372639070979047,
7719335541802590983,
1578078632861068430,
11450608370291117368,
17345790563481277271,
2471612067088960322,
9509634917954887016,
15790984357169346054,
3068287571882149714,
471828767153656274,
13989984920988442927,
7509949839462576562,
10968664464658574290,
6077107907583745923,
14180003222908660504,
785997593410843284,
15346199982210062573,
2127241843253405780,
14106663760181537824,
1816989325079298256,
13585984481704676966,
16775201233882366395,
15894543543338446770,
1107757662154265429,
8343871796706615587,
4004079488409770502,
13897369022267696941,
1900082861214911602,
716522355498280832,
10878671752431301621,
10824325209201257147,
11326396537153935107,
3449811571484933271,
13282337890784915268,
7114243324086389360,
12077364721569316700,
16806236645113874712,
3976467828062833535,
14892561338874070677,
730742184143676508,
8041199874795643530,
10588477393010195205,
8741684265023787402,
9323226257963451657,
12383914466097937740,
5459183481775283109,
8713085987825614917,
13599525973515812615,
18412620200699133025,
6654671808175209159,
15512514585286904591,
3418160363584141286,
5329252877044658765,
1773517879281305085,
6751907522769980960,
5595071891327138711,
15092986339807365771,
2637668950041653368,
9120481822278454853,
6888869033907116052,
2355630305042933816,
15643204059310730325,
14189972604337948712,
15973742050610849695,
6242065490899143192,
10363937503100539096,
11070337623129049141,
8371320746562326912,
12695119021290132172,
10946420405222747694,
11793689207562115243,
9738441606075555748,
4055649477600335048,
3880331981234421156,
13347438816701426930,
17047267217526913425,
14743067117062752918,
7500680963739160488,
3488447525771141371,
9324555149161510174,
7264600294919436405,
9007784967508818611,
6103106720642023698,
10517676694084426843,
15560433103569708967,
2746068979338915377,
4985185996082465965,
16952688848835623971,
5109870761485173378,
8634678600073803408,
2319185650670298791,
12712939795386441047,
12844727668639157639,
18206839820669131705,
13819514640691885271,
4818348659491619709,
6617480138343747641,
15213182099370869167,
14637440613867531472,
9652794545650675745,
6662269855919686728,
15464527851536273824,
6948300103349899268,
753008641517257019,
18423686888802874368,
8667176541059774446,
7099552216889810617,
5097390314227011257,
11164163665133923676,
16601595315094089072,
934251793604345199,
7561790558864090771,
978936761586367389,
17101343332617286825,
18235594016090146675,
8892479711303127261,
9809871209460262551,
2394882822052699187,
17253801929346615689,
11866062736428885642,
16437653361862401491,
7486219130830357614,
13720638887748552989,
3021364063186030632,
4790724598986510238,
14359903221320647419,
15701149522880886933,
5746571782218451762,
7210169400177123347,
10042203436933651963,
12677504245079166833,
18175151564707403074,
9425061978030509015,
5758590662601337386,
15348859264339969047,
84847087193038207,
9111274560170647524,
4278081610518772774,
12529339272615071307,
12409855992802623412,
9523579083364964737,
10131834173738880007,
13754924237593988998,
621522042857583856,
7464325591076653888,
7830537412804901743,
6521359168347430210,
16894039362572777376,
5413242484644566268,
14890107208076170436,
12980026768650320887,
11398310152701007006,
4453768301766954152,
2532536434582483661,
8315666704783771480,
13461364238018113773,
2367277318932022237,
17591329597188385026,
11375623002647255287,
14912925391917134409,
17574598362054282658,
9404088160471690699,
718445096980481234,
12792792291239978324,
8006961223861908611,
16462573277199771867,
15753551978373173836,
1165618856952885551,
13488872490939284662,
6292751434775819077,
17978555343322705896,
11917634234603254804,
162840434454496298,
15468092375694967720,
10967364594358191032,
9314385576792743968,
10874257552955261204,
4080522163464587172,
775060301135710213,
15512539461380143991,
15282862206590121475,
11634145833295838957,
3729296162985408021,
2708304538658858121,
12973478170148581224,
8050517243904765020,
7652018392181115173,
6828100662787911762,
644540307178504165,
9834244593696654688,
717190824240544061,
7918203759694436774,
1381239225989678565,
4037837100601917635,
10802212765762616104,
15085162986324183364,
640803418391629184,
5440933420358031637,
7912472064612543150,
6022949383217060170,
17164562859107739409,
1707274268270363419,
16353036691579357283,
9896120685866007660,
5240055324003979103,
9943488260620580398,
2795797772511437220,
15728639203804433038,
17163352271120418930,
4576984692721900001,
9920664011545963272,
1162651417625311508,
17117469006464985573,
7325235138239111279,
18304978043412704382,
12887402943015993511,
14814534017899278196,
2423645702540296415,
3089940732951430909,
243463633479215389,
1853544701457559150,
16340002828745074453,
14353724121437826749,
10091976479103341782,
16445589728945554096,
12491958380500551140,
16956760932267439248,
8027499409757227236,
6125007472513238023,
9932580797249172181,
8500623667517585457,
13042021579813295620,
15746465657147920157,
4336138550822800341,
9810545091138121169,
5082389296265504858,
2797088738314226811,
1788720676657601196,
13852906260052809399,
15901487609613735742,
16898133139552432839,
9518583808608390497,
3135780694510726770,
15768959579073101320,
5060730587445662107,
13026896330095181663,
13406455708166664349,
15874938122077036419,
12502020629429544436,
3206388887230923597,
5335712912997776161,
18320472783623629896,
12300785747455089667,
13200934099356667514,
16185793709615010552,
10504644792424617533,
3165770672396699194,
9659271587384891683,
14071499891855926173,
10057304373257827497,
8747735409408624915,
7073755668073479290,
14289860991929203106,
2241519710446822187,
3895111632723557508,
2526746390679189521,
3116945709823411600,
17383197281821176783,
7952464668971727516,
6901807899244715536,
18040113216886148526,
4268131054090303895,
1487358751414798288,
7752711065051636269,
782881033717716437,
3048915553972286578,
17944199781198644729,
9389246360770923456,
16122431310696436556,
10776235947384101503,
11061273148200041873,
11376451884458646940,
13228985150393505898,
10201260035282798966,
10960968295486930139,
10150870526387620225,
15622960701236479318,
10830024109717612388,
11069526249991212591,
7177411583475908506,
12883497517546755586,
14452533555439112738,
2319722755462632117,
2707463600284124085,
1640962093580202224,
1781980281809689073,
15431145229979346468,
15450020011414281071,
4610352806777138140,
715901537448564375,
7906779838611334191,
9295186163734943091,
13837118237702626530,
10628587043038215377,
8173817480377720286,
18146513027571012760,
18034377209743766349,
12416434057720465458,
16863109019369808778,
17598425176089192373,
7838352420531465275,
6446253944183856472,
3217827157412015166,
7736416779564775474,
11944279093150198319,
1359722430089967762,
12944512655507306702,
6968226813496259100,
10697114723710345120,
12045439838989284122,
14360294208856859982,
13554544330260187416,
11960481134019314560,
16193728456024646791,
6788935070457860696,
16784253667098474942,
346235036471591563,
12579823797379718533,
11237106727685787594,
7376229368874669746,
2310494137345974933,
10699485085862861475,
17827376656397906407,
12654909010486092313,
12911864664898312670,
16753920293216445659,
6665140426308933113,
16331633263932455518,
10109679348425115019,
15893667959446481301,
18406325439525742133,
933973555678699597,
7168028379341447244,
3151961147604448767,
16537206733760622467,
5066764475441679955,
18142248769235084338,
10267108442140677091,
15428903838728157772,
817803212986250530,
14382377762501152229,
7294220161923800220,
7081723256077136000,
3334475525919947583,
16199270874538651756,
2344559218216607405,
11987285877097183410,
6271232791990646890,
8865933992675026303,
16277240149463018400,
1656896235599446490,
11150448321793527957,
4631896433546355206,
8877084437753247207,
7307284130241324899,
3898492975685743779,
3665446048463257912,
14648028503878372256,
4141262678851999482,
15769177955090495312,
15700478929465111924,
13772286815471806568,
16819697748793130742,
374816477005121133,
9978039585089436623,
5388602092448346783,
7599620772394967758,
13068216955460967229,
2209814478936490342,
11426676931961095314,
3575899553386457735,
10074556064068343208,
1175343165804101193,
2579842808821635021,
12160230121712404482,
4570123963392650145,
11533242066554433675,
8978786221712843977,
2519957542118309466,
11338180312992409210,
17438791722639593890,
235036220639090508,
17299731811003138346,
11345013161471373979,
6808878923112761884,
4906649794209058970,
14510541350917650537,
3129870112661089444,
6780443774321041251,
10383203886842753587,
14791651661609640635,
479104220414488434,
3308544737491745274,
12357304405135409837,
17075636268959836058,
10907896764439381067,
11643599381158439431,
18424980765811796263,
8249222402674259286,
9896706913692159539,
2152931576999706359,
4727177868031013262,
3266165952382965456,
9085838590190029565,
16643373348625444382,
11565678787598161058,
10615433009880595611,
2811627817244839406,
17919168585610158932,
15174362170354828474,
5597023051532920206,
3411824531765525771,
2887283203315816513,
9247340977378434321,
8972524604189795344,
3111627944095111700,
13483341139541609028,
9578789344755939896,
7839906735318986374,
5332229875909435203,
11793410887897771248,
6502944694411264103,
3797221239185211363,
2318303302786427439,
13589147558791336226,
13963887555481507589,
14815243147364150315,
2874636415001201973,
7791969142922524431,
8142478508158078750,
16320253976455093478,
11410599986950683085,
6941190512875461993,
714780298870163634,
12186367514332744780,
7396330582410885775,
11973894210027103516,
15383581181396047007,
16278071189583596534,
12216205906506175663,
6100928555352159602,
2937593753448772352,
14364941381544585739,
7143026965390827808,
12201653352837638909,
8268259781562500315,
17457954864467036821,
1325561951447557612,
1830250720349684188,
6503632833560144671,
8957246064803922704,
13184493622423870667,
3800624358443674755,
5833302624748742405,
5853990385357953007,
4303717340298687263,
4513758912754435790,
10845881821986243973,
18314135169801212762,
814247782154798077,
4175446608061850087,
14066747770756565318,
16223104902964522012,
14386221615141474583,
14286245335107087094,
4797660228332850220,
12494772503717947664,
5046526480383637489,
4695803558343679414,
15207164406494018074,
10746131379349268959,
13427849410099074058,
12960999646017015515,
10875962048958581312,
16380543578406679915,
1081549612447048742,
14988053947085110551,
4719671945245391810,
16089148134643534992,
542091408184916386,
17256758054232279755,
4139827917918018104,
12212703329706756000,
16728271907145403562,
2812092140620955679,
12743744931348422865,
1697950412660640926,
15168405896517504340,
600504526,
],
);
test(
4386,
false,
&[
2067770789339411803,
13103096875436466845,
10775991317478993717,
12967380299398919437,
12020325680191252113,
17748295712695560928,
1429341763317489229,
12678340224185994909,
4335442947861292402,
5254780375536440952,
17074502202508083505,
309407234721139885,
13452727935428837455,
8651378078472139112,
11512513997222178700,
15910186442568670644,
12845112729418812790,
7897815290878156013,
9244723605015583552,
17818446835461168600,
9268757667201962790,
13518324509513650058,
10462750832084307848,
17365663074296091214,
3601241491427429096,
16011129535131124250,
188279845157362453,
11102064840933848532,
12976705436704377860,
16067635780216235799,
15111235286034779573,
16949342242668510111,
15198057271216638117,
14221135849758717397,
4944363911855682389,
3187706824974319087,
7338540094563526202,
16578881813150901018,
11167625661382169176,
517732891565245060,
16978960760497725346,
8776342161961474572,
7065757446489966082,
7633843099211849039,
10126092316436660909,
7137931307826524381,
10378215122356064905,
17259871895964295908,
12904171429142559149,
3245154771911236476,
14137987011116880665,
3313964895395428359,
17536273921393851251,
713485028257444541,
2504041554095751793,
11868371391163863223,
6651805351133757865,
6667440167584357174,
5410381989650680365,
14991818175930336399,
8257594786289573987,
5706253266337186736,
6124744329210826966,
8947309000932886151,
2828062293304464966,
2945904981118350722,
9340961774751783834,
6991179653428794675,
10353734651419249748,
9995290938924246850,
13748292297662222218,
4892960822908531583,
5001073284079337557,
13395090824536719310,
16748415575373971262,
3794277149064466315,
3471133925886159212,
18287753555606486434,
9672715726223475697,
274643140420740271,
5084208256841635357,
565582889520143382,
14443006075048681485,
15151943957630016490,
2415682863008959026,
3647193967014640950,
4900474299482998069,
7440294411928457855,
7555879457509324101,
11720033631659853173,
7634817390629418714,
5364401984816035681,
14274975916464347588,
18110903883298124645,
10451080161694932573,
17274117833138202923,
13092023069546038740,
12707287623023466476,
17701880209880420627,
2721809281104108355,
17847139586804083902,
17102921262115553190,
15532642833766944434,
1280075840001965788,
3761354226423057718,
10238421667499233931,
16260871926280516440,
9728473062383715969,
5953520808705507799,
263442908611940290,
12837547734028811219,
3287327756734946357,
17180396981733070497,
6685721691481472712,
4223337774056033861,
17203789254093256094,
5506147567525874801,
17525679577751101209,
10962165345191958610,
6263807420731253205,
3923945801149572338,
17284772696566520082,
2337995081818459703,
10159695744432522804,
4645991148779039189,
10456895348208050580,
9609163518931971560,
15343500081229831267,
4516517331522645741,
5703018699998096839,
9289174806651010588,
1907313371747641829,
9700205622504251902,
3384501760799438251,
5592475228402079956,
5699363979963530528,
1772165853917465545,
18293565878034536773,
13506779974076830618,
4433695301786679145,
18316157440486549103,
10582239038922153367,
37236612930183149,
17966150282195407897,
12541413422471328583,
3221443629988836742,
10375517911848610163,
16312415585539573309,
17263637399055711337,
12562964968987510931,
948248222908469656,
15567975209379123460,
8261653520686110354,
1999465121504211136,
5781047899520920323,
6315198745347909330,
2920278920380027756,
4345551993213715119,
6283657344621674559,
3606906764584629572,
3214509309748650204,
4421650669626111069,
10113279086264766781,
6040809634318513184,
10105872563177742877,
7530051675459302141,
14917228249506435637,
4803471693748163459,
15339413088591036105,
1138826137575079324,
16391062326234990346,
14971482629623839337,
12498986044767135726,
1758634949316069683,
3079336619173718801,
8019450776809033904,
11043397957650314282,
12422777714615135210,
1600737775507512235,
18027592484657533779,
3245499257818457797,
16997244019634782986,
3056694745780408313,
16838597974032301566,
4231066868194520257,
10562550261283056758,
8961231382598729157,
12511921298671716507,
1865431125930113477,
2907259905584584543,
16284546744177846395,
16912600838448041892,
5685768352085959742,
16073286910652494724,
6283460899260262733,
11006248608684764980,
12393743873088932506,
12391913626649357467,
15016416664079279639,
9408641421320112644,
4025080079418204587,
13515889317109760861,
6226634619622204428,
14051645394100010803,
6133348733808000448,
6549072550797710617,
3366502349209799505,
4214984042943155540,
13545152513431319859,
795203566590623457,
2957066876294725061,
14037361440208811220,
3567928787052247594,
18129592358468459211,
7391337147860966470,
9745224408810299881,
6273194274566822118,
5865744013188664203,
16331376339301383887,
12655709446461158338,
16058749309251802594,
16013590485222250734,
17377122665244463023,
1879007341157847506,
8175620709685639847,
5052075645054700814,
14604619995008524058,
8996782117651602293,
17751524763342629241,
6405720938723467480,
9374406085408070641,
10902473135566069570,
17299547825885109840,
9378213062126977886,
10748234354845075895,
16298760983383038268,
11912524381622117490,
17531579882154090089,
4638623466945320294,
9718336125194098908,
17748627584772750138,
5929383739994257604,
2634528888377348952,
7452587852059168494,
10479972321254713875,
1207579517364184495,
1227691654580968152,
12283325902343980973,
3630742542495239330,
1557735469640288318,
13148409011485075278,
11694984553024128048,
13853138208344888607,
13075028243661617397,
6077061419898013703,
10759228302707904856,
7134870213220203017,
17700670474189599567,
6488352687619878666,
14335593354894875389,
6344626185331917569,
14406699681719439442,
6714341065455077735,
4791758696562431350,
162497200523271921,
17479090938200299691,
2988688594805820109,
7777421366994092731,
14642692051425214172,
6274682819626865559,
5229423047741496007,
5654852991719816168,
5055395278775913297,
12041756526601788850,
6814108790911398001,
13599277275502247027,
1574731768977388996,
14139185185305594281,
10348783097165818778,
16356555785871812759,
8509205960970416974,
369792736551032730,
4928560669248384211,
1496296389308083367,
275482014864563394,
9515713819908090443,
13779279241489032499,
5922260955368225052,
1092706023383976782,
2360049775560684078,
10830508317428607424,
11355555062201315465,
8822901367110163092,
8360846078201768657,
5610591053096960621,
825839549030470748,
4354013872927963141,
6246140926823935603,
2664120007387415299,
11028705440560322531,
10625898421812353966,
148691473840606177,
8310156060530348557,
6684141576519691078,
10666277726485832508,
12496909850771141958,
12640316601276796117,
1625185014000874153,
12691818688161663560,
7284978345576571395,
13570120000390501180,
17258139152508325657,
16431051452047113788,
18021498085837424736,
147540858693017597,
16489503519317138018,
6384423972105245397,
17968902491833871706,
9389823822199644659,
14015616956644237252,
1624016862827524307,
1133086695225646084,
14210479644264771704,
9354045035850960349,
4999905551939222112,
127779107599803994,
17188565212169682757,
9095797152343956231,
7477994596817475252,
6929119664609167341,
3026229977813010602,
3373603747000003839,
402015014046664505,
26644720949978834,
16550954361894454284,
15537993049361919153,
2802848809767628844,
12723476677303988431,
1452153691672522097,
3434061729562431318,
729282772583672128,
7702161485333588893,
8717527779288695787,
12363485505590025970,
17624693189004583309,
14685537190335019953,
7702477702547611841,
13950049520337589373,
995603177974720045,
1908021199455081620,
8666881553466182833,
18205165727916302250,
9075169860963458400,
14214404287201285116,
3730790297335296211,
16018490608374186886,
3817924654967992585,
2594301786026675009,
15391635385542285594,
12501364696981125528,
15521243366566790239,
15115184551511400222,
11890281585537800925,
13743275121740710291,
18290209697475844389,
9452021830711120855,
9366033362614110364,
15189787976271753218,
13926199825258867108,
15495826818284245741,
8531249945458971662,
17589848977595818263,
5117260420662179148,
10609979181463468221,
4913348785482518086,
10558959588352660372,
8256184825576553677,
15328078566821422102,
8369548310319076057,
14408099923166180103,
12023136302419338418,
4185185540229752140,
6826802409442294703,
7577964011315904722,
5184334342724491008,
993509100019263200,
15931436829275119251,
1146421971146413118,
7457752172737922635,
9303468447317898804,
16896814437635093007,
2897580989878368123,
4607005167306394543,
13191995560910209108,
754818302289945956,
16550875926839443808,
7988613715747824244,
7594021839994771817,
13390383436084264345,
10818741266704850020,
9840567310602600933,
6853317455240951849,
3654318299357871447,
7165021883724890419,
366327955050086071,
14929430926370816287,
15929091848994821752,
11105903166789344918,
17397713166933660028,
940076493347828340,
6881587310329390584,
2525314747911475552,
16039575856899289003,
6590095526609987943,
14780829395712816729,
13403664212049269290,
7776885716456199825,
7327709346503253495,
7797242194106433773,
16614929396385540024,
5614139257682381061,
18047475783289703107,
9666137234872592914,
18196751923076222182,
1735358215136480054,
2825261148642530486,
17958215272827091532,
4229064305320080722,
8107409220128419983,
2659809653637122796,
8461071852700444712,
2853300478568934095,
12627226863684674629,
1725915213416318852,
487301172206353235,
4413773887930902588,
11380364842493382110,
18202450692039293805,
7784494480032084716,
12727459447363886037,
9477329144027792300,
9375946880998142541,
3850113885112012173,
11830472656413909940,
13939088354425096574,
12431341669790120564,
14604778789765165983,
15232263358213700722,
12591997966392050807,
5934537059080957325,
9116727594927728823,
831125065896912587,
6919754862689771483,
10898884224579093352,
10194872422166905419,
2240873485886821150,
772949527074947092,
722360265481154865,
7863960452925898308,
2995106245389276294,
6413625243236464846,
11417572663652050724,
16800248131553723377,
13503562407484296894,
13751605094817502750,
17009103221214602662,
6290212481944391998,
16492192720802115237,
3359973450786126320,
18399902818940892859,
12411848360389779577,
16353647163615635517,
14511780882165179745,
4167580674549721515,
1157978505376818537,
4823712731701839796,
15625736345573532694,
13451767465863821756,
15449238941112417676,
15564277366463860073,
17123483066444823350,
17728013126554602313,
16630084534442117029,
3077949725867728231,
16563931105160154865,
1246592974021224293,
12466022741969968785,
936399083803917084,
1508756071576207725,
12593257295671577526,
15030750707522627616,
13422604362668833145,
5988522993706110934,
15545744445564958732,
1333287819193404898,
374964701110478911,
1268449382615324030,
18152641639961098650,
13911634194020977647,
15751397195385234389,
11910107323217822218,
6719368906000612979,
539357533696613124,
12370714977713865320,
11182314386535123678,
8119574039901243532,
12179800389262010105,
1510115720081333085,
3080816336433056477,
7208163224523064396,
4484890163125768129,
4471197540253572019,
16164979284990145212,
1352434240322204577,
17709563636005322148,
6175465245802596932,
2813064733658804479,
3729563625698838686,
17030954856394461019,
8814338780961745521,
2180303021116863804,
10602246745335408702,
11278176099084345908,
2989599815829423813,
3174997621154098140,
6013428651509341881,
1056309801926189131,
6754803862830721714,
13831276002295643570,
1528921296308702728,
7027293378815715253,
14550621546237275727,
14579138781069179492,
16649016585856135100,
2169005788597798917,
13545574963505347448,
6837331033324486251,
7090962232927689286,
4662659566106165098,
8754777632717149483,
5804275858791907219,
788853342477740755,
16728861156177940737,
11428624619995598035,
14984172660064414249,
7586067300257715870,
13544922098234698859,
13257509618658838381,
2652216851092922006,
7861597740154527454,
1410202913196998970,
729890979789569621,
2143681954235555293,
1922907112472408969,
3628498397933816460,
7247461113839898678,
1912586770250857938,
2554218233645160534,
1743595205444296423,
8767829447546562406,
567862460760224080,
7305055418633592092,
16866314930981097852,
3795937503324310941,
5621962951370066494,
8868249692690458913,
721008487395008718,
7430091675158085829,
16331765483270902465,
7335683441619026843,
3257550354989871481,
18264160295416879866,
11136793850551427435,
10546469165077048539,
5550997632077748707,
7153389858358930639,
5061349939637694485,
3990963419914210519,
15864228418379343270,
10313411382620536299,
3247364825267582220,
16798279756492637943,
4799346260722321334,
18161385831180514221,
5680400420092624151,
10244339711594697803,
865876781659886278,
13652502876619329633,
15440911199202656750,
8821648827419111566,
9157488610126501397,
10945666626044426963,
6969723870784479629,
15622137819654655923,
3894460376560585304,
8699178934690713236,
11719950596492741147,
4303171596568431905,
2201336563349598335,
633521128747937906,
10783414600329714759,
12633157919692423052,
16165320295662473268,
15791357301220105561,
16707503754652450664,
14638594967732844399,
11617299177772471971,
7307198283537189698,
14701917077406390219,
18245496844025624337,
11104562001690845490,
6064130654076660079,
6513424921504926691,
1737851892642531957,
18377988941784482593,
8034223685660909576,
9983995693134438566,
4814979217316997434,
10286008916702006441,
18263950945303861757,
17727582182642068647,
8847975247191099221,
14186530850444591231,
848650607969070940,
11636660174669653982,
10790673005564564668,
14420034928065783601,
8938173207516609044,
18440352591895674931,
13402033683256872796,
18045033870573153376,
2237292078652826406,
10211782132693590673,
772050115413368836,
9260457899141949663,
7450174044286317401,
7479368663774737969,
9236392813906009688,
11260429241598988834,
1295346375121863256,
7631713597562972500,
6013785207649710084,
12504083400869715484,
10391675565598624561,
17086420331228234856,
14617438647774567077,
15964728536429688928,
13460421593436649766,
16408312779121921256,
6520489253483657869,
4730756746647128773,
9028350139788839089,
7953083747782670383,
5096299587699598800,
2951011592716102034,
1556959608597785858,
11489708918307621984,
12277065314059308881,
10220668622316585965,
11995324860038254033,
4353183691485690945,
427717306190904666,
],
);
test(26, false, &[11182600415380068643, 2]);
test(35, false, &[13586117418673889649, 130422663336]);
}
#[test]
fn test_factorial() {
fn test(n: u64, out: &str) {
let f = Natural::factorial(n);
assert!(f.is_valid());
assert_eq!(f.to_string(), out);
assert_eq!(factorial_naive(n), f);
assert_eq!(
rug::Integer::factorial(u32::exact_from(n))
.complete()
.to_string(),
out
);
}
test(0, "1");
test(1, "1");
test(2, "2");
test(3, "6");
test(4, "24");
test(5, "120");
test(10, "3628800");
test(20, "2432902008176640000");
test(21, "51090942171709440000");
test(22, "1124000727777607680000");
test(24, "620448401733239439360000");
test(
82,
"47536433370128417484213820698940494664381329406799332861716093407674399473489914861300713\
1808479167119360000000000000000000",
);
test(
100,
"93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463\
976156518286253697920827223758251185210916864000000000000000000000000",
);
}
#[test]
fn test_double_factorial() {
fn test(n: u64, out: &str) {
let f = Natural::double_factorial(n);
assert!(f.is_valid());
assert_eq!(f.to_string(), out);
assert_eq!(double_factorial_naive(n), f);
assert_eq!(
rug::Integer::factorial_2(u32::exact_from(n))
.complete()
.to_string(),
out
);
}
test(0, "1");
test(1, "1");
test(2, "2");
test(3, "3");
test(4, "8");
test(5, "15");
test(6, "48");
test(7, "105");
test(19, "654729075");
test(20, "3715891200");
test(35, "221643095476699771875");
test(37, "8200794532637891559375");
test(55, "8687364368561751199826958100282265625");
test(
99,
"2725392139750729502980713245400918633290796330545803413734328823443106201171875",
);
test(
100,
"34243224702511976248246432895208185975118675053719198827915654463488000000000000",
);
test(
473,
"24105348290207984100197317421171182490921899413623319647593979414961419154254094380115999\
189301460161039406301206658065847305231769123134642895607903467624412688193137891638118329\
605237994774653987740749807295557291435144240110313449108135603699200932257584350374350787\
323659752996357699013258512218790061191470897010499751650188156859142205866225173540759120\
884362743953738057721709446884608434913698856509684431470876923079372190040412643076525278\
35572579953211852767587427960391216326823983495675207677777507342398166656494140625",
);
}
#[test]
fn test_multifactorial() {
fn test(n: u64, m: u64, out: &str) {
let f = Natural::multifactorial(n, m);
assert!(f.is_valid());
assert_eq!(f.to_string(), out);
assert_eq!(multifactorial_naive(n, m), f);
assert_eq!(
rug::Integer::factorial_m(u32::exact_from(n), u32::exact_from(m))
.complete()
.to_string(),
out,
);
}
test(0, 1, "1");
test(1, 1, "1");
test(2, 1, "2");
test(3, 1, "6");
test(4, 1, "24");
test(5, 1, "120");
test(0, 2, "1");
test(1, 2, "1");
test(2, 2, "2");
test(3, 2, "3");
test(4, 2, "8");
test(5, 2, "15");
test(6, 2, "48");
test(7, 2, "105");
test(0, 3, "1");
test(1, 3, "1");
test(2, 3, "2");
test(3, 3, "3");
test(4, 3, "4");
test(5, 3, "10");
test(6, 3, "18");
test(7, 3, "28");
test(8, 3, "80");
test(9, 3, "162");
test(6, 4, "12");
test(8, 6, "16");
test(10, 1, "3628800");
test(20, 2, "3715891200");
test(25, 3, "608608000");
test(44, 3, "5577337931669504000");
test(
100,
1,
"93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463\
976156518286253697920827223758251185210916864000000000000000000000000",
);
test(
100,
2,
"34243224702511976248246432895208185975118675053719198827915654463488000000000000",
);
test(
100,
3,
"174548867015437739741494347897360069928419328000000000",
);
test(8, 6, "16");
}
#[test]
fn test_subfactorial() {
fn test(n: u64, out: &str) {
let f = Natural::subfactorial(n);
assert!(f.is_valid());
assert_eq!(f.to_string(), out);
assert_eq!(subfactorial_naive(n), f);
}
test(0, "1");
test(1, "0");
test(2, "1");
test(3, "2");
test(4, "9");
test(5, "44");
test(10, "1334961");
test(
100,
"34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396\
429850988990237345920155783984828001486412574060553756854137069878601",
);
}
#[test]
fn limbs_odd_factorial_properties() {
let mut config = GenConfig::new();
config.insert("mean_n", 4096);
unsigned_bool_pair_gen_var_1().test_properties_with_config(&config, |(n, double)| {
let xs = limbs_odd_factorial(n, double);
let x = Natural::from_owned_limbs_asc(xs);
let n = u64::exact_from(n);
let f = if double {
double_factorial_naive(if n.odd() { n } else { n - 1 })
} else {
factorial_naive(n)
};
let zeros = f.trailing_zeros().unwrap_or(0);
assert_eq!(x, f >> zeros);
});
}
#[test]
fn factorial_properties() {
unsigned_gen_var_5().test_properties(|n| {
let f = Natural::factorial(n);
assert!(f.is_valid());
assert_eq!(factorial_naive(n), f);
assert_eq!(
Natural::exact_from(&rug::Integer::factorial(u32::exact_from(n)).complete()),
f
);
assert_eq!(Natural::multifactorial(n, 1), f);
assert_ne!(f, 0u32);
if n != 0 {
assert_eq!(
f.div_round(Natural::factorial(n - 1), RoundingMode::Exact),
n
);
}
});
unsigned_gen_var_23::<Limb>().test_properties(|n| {
assert_eq!(Natural::factorial(n), Limb::factorial(n));
});
}
#[test]
fn double_factorial_properties() {
unsigned_gen_var_5().test_properties(|n| {
let f = Natural::double_factorial(n);
assert!(f.is_valid());
assert_eq!(double_factorial_naive(n), f);
assert_eq!(
Natural::exact_from(&rug::Integer::factorial_2(u32::exact_from(n)).complete()),
f
);
assert_eq!(Natural::multifactorial(n, 2), f);
assert_ne!(f, 0);
if n > 1 {
assert_eq!(
f.div_round(Natural::double_factorial(n - 2), RoundingMode::Exact),
n
);
}
});
unsigned_gen_var_24::<Limb>().test_properties(|n| {
assert_eq!(Natural::double_factorial(n), Limb::double_factorial(n));
});
}
#[test]
fn multifactorial_properties() {
unsigned_pair_gen_var_18().test_properties(|(n, m)| {
let f = Natural::multifactorial(n, m);
assert!(f.is_valid());
assert_eq!(
Natural::exact_from(
&rug::Integer::factorial_m(u32::exact_from(n), u32::exact_from(m)).complete()
),
f,
);
assert_eq!(multifactorial_naive(n, m), f);
assert_ne!(f, 0u32);
if n >= m {
assert_eq!(
f.div_round(Natural::multifactorial(n - m, m), RoundingMode::Exact),
n
);
}
});
unsigned_pair_gen_var_43::<Limb>().test_properties(|(n, m)| {
assert_eq!(Natural::multifactorial(n, m), Limb::multifactorial(n, m));
});
}
#[test]
fn subfactorial_properties() {
unsigned_gen_var_5().test_properties(|n| {
let f = Natural::subfactorial(n);
assert!(f.is_valid());
assert_eq!(subfactorial_naive(n), f);
if n != 1 {
assert_ne!(f, 0u32);
}
if n != 0 && n != 2 {
let g = if n.even() {
f - Natural::ONE
} else {
f + Natural::ONE
};
assert_eq!(
g.div_round(Natural::subfactorial(n - 1), RoundingMode::Exact),
n
);
}
});
unsigned_gen_var_25::<Limb>().test_properties(|n| {
assert_eq!(Natural::subfactorial(n), Limb::subfactorial(n));
});
}