Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

Этюд для программиста.
Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
Найти a(1),...,a(7).

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>Этюд для программиста.
V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>Найти a(1),...,a(7).

С использованием "длинной" математики или без?

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>Этюд для программиста.
V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>Найти a(1),...,a(7).

a(1) [2^10] = 1024
a(2) [2^53] = 9007199254740992
a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104
a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272

вот пока что успел просчитать...

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>Этюд для программиста.
V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>Найти a(1),...,a(7).

S>a(1) [2^10] = 1024
S>a(2) [2^53] = 9007199254740992
S>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104
S>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272

S>вот пока что успел просчитать...


a(5) [2^1491] = 685051994344414819289601327349235507686015935162711500470230430
17169851270631488679017736106611268089166309388272338901170497165901308515144865
31038672793134353507126040839309470078654606145106745445739128933326064717862942
37233252448898816197557825091114307651395358115415022917209577261642767771202747
54519441816831362983266849142056649908740853890886083405397212467377035143021587
233073571308500000341901085017693125848012770286553757194752360448


a(6) [2^1492] = 1370103988688829638579202654698471015372031870325423000940460860
34339702541262977358035472213222536178332618776544677802340994331802617030289730
62077345586268707014252081678618940157309212290213490891478257866652129435725884
74466504897797632395115650182228615302790716230830045834419154523285535542405495
09038883633662725966533698284113299817481707781772166810794424934754070286043174
466147142617000000683802170035386251696025540573107514389504720896

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Seon, Вы писали:

S>>Здравствуйте, vadimcher, Вы писали:

V>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>>Этюд для программиста.
V>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>>Найти a(1),...,a(7).

S>>a(1) [2^10] = 1024
S>>a(2) [2^53] = 9007199254740992
S>>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104
S>>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272

S>>вот пока что успел просчитать...


S>a(5) [2^1491] = 685051994344414819289601327349235507686015935162711500470230430
S>17169851270631488679017736106611268089166309388272338901170497165901308515144865
S>31038672793134353507126040839309470078654606145106745445739128933326064717862942
S>37233252448898816197557825091114307651395358115415022917209577261642767771202747
S>54519441816831362983266849142056649908740853890886083405397212467377035143021587
S>233073571308500000341901085017693125848012770286553757194752360448


S>a(6) [2^1492] = 1370103988688829638579202654698471015372031870325423000940460860
S>34339702541262977358035472213222536178332618776544677802340994331802617030289730
S>62077345586268707014252081678618940157309212290213490891478257866652129435725884
S>74466504897797632395115650182228615302790716230830045834419154523285535542405495
S>09038883633662725966533698284113299817481707781772166810794424934754070286043174
S>466147142617000000683802170035386251696025540573107514389504720896


Предположительно следующее число должно быть до 2^16380 ... ??? прога досчитала пока что до 7000

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Seon, Вы писали:

S>>Здравствуйте, Seon, Вы писали:

S>>>Здравствуйте, vadimcher, Вы писали:

V>>>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>>>Этюд для программиста.
V>>>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>>>Найти a(1),...,a(7).

S>>>a(1) [2^10] = 1024
S>>>a(2) [2^53] = 9007199254740992
S>>>a(3) [2^242] = 7067388259113537318333190002971674063309935587502475832486424805170479104
S>>>a(4) [2^377] = 307828173409331868845930000782371982852185463050511302093346042220669701339821957901673955116288403443801781174272

S>>>вот пока что успел просчитать...


S>>a(5) [2^1491] = 685051994344414819289601327349235507686015935162711500470230430
S>>17169851270631488679017736106611268089166309388272338901170497165901308515144865
S>>31038672793134353507126040839309470078654606145106745445739128933326064717862942
S>>37233252448898816197557825091114307651395358115415022917209577261642767771202747
S>>54519441816831362983266849142056649908740853890886083405397212467377035143021587
S>>233073571308500000341901085017693125848012770286553757194752360448


S>>a(6) [2^1492] = 1370103988688829638579202654698471015372031870325423000940460860
S>>34339702541262977358035472213222536178332618776544677802340994331802617030289730
S>>62077345586268707014252081678618940157309212290213490891478257866652129435725884
S>>74466504897797632395115650182228615302790716230830045834419154523285535542405495
S>>09038883633662725966533698284113299817481707781772166810794424934754070286043174
S>>466147142617000000683802170035386251696025540573107514389504720896


S>Предположительно следующее число должно быть до 2^16380 ... ??? прога досчитала пока что до 7000

ЕЕЕСТТЬЬЬ!!!!!!! Нашолсо!!!

a(7) [2^6801] = 201836873730874603496067078704951742793271571467796357102595
63287899142446307449396553194376649549544732189805453964941287117332349807961845
96898709408220563882064198527460107522879819440838558686377575813024966104312440
40472053699794021012450900678592159202221067186018047489680554937424241508712624
33034724433154210959239966119613875688017101973957888567620067154231849972166639
59935738965349992022396029669476515909241032357927107773201668849648641513488181
28121205970900852387794365773285613104276333767014551707236799842614244090868138
82789134901238252835879089500000007784845918211269876585199886468773537067916422
55363794208429618031522790966763352630862216045390677455403997741887757819822545
36179073980292378702921519952169721534896399382438243624599995559220773507782863
57407766107793804592897320742792492416740896009983541060820246839826616223053856
18725457038911592602490298629776977230236880196255981756304400152189092409917670
63637206206142133371517905248972371848199178904029181997615380773873319531937795
37420090512597084968049368790217593123843433853633480876353176069425237997545227
48363067328093980965170154587917064165748691133914573471242449819558571165600837
22808170828653631246601044196566973412839611008060079204838775879979315996716284
39148801310673164340829308511104223422136544209138120755491804122181842958700452
63903594959985540352748924356931540912889423675422225013358375870739791856320272
07406851917856357718967853749880064245078036414369677587722694034263142119385177
47337101117944085336648858912750540490583941341768853329676606213106781004672766
47853690600834991591180467771692374905527010384973782874030002217253098383774586
45395269029802127818256217492473685467008121796090793979868062532342326656709441
56564848878452893940866500287080012514525229194434984840878537328561392666125392
56584609329469478143847118157468341549543546016378221618728937408483247576125814
20865579955645654575584326885619372827808775026733088186692740211957894903835943
60483708898503857927341665254697222189001784070888784966164259274752

продолжаем считать, ищем а(8) !!!

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>Этюд для программиста.
V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>Найти a(1),...,a(7).

Решение на Haskell.

import Data.List
zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]

Ответ:

*Main> zeros 1
10
*Main> zeros 2
53
*Main> zeros 3
242
*Main> zeros 4
377
*Main> zeros 5
1491
*Main> zeros 6
1492
*Main> zeros 7  -- 5 сек.
6801
*Main> zeros 8  -- 25 сек.
14007

zeros 9 считает уже 7 минут
Не дождался — написал, то что есть

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>Этюд для программиста.
V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>Найти a(1),...,a(7).

А>Решение на Haskell.
А>

А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>

А>Ответ:

А>

А>*Main> zeros 1
А>10
А>*Main> zeros 2
А>53
А>*Main> zeros 3
А>242
А>*Main> zeros 4
А>377
А>*Main> zeros 5
А>1491
А>*Main> zeros 6
А>1492
А>*Main> zeros 7  -- 5 сек.
А>6801
А>*Main> zeros 8  -- 25 сек.
А>14007
А>

А>zeros 9 считает уже 7 минут
А>Не дождался — написал, то что есть

От блин.... быстро!
Я а(8) считаю уже час, только до 11000 дошел
Что за кирпич?

Здравствуйте, Seon, Вы писали:

Аноним — это я Че-то не залогинился.

S>От блин.... быстро!
S>Я а(8) считаю уже час, только до 11000 дошел

Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
А вот девятку до сих пор считает

S>Что за кирпич?
Это вопрос? Или утверждение?

А почему у Вас медленно? Что за язык?

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, Seon, Вы писали:

B>Аноним — это я Че-то не залогинился.

S>>От блин.... быстро!
S>>Я а(8) считаю уже час, только до 11000 дошел

B>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
B>А вот девятку до сих пор считает

S>>Что за кирпич?
B>Это вопрос? Или утверждение?

я спрашиваю проц какой?

B>А почему у Вас медленно? Что за язык?

C++

самодельная математика...

Здравствуйте, Seon, Вы писали:

S>я спрашиваю проц какой?

Старенький — Celeron 1,7 Гц

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vadimcher, Вы писали:

V>>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>>Этюд для программиста.
V>>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>>Найти a(1),...,a(7).

А>Решение на Haskell.
А>

А>import Data.List
А>zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]
А>

Блин...
завожу ваш пример в GHC, а мне выдает:

<interactive>:1:8: parse error on input `='
Prelude Data.List>

что это?

.... я его тока поставил. еще не шуруплю...

Здравствуйте, Seon, Вы писали:

S>Блин...
S>завожу ваш пример в GHC, а мне выдает:

S><interactive>:1:8: parse error on input `='
S>Prelude Data.List>

S>что это?

S>.... я его тока поставил. еще не шуруплю...

В ghci надо let добавить:
let zeros n = head [p | p <- [1..], (replicate n '0') `isInfixOf` (show $ 2^p)]

Здравствуйте, Beam, Вы писали:

B>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
B>А вот девятку до сих пор считает

Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц
Просчиталось достаточно быстро — около 13 минут

2^100823 содержит 9 нулей подряд
т.е. a(9) = 100823

Само число содержит более 30 тыс. цифр

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, Beam, Вы писали:

B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
B>>А вот девятку до сих пор считает

B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц
B>Просчиталось достаточно быстро — около 13 минут

B>2^100823 содержит 9 нулей подряд
B>т.е. a(9) = 100823

B>Само число содержит более 30 тыс. цифр

Моя прога посчитала а(8)
a(8) [2^14007] = 000033662724701763990788983568556041232924515475860246167482253
21619179440438646293915455822251957083168790275365058169103299047907279931869666
62377093412572648398352429291109496691741373642434693114609921276964706431437563
17740303484788330486266539622312618771291197421437578049234416261281431991948830
90179741345388466047083662146412684123197874626588783927450887432153639999725945
49378169730314908238265400304811308972022575532573583203776926224230466012278511
74984677774147733075916511439807221461359073816036944080183143324847649511019232
96984635532851895777542519415279887128451873722760920519590845741185967486448382
59820645499314214542369733390812009307673613200659560870763343764286818531635193
82405838588997257168342124111344349677799408957534228984890299453466158953777838
40097924417252643116512471362377442057882828953674081984516353623425224379037319
13158314106869765895203582571206420678735081975763088958817692576966922251433271
31149841861548806993656297661306254830666217985043374972571796007600033509695004
39530897238474774879513048709933824255644828908475535692390574185596520249563832
09672073543818563332071480348421085357778839875754077257992237903661156295049490
24423462714994678260166485662451281221484552628252933912156726887458639863215683
82689290803885558818429029691941206128130176681760557330308529389627853758142576
76382545605570175109866401680631746354382943764908578351235377904957117321240100
56634769360287434968435338525887286530241719991993677640545050902862773629843050
95825561795016780443117510377279218584320194755363314101420901307541167436708016
09430543302734343868858891379843570280291787641988083391041239145188428252390476
85299015379737305590546615370477003685843342861156832472323600913789940912832878
85566016456534465182459126518592693119644449085012256355113681854264441459954678
50894281995833458889586853196617094216560260672386018619055624022053207139330516
88627769755037093026916953693267238918393033938985982357071756801119765376591242
11458455114130417834512133851069724865020582695692939047342977887797639127211802
25093019437706455451364423326669224665482810369799756807523222571769398102563264
87666682763778229161999263320804088315131882440538666479961425423827165774903408
23581048791287094226656961100195042382947186191288972095842951941087700552509226
31395517758764602447212753017608500017966084109115460944900327527614098144077656
58771749968396527679993450494147364364603568492311170846895897147218139840357700
74466931864136217286041866608188000843078788274891853988171934613966449874151195
02842958034297094514467899500965183464661796159370287393574846968144253223362396
12113923325330847946073081496234993152251179378322007361257399204233807479430257
08245441473989918889084601651220873221522680115812077735603902062828357877004675
91128228637730175174058379844803659249317442480204561241926853901464468362217164
48171545043163082341788465622588806031561851549790414734688672506572506600413342
63976080502482068631084389281309416243864766635698025192159399567304996489940951
90275056743308946961671112860428556721479556486184443505975896750889095178318114
21977577331766136251206312579842703668727259377103704759588652882668040880064429
86344266907053894560793929690067357517861646226248747301028658965934924293208414
47741855589902056920020218026296531345015993803782073779255370903736253099308594
00469941205004292010189639672282673042889881215331609558146147924611385253494236
47367861213759899269886939055194622171075693421784203287916603000000003213966087
57682208184786718550580089193781283154953812210416368242984614472126184380298716
88290111756639496292102403593157001971051780815372615256408750384074488193256513
38373692432796996667155150254054735193086518231855207667453906821302360953782673
22244483246613674879928197501396293251605674916319891085983406510940406816471127
58495276169917416450646758457660169005035016907184258672323521733858132349377243
75296476337758834631167125502249848717287052323868823727498857925543131093451510
97470435550431445278068017349964361161246846150796218579004669892183711597629126
44942617389369626802994855326768788247937341632109249492575848180947430156437831
245815185340839376921637308770763013748956540802880891289897190564060230320128

ХеХ!

Мдя до 100000 это неделя, не меньше...

Здравствуйте, Seon, Вы писали:

S>Моя прога посчитала а(8)

Поздравляю

S>Мдя до 100000 это неделя, не меньше...

Может попробовать готовые библиотеки использовать?
Надо всего-то — работа с большими числами и поиск подстроки.
Уверен, что такие библиотеки для си есть.

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, Beam, Вы писали:

B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
B>>А вот девятку до сих пор считает

B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц
B>Просчиталось достаточно быстро — около 13 минут

B>2^100823 содержит 9 нулей подряд
B>т.е. a(9) = 100823

B>Само число содержит более 30 тыс. цифр

А можно подкорректировать Вашу программу, чтобы писало текущее значение степени, ну типа как

std::cout << p << "\r";

???

Здравствуйте, vadimcher, Вы писали:

V>Докажите, что для любого k найдется такое число n, что в [i]десятичной[i] записи числа 2^n, встречается k нулей подряд.

V>Этюд для программиста.
V>Обозначим минимальное такое n как a(k). Например, a(1)=10, т.к. 2^10=1024 -- минимальная степень двойки, содержащая один ноль (подряд? ). a(2)=53, т.к. 2^53=9007199254740992 -- минимальная степень двойки, содержащая два нуля подряд. Ну и т.д.
V>Найти a(1),...,a(7).

Обратная задача

Найти все числа, степени двойки, для которых не будет повторяться 2х нулей подряд !!
Существует ли предел, степени, больше которой 2 нуля подряд не повторяются?

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, Seon, Вы писали:

S>>Моя прога посчитала а(8)

B>Поздравляю

S>>Мдя до 100000 это неделя, не меньше...

B>Может попробовать готовые библиотеки использовать?
B>Надо всего-то — работа с большими числами и поиск подстроки.
B>Уверен, что такие библиотеки для си есть.

Та тут можно проще сделать... думаю хаскел так и работает...
берем сразу десятичное число в строковом виде и удваиваем его, и проверяем нули!
это будет на несколько порядков быстрее...

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, Beam, Вы писали:

B>>Да это еще не быстро. После компиляции вместо 25 сек. получил около 12 сек.
B>>А вот девятку до сих пор считает

B>Откомпилировал с -O2, перезапустил на Core 2 duo 2,66 ГГц
B>Просчиталось достаточно быстро — около 13 минут

B>2^100823 содержит 9 нулей подряд
B>т.е. a(9) = 100823

B>Само число содержит более 30 тыс. цифр


Вот это число:
a(9) [2^100823] = 00000055879540930067078422327851837042530966116054800134702688
41531165354249691066749470220417094225054610947409690191397767467944539216528613
60490423936108980038523632746621405629468590257489810381244296371170163628559434
61516957475008371824333109231732637641151956046535035629140674342282097000864089
85724076969719785461519381183607314969542437423703291663136408241484749520614832
77739091220250954466768269671729318742809395471840724208254907723886310417839792
18984776896249003279151002164644487834098119065895324447891411285577726441479320
07080563879567160958513392549663832955087734073911017445769747780775477506158838
96783030326791107659503992342898808704648031964568004596527219990246575915584306
98763468956731290430457003020578677610437142662086255198813391739718975530484527
20397708520786402659707979234837333950899206687785845218835941694733241202937881
51097451245048770952853681570458885548655647530999829976293624581478248911606675
87221768675125966104322794301048127809463808979699840525114583361202210505980632
25285787430609826098636965386513045060718042339014773342787743116618274161350467
61610026032015953001886253787819756036872679802044371753833406184416856101477041
25225342823822257382311482284659148363527069567161575415889915357600827021746456
68282152108465919376275368944121894177854682456441835613925982844606724307036016
77772926326468173497169309232389097504751318745431892153261678448017520421292074
96012541997374250964923876119772147314341288284431351872211172110719638997288500
47228486438160866920979136949075392679777528267483521795584340871077431756714340
87529064916837513834584359730272996376098753229300829331946149055623692923617172
46801621069690030608001281731145856518991607416801988755685525831247092343395763
26948673729341740479958596330345654486989627695717372549526503903681518849476544
79170567064520364229371512333228947885229861102445947523416787548917769922882933
18750727135402864475822435271128831613857796479788998728638426778769938942452805
77283087131264709467926406474574880763932709367306197278539868652989544158223392
50776750450324092953251250888643722524655542688125012686294685078152391598943962
91691112225626827187938301316053686594713675117576081992173193719736469839228697
71024049561905220167524635100946347330947040881552714669224069434309188611272998
56537040271948085118397761825675828095586062206228764583234828544267864734821961
24063705343092299649326999558066129893768871984498510057819554301599303383010188
04357879879068461472706869407892414812566404773602892688873553591576708604654076
87072648198781813529534290933461426941564296522438433373596056440724346383374904
42075796892342391902685162518409260921655745799945763130472423325370480098860661
39138187807160466266487298859482076320703223544818722672394805899279081736177853
73520323899035823171638984851111206660983687902327013480940548818218458057881041
19990893998016796361014094225799121528741371787423632192109729862337214365036869
52528327935613576996590868158680906097097155433610319283746161006680227328011103
28647690233607751763686571013444709535721665803915086260404124862850734650087287
94703540775768977594314460262833619421265728398973454500978189899035108614054083
81449790787311072206507000201628801862471819173045967796956760077461490160537267
62679746111209665960627579451670248383276303060304697199584007811384228561104599
82159435827438942221724066897215475507212041765288803306140189172367008901744540
66556220403373229198744732862297809140893237727733516735734743459334110535360676
32005530913619279230639057600560888863644115731010761677729821840964530253758209
80295331503332688010781698765224228624854739534877682888096451413418878638117725
62354095951170109213686697265274924539879165049319334448786716181622864311070757
32336449229730865777748185427883519692579017494033965416193748194234130244042562
86420914358851633688869422808074078320628142167946114561149746043334692693231508
68187968046000908702317547703714332712585878367482741980254982938244773492712082
30315451246150008826744680670941913847239246083347285934976090683158850105389347
09021934112300693033943692616455423867252912510200380935820605828587640660685847
57104150091390221653526258281651043584938053065384050073227423939855306476223768
16840799111148945085819397334252042774524152244449486331344338598935786250253799
06834747661519313756357864010535422239668841058737351568504503547056182312757022
14136512433441879531961700861231648542101597602690417702446911467553652183978973
52739423851521661072645566395699781033902316164988624587446968168739927476815799
82082770414112247461368222765362643299388091763200868889247915197886395222192688
43640158419483312089577791375670777621205221251015838299272244846531060692190430
85286300560984085036257254086024733969723374320374785339076009807445375684545593
11017868365782564077386289185848717926458487095961351007944388853791403869401773
76977726367452359527845934120011962482126668849305827096760996654759437383478319
38121342175729822215459366242562178282759502733296540090244860552586311034211270
43104203948140680951105734627353501899893028405160864174683747464423948010389965
99275053082804239969832330191025444223071533403686937413325218929299810099936477
53213858201634317058435811286388768915240261040453117539268729663735125983269406
31453224948876687194831777236358300692721846663574149187433242264049965227182385
15124933301515292341627445956246328886678973890348168738652587141135510026372797
63334368781076580191625332919057073766590674416073111751651265129751534683349314
14813969420443019603972556336386328316842339852504331502485548142714287078622885
31938390589726068301639382541125254427434149412493962312573389051802513147141663
43527607945564101313346072456391967896165621830072107382710452959809641661338426
23922637364377396807279453158657327005363882135134097032524863234985558386331146
43043083682350496534548078062613388883047118431599824606702749556845524167492796
90216698229558873882624738521701835552789300586730176380709729484106777705900733
60159614170437013168531475812319117565433718403633805373994451223260997399680999
39103030744776491983991247610814319976679348252956045570014650452526420442157652
43335269657311749518352124484353325675835607287293525381790503039605962640270212
22979978257549783115760628953373298435164344834883242210552346182618810212832025
09340384600274428353166015389023985245468345728677715888458264113412753116552877
44033505687414604038798046584929244688507833486436060019478830140438610907519252
65371060371628390069936240607691081250070779108039277097479843130650581975472043
08412939586022217703247835359371572823790911166015025723275112774368302356267271
18136109663388321469565354016197475325256247145356175601729184896269825633916775
11225181192013500836188219614484269518424157765762901465911023145885530371146195
39925460921390668213062974365767618123443563874739610431327551298991173498575216
03664657265389227571229230994867617349972949559292928284485826092642237109874914
52280727206032957944576266326460394844242780023192105631136228573204054498005713
79815674258838527729100152804149328296128975104639840992545490847923671140032446
42476423785650004326021745126297133695530472597704295439682920387049970440692458
34536409220384029167005334558632487549683165848767954657168810372722484024197728
94266359275317765201958646342587489766350173810818392216487401998972554609014393
04576960339693565959518568128606215173555794076836891742777310538150658655685306
00773473597943490082253302173120257656736312169905663516971387562001846889565630
94247890538836188534365791103563875515918659395092080736112089580699503093860319
31670921820442524864841271485267197566597927634423244906855604914398608433230745
92174829241116631609011017179363594446272967649525188727000178698974217587856201
23724625948177989250297576660928180436499945896487139693826406041101835616146219
62123406469340513372610854978643264085885925549181184387239130012820254841313582
90498882701620085830637971626798808315621744270812998921446454992430116972835284
14211037923376688793812489441496383504654021879748059647967340781919829401884277
07578644412647684161093808261554347479713510724936082214893100681970131910872947
00098973064588622501278573728038722021846068875397842948278275652350007346978165
64403846455557121382866765451090746103081743640967405570391350888349352955901906
61460514725948600015595792537809659037503381656989834888900686035208515539554797
88680547227622760886601464543536085145246336186163097426754109021790246556468726
52626825973213309652963652570526170357252126107085261694232874937807593527608758
73114700803492853788698475382016976448297115424304374623720826968649573955269948
13629731531372055989132095969110696959775352692685911631742898242981563252507495
97896039089404219535290528814308329697756464909192478863532829013735900119212377
78641590935540040747999764169334346745564169624674964223357990694303001455194232
89124814819905795263207813034064568370904968125810665948488168049619452914580020
86051529759651304734023219917798514709808222291588297118092734704459803472643317
24382873339019698297306082999033296835068415491361982897465291865058750535497171
36552158502232307301882637110867968269501707794127780819257643650425539200947856
25474831637633201568582468156788691177771032616703653163859032967348337787455192
92467693639768497443720910420192259215053477568566648174011298676303469997867367
45626709054558037349154761621853777481926627317352500302389063204942748341547855
09156372774355379646104759677883389956230775175163365500622144666158511307787136
81719388222115984992245009541567925792946980693522807119135921266129581478072624
60704708026381875778972378746843427954041379169267501225631395418447713606377266
73687774375297399703385248601702498401113358402307696649869872034790183336341859
76622381396908248432125023198968141602797711370613260346810575045283623023423218
26282960069008601816286835406377116868992773356219525764624979104712469918876106
70372665433042603193704135349982214620383575659928396256528724667828944096188654
54924002236767470598676307389874674965236363081325313504665571880007965639352538
32120989386311273480290016349046967110152276449784751283841182728451200440395248
66970912525263766398574544305301945378441280174046904984450525895331921965180113
09801024928899838610396765187179327640633584443225222256535197946118332678512956
95645300437337157878308256548493241590587744055778302609854638075538660570195292
14759534698615764038181515591346296788869394784568027427424543744771496273798512
67303516177067623773840709018463037768039644607216698173851407892881674942195527
88069317744266796232814626212894315851916710428976252448241246235459595660302412
41466813274264089467282025887511394511333252463631305799922404941909746066188590
98354481674457834615845143320197338398273124429978253476080394316070657490479597
71777154309541390885423475908747841928902666579780062202750301323890592090692224
36664814663267448659742634541469832362082381688508215899269018589764340388809022
86167554467161660109509326151258434916915362633382377515777183009035128677312082
49804853956317389016894278841271204441634243342232652519116926051399641998683621
37022893205008338453148370541983264069086403359048325382564831622870982871949042
69574538484534575952909816849480883901499228307406834340811670318783593828840292
46813529459099673637522068996866256373130627346790386247448216342293438817534291
54922264094433605161186832589085149048799403209380103219601523222103535077853475
01218153077770866995757399127622406014642374267705422104922969339885722776118723
75792118097951387154125588172587411307596905026866283781696193665438771028685234
63799000400225789708715876929590702047656944025749499652662438139090243246480481
88901850279625062973773279736804280868719505098363196975313514885775461376075788
35909223533635847714511988275030657700452923447786493926013374003323290303989908
90272580344005591113783499849602487008695983102113561425837675624456323224035630
08423550832870562448548569511821077754921363120394252640492001305556660464271929
57446342893787304534974032073725706939038266820310965248948356629413049640219282
02804616132131859599206943549487029285649974604250768866892495065945630493467820
21840256544769677493002145488605195990438075583791196081858884529930336719912391
87684613563191298002734051532308454837070649488313036367067759512150362304793479
97247393684742620446700527737378009252695001383058150118618629838883848315452115
81435710744921192518559800987552759189069734615753428282368511724784793444225647
51913863291782980784853397044484545045666143875021620474014593262661772424690441
58723220772566962725364550119899667087585810337127305615244673854418969069205712
19069056466080765674992746748514583583875051640461025915763535303725904310846482
08405042280470768861850625414896364496868635449842571298091387662544543277767632
39442500199835029114874935376968788307832393062432492354436677616452693458157311
91149947397074763152145391139522037653074901978698564903755591550073270499042781
66938124048600904762533730272617792267133339916182052934909058739508839126439445
34711933148592544838041439842907400466664607625479193557732190640606722947337921
30371823934618525606909798264604561784410869637124840370588309952755482585816211
69189353039127718596837505998131204668986530615581596169366226080659218506421055
51414859278420937411856212371748648551772454287644039208775890472675618293969459
25318284080961989806623478729950952666504579417726381667871519773932893495929105
55274661596180092484046598676227493800282269375512405401336036358327996112099795
72251546575258812191631347662300608755718313525103282560213199861009851683413438
19824429991639970416300232676729128263993713223767078112276671140499159577785889
43050619108303527135310002147629264700963665635222974208733617748680654117449897
70243725622148086168722136956032705282691838186823219841541040505008173328681936
36998350016844240067472628872108409976993791329240429378254258021031781806791694
53784447936943316890280469552855806322011480429987304559538298774770768757915242
93231899414193804672619652569703246323932157853441544849234689636956995265514755
35489617332913898094299651039824548817855517094936379474213185112564855986278295
62352363109236688906035976730562107048233548917234786684090978213342314174877537
26134615736120626117112216247374737066048025823885892623336976797974543136393754
62380792472035960913951230562231576794502894865936542465387079044974463369878942
36131208316856952522421124887649941674747126623444841344830271748934147847474332
00625429469627961558231053660905982574819481674328019070281165908962096366828833
16359018153672746783846273654352464404261736012354039024145136209379077340033619
66754529125642391664109307536277684766310595819192454233362980690310965011725817
31854090046226148465347009778186080320346562527072086823017105379433497598183945
80414965641189981672911809614496884637329490867579022434560131616329914286131926
94709864301117207505043056443517950888174815099714170365511604942275313251346775
85916642800497191606313659073271860538098326537630618539938613680254360405896951
68591740556050661584257552740807974025231089693202871297435449522659505741612335
79798652777544063301929718222418580068585354400576385284506436678285276553087711
02503880817768167162863833038339911056337759002201531564365446589677398746728223
37967955860909013307082636027732996298649559027643257389703278234597880640735603
66008021206067489320334340919314033327282092414203072225957120424767476733087579
14775246630923840720263490008313423863996944870005107268670241104797898190915877
24602794409390610387717530268727496940563759741711564467137973198885634262894658
29500376434566612062621873056042395126259461488260000266841804573397051862966922
98434073959808933786428827744767173447503757005439590141662748483205327310396224
30397480501774116290822135569965213697476041184484225900415592672059371231453080
11454366303956730776901986468638284406645438781636531196503967859770987356304433
53599451617948707356142026389567529276626856797069771080493400818148841456670718
68896995971383499729263114770149262814156575929213363428089427678534787326522954
94188764350046626847136709842964674101202176101060586273322797469335759024005955
44873367423497439397828680956208467722147301986814067711998984470573545418383489
58011318945481575232060056767329014156639560810763390338451752564797918438760824
66019059273619499485788546915263149919739352212444496082484958583511047485539041
29670208133984292302192014381540241877744851912270616371743910958660007841022168
87585108006498518494643303489248493815621288279803197212840906557674186751471802
68334981673632514894910671026021508027890489037441536373385518970337937269584986
26782760721140784276705111733790080305276937132537486952695389768708934448117782
73019125371045063713416304482037795356073809793714420289251166301194309143574583
45432599757821942759139232062974882973816379801773338247216269465280123329172969
06169386484629460294353930461487065140707310194195035854976389407422629082616649
70074599758580758331758768043615519255206321201987384092372450725506029231615607
60091084548374579401335898236576730027754974249042975201843631003175525876441756
90173749217682733596445846829621725308152170932226454876309606190507830368985009
42641245189698923591353826902780793945358202482743943387525652026403154025401798
34447642402668337261943738706094698348789138859858713898090636078414775145124504
17771153831844713166057226208560098904825480360965795847046203246406542990875743
43957914398552935834340669912090156667018189997715583021811150125421221222996413
04886269280942616806324600409557398687785473638259650982395272708334124382333597
10250116320087686591887915045236970717059907169208577040678098107056357194961807
59866074484091426269231397088993950412414565089542564207375562647292630781718091
71684240737851256506890461399307488630931148652809825135031536200398459145235676
62884672697339814048478443973117143913592586216743845712493646076924918167017377
02704352939392814793755355857728216315026693935904132456486947383355248921753660
58100348062911825083045946093277841198442730970203559739501331005131960267272253
61643566548412857611332222325981860542099381686594056282829570652253230059376340
37757210316681081544436260248237409873758056755228408500261416825498962753082379
62833871126074756523387263004224599550172767779033920757276855802409968821004712
48944537436993179318372323871795165588130247945503084536325390096336399312197560
60783101453273338236463093855319390080256043286241625052784344740078769973633788
30114122335056709029129307040689607532367070881682939603267488895262917887742294
50737391687568960370956158559131345541045381855450383568525576864172552710827035
98185052253082620315349136169907950835432583946153848607808795678238767227875833
44008885866560810339385053232854285695911090061361622582611061122141460844074170
22941935571417584724023727750362162856340833452644849712768135518733877488709674
55713965046825192785519248956078766613694936053898780231294060204406770074298879
14463579773378362966339322505562962670908360558492194445819379035505497212818378
39620642866813314131145279252707011892762907711414321780594450769005893194714262
36899822042625127860878084896052174082242340669960516220160821084073371075511645
75142003462371445039188061585811963695871544620203133368408389884825856388544393
11575458523878669854821292532468431141450122669137458530241060871375404973647916
66688110074828730258695070658682720195483759193240751729244037747361178897254385
40850337037274359687991032996267730937182200413645566385807797796775525113819956
90311272495203158497950565140307659818360834123180006499390051079276024572428372
37234040507392375546501079238382615738999289913738843882283905239084640254417833
31676894229791631831466153508793169840012684905396377448352358280131121731847397
38671094848682967923129363251880410088629431579471731381923423904722150579648146
65923667426951789233453780661857141076727621789156342707156593543269155609317301
39197229453001413384779468905931504832133955427742916491569430321597195434503417
66201251188613379285563302640150716105873546541629185059850915967062103838940188
44684634962080713733833989104978330173906731635030567230656891640293276795775287
82800785466433265275507793531647923818004849954660468196721737101204877378693511
08566345967213642036775180137145751405392894693747612745692086936761369597296700
44675502820221213640165642513390700649600811342192586815072964977935772560860808
44845800869092349381926331313312938267846577368111891970838782040012495869811104
82546393974340281014458444762583068853962025783137619509008551703858486934626138
97899351688012721042470133992613415994613584278286727420433632548349559578778498
51264071649415326605371802227858429833520867856482581433195758692932549520258824
60918562742928340692541256538514608253886696699256468748991908248636001310140220
07670137700839650528536388151654993782567192257449829483096148247351963051920020
37916082291628243209892105251237200128311052927715096516024623308764823757587130
28312735631055423387499617706321650613315759254819872316158039625578161933824020
86608190828273541683281771935102602781688802039147439096612795561149547853432908
30482200741576758812960195318453397843431608733618142748789844979736961977021019
74353225683818794277371380948820157107157529477325519781033779475993760601795062
27367143869387127193558418164277379829591326591183903269609926566775573801954253
35797915215123583635069364233667624294016754197799536833659865194197906368685293
01289144269337429082329659874750574115471576321062569787941229853527393529418283
28322366127467995005168580486175625750743545390364880413573372155108349654590783
40986217074342763959973399037871462533620108311829563526497064023442723872307430
21722988507908537625766150580702503110224492809713322727370100111627213058929692
21465971941383185915242997076301112087822392857549311867549594012816461281850679
44657672379439739494363843592623834538652010057382983245961398738472329771639691
00000000034244507533626934098613499300169757059255749630558108402945405953424635
79872245231280614927808083661198895776426874863506199150914809241898138567694149
27135364555505662331751429601708742946563296974615554429205734831227817289278174
87884757005024102559541707043690575996923407205579821797575196418932551633602134
28348088883972857490874971946664397998179738460575741943137440468963370677258727
12075555625643859043878113056598956210172976319085457120362429321837789643269588
90749140819760140571743546598231659714524851876965689491414005607105876203338094
92671425128088091680426146535505730489315704121789099285457034914232467966213685
68316970318724907180863656068605692606937528733919293045449903443050757480265184
58599632354715864767568843496476624659201446149422241519085723547529411871209350
27769514193771799273259309065922815475544288077093976319109085339153903794984337
50453762850887271965295065860127620185215785627776943937323404723358022150639489
90254464171937787846003980412934044281268207616370943805332901008722384113920029
81821637403230966826736489478273072275048257253371379063006311740837755618278890
62205973535787537918527860896238662972340292850155418700620407109768653309082468
79156424673888626224308608817210441640257409256753435432479889890193472667169180
30619543341722258704454944035104228712496948245246942337490910831628464255743985
03926853078883434116972427716517056624741768666503044593767475970012314097543408
22873529888896217209100187064333805546745069645234768429688563447552641361235035
68046340952775511168480627718593954966152824250436436448088302677006140757903688
59222336157320161485126452494165009557257498211422559620616149036514953835096823
61640027461081510004425304963479947605571472325692665173763576603388522761862541
88189836025583952495651907647345155248681513412510891831801976711213949467952857
21764271851572993609591883561651826582624016515128751023256715294203426720938917
51849246004964932504250093771104291546052911924530630503812732545122024017714790
23044193772136468964948805457336199327823304462555650506353830541418657142716731
01085607327058918755362173998681582656917047648552959202296312204231541151510853
22646636302285534570135231664774833812438826896544824002604078255866823477298543
77539584774597494263267742904272477087565267397623270408962991841567350696052727
36194533473813827363603129577487609755173673505399263132898616020245659437333748
69382323915267953947243148838200402663820795402387670613938334454150730643403144
01626202762484200809046046296781147657002267994656832741967700822096269623702361
95356568293317987905892599850443093034972813936485422278771066552826450747804978
25186025344776573611000295711421455361981686799070159623604161388843759975064177
17876588098042561598769709252288866463663885497653228060067594275672586980729698
16249102506086760546772644413476381726091141854748303510896740232548705391687515
58236948640277861530432232472529221247948449986386804005220994077497081252142789
70703955473845098707334601230337772385998073877862954064827932831856674590984181
13661331751572651963002960291457888647099615390203424518423060351698121799477619
02302463247795759541860835778530285726349114387111772713337059584062714938188613
88652942063372339934359972314934591112847587065277365985585020288735134798110832
46196497946077859193584627036411163977238969101327404001996549697571875229302898
28951516918733284169994302632435690339882045224217422904601116407327052459912538
73811340436046493868950241854331372870038297340706913806982602943376757195495823
57118794845402533534634000629903598331336110895349820433389517854355794138946487
87827908244690710523667757801479971551202841745304279220212123469997546336288818
07241303501863592234782328608460001510696226339822771774263906182426210316201646
06147584738992966917828903049727120113775234577311930177901825463874373870409327
06540016899184053836556923537692195054659076131075342366967688500966366307372359
64561531626356248638651473654932620808068621498763925761669485643629052322750209
09889435461818490993162162558326381259722951411378124395051848093131540128749856
80343277167465557145862900613169390365882813792688094023557716502502426877920609
42469513142186573011018263886961071628172954175866136992855638419199373909804102
29484925428697965994874224342395759816715732457352140971743096370841863327548403
69659401070487121700451194119973832330593134301844566286816038152184689194969767
42750294990087914008615773753082508827092303263955954417422969383596387967397570
97450523552700186435865923629128874206025727135690287457615383845146728270906709
62609690314530598386052144897892286344739853793579446476250839015285276656668916
52995542393693617945410770418025503093859087686374204370377222781631158478587453
52031810664419529491643174389948629608070293239660570583349910920026549245537249
30045609371176320920396582087388210883121982269338969394461953901146881240444564
73226388853353285596154846841135953917179272482587905714883111096347493743250133
17076989805537351400264339402271902291889585679964540885785090523704796178028485
75182725487948467858644190406800743353265876540473841541726138027479842402063881
42303712873885825620054073417439503820601344114692721545953209862722787535565795
73103062545427880085106586412129232357838284449878319924530745694049466266123414
56464292201610630972533089043360640248113140840246819185457032573866631957497917
76786209565765636028123406531012917252358129391251291419015631150136196674528498
88952860666772974976800066405880567171823544904475746421526012085919168418871236
10140536318318064259805982596191271876454368133154909862826942128230967793581680
04699257721806888313394392048089674773491063160843445068300668054905824756279428
43449725392292585520338657240036178862536693026432667489813829772297199352364125
43467935706490961631417226061196351123944065243357418217758182474240463119927637
46595592344825520877451997966292732244526279710910667186096851060182618516906582
04546691809588587779378113660063074161760474882055170316276570369942818317697349
06810071109732366428050276531116525710657293658070159010127262730257749693598759
78919673694237322547681770025494834978615437024877321011337702966596320577169675
21267220639331076619821026710416154106601354496590987653569250019551487115173426
02213497829021416815059456678503481935775551134901174722796972707461511415253234
04929448879573436232253745356544815570462295192271334749523009956490879507336354
65642980745462344665710602677530142850206630300262086703331051614127813983871221
24084512498427368122561696251681964669139496180670564352989282964801635254707749
95302009752952012822440061708476235448766435884168234703991388266740914721692999
98286843328904221509437308721470608792251837271330736548925564652996513568984094
76703051536904451954082157128747503265930835856111671544051685491072449086684885
35956086606663967123679881338137069036684963098682841741974506381167334322718640
91259363670166214859564294747140257474443471359502360210218428463927018950564434
56461564541473705489905830064156392883647792046407297543824577233391999224237476
07663764149684261203895326552885772148236206726296290904982262392935578281162378
37960966480588496211956565717519064414239865765911348243556795157228852875907509
04193968994826660354419395779522237320428801285297296650408890145232582748905436
05649424158931710164139225388564058099712403938194134993437741931277264768326093
51052581834006955518392938484236561750168511227695836514175920678455118076291781
26895419778791296946789754424222998240877133347125980631768068553049925555161336
11097260312564886735043232322239289442807403044417762628287885108847289085516352
14189062921823304003847650402452717418772808062412883054665183076104903410005596
28580886860349238674592462693627188225123531284664528672794881557901284191984382
42516206527166106005572723770155797282801137662592386533678011702895027912630615
12150335016781602354561507841175266897589882431374762568544381039814906906121734
03556711903641666808845712809867560570961909589616718834796667261236828988331652
55762455089919399828243772328550064571498405289693638198605171827347028979557388
39392530713269743765076606959463988271321223893359175113978200816653963834819848
71222217830773952316182037353615141595176710117802928615667467328003970175011860
41348749862883274221516033303982122326217485700544485881117171750773599650720417
98303238594146486449450963679979199662251523726947494978383716235213852992259548
2132074535536718685190028208030449249412006825435332608