베이스 코드 구현

rust에서는, sethash 를 전역으로 사용할 수가 없었다. 삽입, 삭제 시간복잡도가 1인 자료구조를 쓰지 못했다. 예상치 못한 상황인데, 차라리 c++으로 구현해야 하나 생각을 한다.

그리고, 구하는 숫자를 10000개로 했더니, 스택오버플로우가 난다.

static mut gat:[u64;1001]=[0;1001];
static mut x:usize=0;
fn main(){
    unsafe{calcul(2);
    gat.sort();
    for i in gat{print!("{i}, ")};}
}
fn calcul(num:u64){
    unsafe{if gat.contains(&num) || x>=1000 {return;}
    x=x+1;
    gat[x]=num;
    if (num-1)%3==0{ calcul((num-1)/3);}
    if num%2==0 {calcul(num<<1);}}
}

그래서 배열에다가, 1000개의 숫자만 구해봤다.

짝수일 때랑 홀수일 때를 구분해서 x/2,3x+1의 역함수를 적용해 가며 역추적했다.

아래는 출력이다.

0, 1, 2, 4, 5, 8, 9, 12, 16, 21, 24, 28, 29, 32, 37, 48, 56, 64, 85, 88, 96, 112, 117, 128, 149, 156, 176, 192, 216, 224, 256, 265, 312, 329, 352, 384, 432, 448, 469, 585, 597, 624, 649, 704, 741, 768, 780, 796, 864, 896, 988, 1112, 1248, 1317, 1408, 1461, 1536, 1560, 1728, 1756, 1792, 1877, 1948, 1976, 2192, 2224, 2341, 2389, 2496, 2597, 2816, 2965, 3072, 3120, 3337, 3456, 3512, 3584, 3896, 3952, 4384, 4448, 4617, 4992, 5269, 5632, 5845, 6144, 6156, 6240, 6577, 6912, 7024, 7168, 7509, 7792, 7904, 8768, 8896, 9365, 9984, 10012, 10389, 11264, 12288, 12312, 12480, 13824, 13852, 14048, 15584, 15808, 16649, 17536, 18469, 19732, 19968, 22528, 24576, 24624, 24960, 27648, 27704, 28096, 30037, 31168, 37461, 39936, 41557, 45056, 48588, 49152, 49248, 49920, 49948, 55296, 55408, 56192, 59197, 62336, 66597, 73877, 79872, 88796, 90112, 97176, 98304, 98496, 99840, 99896, 110592, 110816, 112384, 124672, 131337, 145765, 149845, 159744, 175116, 177592, 194352, 196608, 196992, 199680, 199792, 218648, 221184, 221632, 224768, 266389, 295509, 319488, 350232, 368969, 388704, 393216, 393984, 394012, 399360, 399584, 437296, 442368, 443264, 449536, 525349, 638976, 655945, 700464, 777408, 786432, 787968, 788024, 798720, 799168, 830181, 884736, 886528, 1106908, 1182037, 1245272, 1277952, 1400928, 1475877, 1554816, 1572864, 1575936, 1576048, 1597440, 1769472, 1773056, 1967836, 2101397, 2213816, 2490544, 2555904, 2801856, 3109632, 3145728, 3151872, 3152096, 3194880, 3320725, 3538944, 3546112, 3735817, 4427632, 4981088, 5111808, 5603712, 5903509, 6219264, 6291456, 6303744, 6304192, 6389760, 7077888, 8405589, 8855264, 9962176, 10223616, 11207424, 11207452, 12438528, 12582912, 12607488, 12608384, 12779520, 14155776, 17710528, 20447232, 22414848, 24877056, 25165824, 25214976, 25216768, 25559040, 28311552, 33622357, 40894464, 44829696, 49754112, 50331648, 50429952, 50433536, 51118080, 56623104, 81788928, 89659392, 99508224, 100663296, 100859904, 100867072, 102236160, 113246208, 163577856, 179318784, 199016448, 201326592, 201719808, 204472320, 226492416, 327155712, 358637568, 398032896, 402653184, 403439616, 408944640, 452984832, 654311424, 717275136, 796065792, 805306368, 806879232, 817889280, 905969664, 1308622848, 1434550272, 1592131584, 1610612736, 1613758464, 1635778560, 1811939328, 2617245696, 2869100544, 3184263168, 3221225472, 3227516928, 3271557120, 3623878656, 5234491392, 5738201088, 6368526336, 6442450944, 6455033856, 6543114240, 7247757312, 10468982784, 11476402176, 12737052672, 12884901888, 12910067712, 13086228480, 14495514624, 20937965568, 22952804352, 25474105344, 25769803776, 25820135424, 26172456960, 28991029248, 41875931136, 45905608704, 50948210688, 51539607552, 51640270848, 52344913920, 57982058496, 83751862272, 91811217408, 101896421376, 103079215104, 103280541696, 104689827840, 115964116992, 167503724544, 183622434816, 203792842752, 206158430208, 206561083392, 209379655680, 231928233984, 335007449088, 367244869632, 407585685504, 412316860416, 413122166784, 418759311360, 463856467968, 670014898176, 734489739264, 815171371008, 824633720832, 826244333568, 837518622720, 927712935936, 1340029796352, 1468979478528, 1630342742016, 1649267441664, 1652488667136, 1675037245440, 1855425871872, 2680059592704, 2937958957056, 3260685484032, 3298534883328, 3304977334272, 3350074490880, 3710851743744, 5360119185408, 5875917914112, 6521370968064, 6597069766656, 6609954668544, 6700148981760, 7421703487488, 10720238370816, 11751835828224, 13042741936128, 13194139533312, 13219909337088, 13400297963520, 14843406974976, 21440476741632, 23503671656448, 26085483872256, 26388279066624, 26439818674176, 26800595927040, 29686813949952, 42880953483264, 47007343312896, 52170967744512, 52776558133248, 52879637348352, 53601191854080, 59373627899904, 85761906966528, 94014686625792, 104341935489024, 105553116266496, 105759274696704, 107202383708160, 118747255799808, 171523813933056, 188029373251584, 208683870978048, 211106232532992, 211518549393408, 214404767416320, 237494511599616, 343047627866112, 376058746503168, 417367741956096, 422212465065984, 423037098786816, 428809534832640, 474989023199232, 686095255732224, 752117493006336, 834735483912192, 844424930131968, 846074197573632, 857619069665280, 949978046398464, 1372190511464448, 1504234986012672, 1669470967824384, 1688849860263936, 1692148395147264, 1715238139330560, 1899956092796928, 2582767342956348, 2744381022928896, 3008469972025344, 3338941935648768, 3377699720527872, 3384296790294528, 3430476278661120, 3799912185593856, 5165534685912696, 5488762045857792, 6016939944050688, 6487158869751372, 6677883871297536, 6755399441055744, 6768593580589056, 6860952557322240, 7599824371187712, 7748302028869045, 10331069371825392, 10977524091715584, 11091367172614077, 11622453043303568, 12033879888101376, 12974317739502744, 13355767742595072, 13510798882111488, 13537187161178112, 13721905114644480, 14788489563485436, 15199648742375424, 19461476609254117, 20662138743650784, 21955048183431168, 23244906086607136, 24067759776202752, 25948635479005488, 26711535485190144, 27021597764222976, 27074374322356224, 27443810229288960, 29192214913881176, 29576979126970872, 30399297484750848, 33274101517842232, 34867359129910705, 36410591071254528, 41324277487301568, 43439678838392604, 43910096366862336, 44365468690456309, 48135519552405504, 51897270958010976, 53423070970380288, 54043195528445952, 54148748644712448, 54887620458577920, 58384429827762352, 59153958253941744, 60798594969501696, 66548203035684464, 72821182142509056, 82648554974603136, 86879357676785208, 87576644741643529, 87820192733724672, 88258002797586473, 96271039104811008, 99822304553526697, 103794541916021952, 104602077389732116, 106846141940760576, 107152240442197788, 108086391056891904, 108297497289424896, 109775240917155840, 114216295335799601, 118307916507883488, 121597189939003392, 130319036515177813, 133096406071368928, 141372254969473841, 145556217474482609, 145642364285018112, 165297109949206272, 173758715353570416, 175640385467449344, 182409118865196221, 192542078209622016, 195478554772766720, 198580506294569565, 207589083832043904, 213692283881521152, 214304480884395576, 216172782113783808, 216594994578849792, 219550481834311680, 223403069581390761, 224600185245435069, 230014763416466345, 236615833015766976, 243194379878006784, 262484978776794780, 262729934224930588, 264774008392759420, 273613678297794332, 289109997568742741, 291284728570036224, 297870759441854348, 299466913660580092, 313806232169196349, 321456721326593365, 330594219898412544, 336900277868152604, 342648886007398804, 347517430707140832, 351280770934898688, 353032011190345893, 368439175482284105, 385084156419244032, 390957109545533440, 415178167664087808, 424116764908421524, 427384567763042304, 428608961768791152, 432345564227567616, 433189989157699584, 436668652423447828, 439100963668623360, 456865181343198405, 470709348253794524, 473231666031533952, 486388759756013568, 502656906558129213, 517533217687049277, 524969957553589560, 529548016785518840, 531091156057320713, 547227356595588664, 552653344426936092, 552943098282197897, 555674616525963861, 565489019877895365, 582224869897930437, 582569457140072448, 595741518883708696, 602507999953078044, 609153575124264540, 661188439796825088, 670209208744172284, 673800555736305208, 685297772014797608, 690044290249399036, 695034861414281664, 697446886844609109, 702561541869797376, 729636475460784885, 740899488701285148, 753985359837193820, 770168312838488064, 776299826530573916, 787454936330384341, 788189802674791765, 794322025178278261, 820841034893382997, 830356335328175616, 833511924788945792, 848233529816843048, 854769135526084608, 857217923537582304, 864691128455135232, 866379978315399168, 867138061738913621, 867329992706228224, 871219465766237525, 873337304846895656, 878201927337246720, 893612278325563045, 898400740981740277, 920059053665865381, 929929182459478812, 941418696507589048, 946463332063067904, 964370163979780096, 972777519512027136, 972848633947713180, 1010700833604457813, 1024819115206086144, 1027946658022196413, 1046170330266913664, 1049939915107179120, 1059096033571037680, 1094454713191177328, 1105306688853872184, 1105317526446852316, 1156439990274970965, 1165138914280144896, 1181182404495576512, 1183108408822134269, 1191483037767417392, 1205015999906156088, 1214600432836838589, 1218307150248529080, 1226745404887820508, 1272350294725264573, 1310005957270343485, 1322376879593650176, 1330996959924901053, 1340418417488344568, 1347601111472610416, 1366091886969050453, 1366425486941443413, 1370595544029595216, 1380088580498798072, 1390069722828563328, 1405123083739594752, 1412128044761383573, 1473756701929136421, 1481798977402570296, 1507970719674387640, 1540336625676976128, 1541919987033294620, 1552599653061147832, 1593273468171962140, 1619467243782451452, 1632672585889087488, 1657960033280808277, 1658829294846593692, 1660712670656351232, 1667023849577891584, 1696467059633686096, 1709538271052169216, 1714435847075164608, 1729382256910270464, 1732759956630798336, 1734659985412456448, 1746674609693791312, 1756403854674493440, 1774662613233201404, 1807523999859234133, 1821900649255257884, 1827460725372793621, 1859858364918957624, 1892926664126135808, 1902394891012756821, 1908525442087896860, 1945555039024054272, 1945697267895426360, 1965008935905515228, 1996495439887351580, 2010627626232516853, 2022635394332710229, 2049137830453575680, 2049638230412165120, 2049638230412172288, 2070132870748197109, 2092340660533827328, 2099879830214358240, 2115941224926238037, 2118192067142075360, 2124364624229282853, 2169159051180856661, 2188909426382354656, 2210613377707744368, 2210635052893704632, 2211772393128791589, 2222698466103855445, 2261956079511581461, 2328899479591721749, 2330277828560289792, 2362364808991153024, 2364569408024375296, 2382966075534834784, 2410031999812312176, 2436614300497058160, 2453490809775641016, 2462523104680148992, 2486940049921212416, 2529580994364974421, 2601414185216740864, 2613658397298712576, 2627966495540106581, 2644753759187300352, 2680836834976689136, 2690150177415976277, 2695202222945220832, 2711285999788851200, 2741191088059190432, 2760177160997596144, 2780139445657126656, 2789787547378436437, 2810246167479189504, 2853592336519135232, 2918545901843139541, 2963597954805140592, 2986884056619193685, 3015941439348775280, 3032102500813373440, 3080673251353952256, 3083839974066589240, 3105199306122295664, 3186546936343924280, 3219012344402629973, 3235185706281555285, 3238934487564902904, 3265345171778174976, 3315952579340556949, 3317658589693187384, 3321425341312702464, 3334047699155783168, 3392934119267372192, 3419076542104338432, 3428871694150329216, 3458764513820540928, 3465519913261596672, 3468552246955654485, 3469319970824912896, 3484877863064950101, 3493349219387582624, 3508026376487715413, 3510067078501377365, 3512807709348986880, 3549325226466402808, 3579807762420487509, 3643801298510515768, 3680236214663461525, 3719716729837915248, 3746494474742661120, 3785853328252271616, 3794371491547461632, 3817050884175793720, 3891110078048108544, 3891394535790852720, 3930017871811030456, 3992990879774703160, 4035225266123964416, 4085775042784613717, 4098275660907151360, 4099276460824330240, 4099276460824344576, 4132427958081377621, 4159036871208686933, 4175235456277989120, 4184681321067654656, 4199759660428716480, 4236384134284150720, 4377818852764709312, 4381994618443530240, 4388440593388311893, 4421226755415488736, 4421270105787409264, 4480326084928790528, 4603679374753923072, 4625759961099883861, 4660555657120579584, 4683963517819573589, 4732433635288537077, 4779820404515886421, 4820063999624624352, 4852778559422332928, 4858401731347354357, 4873228600994116320, 4906981619551282032, 4973880099842424832, 4976487884539781077, 5117344867010565461, 5153975781222602069, 5202828370433481728, 5227316794597425152, 5233421030907691008, 5262039564731573120, 5265100617752066048, 5289507518374600704, 5323987839699604213, 5325084102557171712, 5369711643630731264, 5416439104528045397, 5422571999577702400, 5464367547876201813, 5465701947765773653, 5482382176118380864, 5520354321995192288, 5560278891314253312, 5620492334958379008, 5707184673038270464, 5725576326263690581, 5824880658282971136, 5895026807716545685, 5927195909610281184, 5937245508750103893, 5989486319662054741, 6031882878697550560, 6067906182998130688, 6161346502707904512, 6198641937122066432, 6210398612244591328, 6257351240948004864, 6347823674778714112, 6373093872687848560, 6477868975129805808, 6507477153542569984, 6530690343556349952, 6582660890082467840, 6635317179386374768, 6642850682625404928, 6668095398311566336, 6785868238534744384, 6838153084208676864, 6857743388300658432, 6917529027641081856, 6922080351524988672, 6931039826523193344, 6938639941649825792, 6944550625405304832, 6986698438775165248, 7025615418697973760, 7045631417041842624, 7098650452932805616, 7287602597021031536, 7439433459675830496, 7464731826809671616, 7492988949485322240, 7571706656504543232, 7583164540460728320, 7588742983094923264, 7676017300515848192, 7730963671833903104, 7782220156096217088, 7782789071581705440, 7883899486620319744, 7985981759549406320, 8070450532247928832, 8124658656792068096, 8196551321814302720, 8198552921648660480, 8198552921648689152, 8350470912555978240, 8369362642135309312, 8399519320857432960, 8755637705529418624, 8763989236887060480, 8842453510830977472, 8842540211574818528, 8905868263125155840, 8960652169857581056, 8984229479493082112, 9207358749507846144, 9223372036854775808, 9241577332390403072, 9277415232383221760, 9321111314241159168, 9331458427911667712, 9640127999249248704, 9655717601082343424, 9657037033207889920, 9705557118844665856, 9735781594457818880, 9746457201988232640, 9813963239102564064, 9947857738021670848, 10039708329799319552, 10247940952081563648, 10248191152060858368, 10405656740866963456, 10454633589194850304, 10466842061815382016, 10524079129463146240, 10530201235504132096, 10579015036749201408, 10650168205114343424, 10739423287261462528, 11040708643990384576, 11096619274226106368, 11120557782628506624, 11240984669916758016, 11310989764993770368, 11414369346076540928, 11463535079319171072, 11525211724231737344, 11649761316565942272, 11840082552308621312, 11854391819220562368, 11855922345730808832, 11885914088133361664, 11908227858670141440, 12135812365996261376, 12257325128353841152, 12322693005415809024, 12352047657328778240, 12397283874244132864, 12477110613626060800, 12514702481896009728, 12682136550675316736, 12684412212617270144, 12695647349557428224, 12746187745375697120, 12955737950259611616, 13014954307085139968, 13061380687112699904, 13088853872771727360, 13165321780164935680, 13270634358772749536, 13285701365250809856, 13676306168417353728, 13715486776601316864, 13835058055282163712, 13844160703049977344, 13862079653046386688, 13877279883299651584, 13889101250810609664, 14051230837395947520, 14051890553458720768, 14091262834083685248, 14197300905865611232, 14243226201754435584, 14339461213547659264, 14347342512895557632, 14347467612885204992, 14575205194042063072, 14771681673967828992, 14878866919351660992, 14929463653619343232, 14955139576514361344, 14985977898970644480, 15143413313009086464, 15151333209720180224, 15166329080921456640, 15177485966189846528, 15352034601031696384, 15399395865519164928, 15461927343667806208, 15564440312192434176, 15565578143163410880, 15767798973240639488, 15971963519098812640, 16140901064495857664, 16249317313584136192, 16344985137731993600, 16393102643628605440, 16397043293302554624, 16397105843297320960, 16397105843297378304, 16609212873838690304, 16700941825111956480, 16799038641714865920, 16923069969614358272, 17176728978791071744, 17395864605720772608, 17421893683506053120, 17527978473774120960, 17684907021661954944, 17685080423149637056, 17811736526250311680, 17921304339715162112, 17934318878607802368, 17968458958986164224, 18190531476158676992, 18318637774934114304, 18382690924321832960, 18414717499015692288,

짝수를 먼저 판별할 것인지, 3으로 나누는것을 먼저 판별할 것인지,

결국은 1스레드에서 돌아가기 때문에 dfs 모양으로 탐색될 것이다. 먼저 판별하는 곳으로 들어갈 텐데, 스레드를 늘려야 하고, 판별을 어떻게 할지, 트리를 어떻게 탐색할지 고민해야 한다.