41 Відповідь від P.Y. Востаннє редагувалося P.Y. (17.10.2021 16:13:52)

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

koala написав:

Цікаве питання: якщо взяти довгі бінарні числа і запрограмувати двійкові ознаки подільності, то вони обчислюватимуться ж швидше, ніж безпосереднє ділення, правильно? Тобто це не таке вже й непрактичне питання...

До речі, довгий формат необов'язково має бути довгим двійковим — довгі десяткові, наприклад, теж мають своє застосування (напр., у фінансових розрахунках, де кожна копійка рахується, і масова втрата копійок через помилку округлення при перетворенні між двійковими й десятковими може вилитися в збитки). У найпростішому випадку, в ролі десяткового формату можна використати й звичайний рядок, доповнивши його засобами для виконання арифметичних операцій.
Тоді так, скорочена перевірка подільності для десяткової системи справді даватиме оптимізацію порівняно з діленням (як це відбувається і при підрахунках без комп'ютера, для яких ці методи початково й придумали).

Схоже, чим більшу основу має система запису чисел, тим більша вигода від застосування таких методів. Якщо це так, то, можливо, варто подумати про методи перевірки для основи 256 (чи інших степів двійки, з яким безпосередньо оперує довгий двійковий формат, коли число зберігається в пам'яті в вигляді послідовності байтів або слів).

42 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

У десятковій позиційній системі остання цифра квадрату будь-якого цілого числа може бути лише 0, 1, 4, 5, 6, 9 — тобто, це ті цифри, на які закінчуються квадрати одноцифрових чисел (можна легко переконатися, що остання цифра квадрату числа залежить лише від останньої цифри числа й не залежить від інших цифр у ньому). Якщо ж ціле число закінчується на  2, 3, 7, 8, то корінь з нього не може бути цілим числом.

Схожі закономірності діють і в інших позиційних системах, основа яких відрізняється від 10: остання цифра квадрату числа залежить тільки від останньої цифри числа, але множини останніх цифр квадратів будуть іншими. Користі з останньої цифри в якійсь одній системі небагато: так, на 1 у десятковій системі закінчуються числа 1, 11, 21,..., 81 тощо, але лише деякі з них є квадратами цілих чисел (1=1², 81=9², 121=11² — проте, більшість чисел на 1, співрозмірних з ними, квадратами не є). Але, якщо записати число в кількох різних позиційних системах, то ймовірність того, що остання цифра неквадрата потрапить до множин останніх цифр квадратів у всіх цих системах, буде нижчою. Припускаю, що в певних межах це можна використати для перевірки, чи є число квадратом цілого (або ж, принаймні, це дозволить відсіяти значну частину неквадратів). Очевидно, більш ефективними будуть такі основи, у яких множини останніх цифр квадратів будуть якомога меншими відносно основи — тоді більший відсоток хибних результатів буде відсіяно. Я написав програму (на APL), щоб подивитися, як виглядатимуть множини останніх цифр для різних основ (використавши в ролі додаткових цифр літери латинського та кількох інших алфавітів):

      ⎕aa←⎕ucs(⎕ucs'Ա')+⍳38
⍝ ԱԲԳԴԵԶԷԸԹԺԻԼԽԾԿՀՁՂՃՄՅՆՇՈՉՊՋՌՍՎՏՐՑՒՓՔՕՖ
      ⎕ag←⎕ucs(⎕ucs'ა')+⍳38
⍝ აბგდევზთიკლმნოპჟრსტუფქღყშჩცძწჭხჯჰჱჲჳჴჵ
      ⎕ah←⎕ucs(⎕ucs'א')+⍳27
⍝ אבגדהוזחטיךכלםמןנסעףפץצקרשת
      ⎕al←⎕ucs(⎕ucs'α')+⍳25
⍝ αβγδεζηθικλμνξοπρςστυφχψω
      ⎕←⊃{⍵('0123456789',⎕a,⎕al,⎕ah,⎕ag,⎕aa)[∪⍵|2⋆⍨⍳⍵]}¨2+⍳128

Результат:

  2  01
  3  01
  4  01
  5  014
  6  0143
  7  0142
  8  014
  9  0147
 10  014965
 11  014953
 12  0149
 13  01493CA
 14  01492B87
 15  0149A6
 16  0149
 17  0149G82FD
 18  0149G7DA
 19  0149G6HB75
 20  0149G5
 21  0149GF7I
 22  0149G3E5KFCB
 23  0149G2D3IC86
 24  0149GC
 25  0149GBOE6LJ
 26  0149GPANC3MHED
 27  0149GPMAJD7
 28  0149GP8L
 29  0149GP7K6ND5SOM
 30  0149GP6JLAOF
 31  0149GP5I2J7SKEA8
 32  0149GPH
 33  0149GP3VFMCR
 34  0149GP2FUDWJ8XQLIH
 35  0149GPETBULF
 36  0149GPDS
 37  0149GPαCR7QAXLB3YUS
 38  0149GPαBQ5O7UH6ZSNKJ
 39  0149GPαA3MRDUC
 40  0149GPαOK
 41  0149GPα8NεIδL5WKA2βXV
 42  0149GPα7MδβISFUL
 43  0149GPα6LγEZFεOAζVNHDB
 44  0149GPα5KβCX
 45  0149GPαJAVYε
 46  0149GPα3IZ8T6VCζQD2δWRON
 47  0149GPα2HY6R3S8βL7ηWOIEC
 48  0149GPαX
 49  0149GPαFW2NλMTBιUI8θδβ
 50  0149GPαξEVLιJλ6δOBζYTQ
 51  0149GPαξDUJηθLYIXF
 52  0149GPαξCTνHεD
 53  0149GPαξBSμFγAβDιO6θTH7ρληε
 54  0149GPαξARλD7YεJβMρθVS
 55  0149GPαξQκBYV5EFιK
 56  0149GPαξ8ιWS
 57  0149GPαξ7OθUτσSδJη6κ
 58  0149GPαξ6Nη5SςMπOφYDρZK7σκγXUT
 59  0149GPαξ5Mζ3QπJνKςT7λSCφκZRLHF
 60  0149GPαξLεOκ
 61  0149GPαξ3KδωMμDηCκJυYEφζRF5χρνλ
 62  0149GPαξ2JγψKκAδ8ζEπS7οXI5υμεZWV
 63  0149GPαξIβχθ7λMS
 64  0149GPαξHφζX
 65  0149GPαξדZυEδUאTAπεQτ
 66  0149GPαξדFYτCβRχωVκMν3ηX
 67  0149GPαξדEXσAZבOτLυQהδFωεM6ψμβTNJH
 68  0149GPαξדDWς8XωLρH
 69  0149GPαξדCVρ6χIDντRλOδ3σ
 70  0149GPαξדBUπTυFλιοLδהEωZ
 71  0149GPαξדATο2RσCθ5ε6κFχW8φβJ3ωνγUOKI
 72  0149GPαξדSρε
 73  0149GPαξד8RνךNο6βיWטZ3λIהζJכσγOC2זאφτ
 74  0149GPαξד7QμיLν3YזSהUךεBχXAגιRCלבςλζγβ
 75  0149GPαξד6λטJVOאוYπσδL
 76  0149GPαξד5OκחHιלSאKφ
 77  0149GPαξדNιזFηךχςυMβωEBי
 78  0149GPαξד3MθוDεטτCAπאUρRηמνδ
 79  0149GPαξד2LηהBγזJρ8κ5λAτNכιIלπVDןבοεWQMK
 80  0149GPαξדKζה
 81  0149GPαξדJεג7YDλβןעθχSτVיρMAלזא
 82  0149GPαξדפIδב5WאAθסXכVםβ2πKלλLףψεN8נוφοκηζ
 83  0149GPαξדפHγא3Uψ7εמTחQטVסιCהβBיνSAנגπζXRNL
 84  0149GPαξדפβωSφכL
 85  0149GPαξדפFψקQτYטLωJוUןοπZי
 86  0149GPαξדפEZχצOςקVוHυBσDωNםζAזεFסφγL6עחψρμιθ
 87  0149GPαξדפDYφץMπSגρ67σזXχUκסηO
 88  0149GPαξדפCXυKףωνι
 89  0149GPαξדפBWτףIμסMφ5ιרδקη2ςHכεAךκLაחοYK8תעלטז
 90  0149GPαξדפAVσעκןJεYרλאτי
 91  0149GPαξדפUςסEθםπაנTעδυMNηהZ
 92  0149GPαξדפ8TρנCζכDνרWלOט
 93  0149GPαξדפ7SπןAδיκץטJIזסεגVותXგכ
 94  0149GPαξדפ6Rοמ8βח7ηעOהEψCאIךWბσLקτS3םςYH2צכגυπνμ
 95  0149GPαξדפ5Qם6ZוδןKאστBOκιרJףU
 96  0149GPαξדפνלXφ
 97  0149GPαξדפ3Oμכ2VבთXיCςიιდθზο8הRაσMბאZBשוνWI6ვרעמל
 98  0149GPαξדפ2NλךTωვUז8ეδשβაθφIעιBסMთכπWFרםהχςο
 99  0149GPαξדפMκיკRχდაYVץזβτ
100  0149GPαξדפLιטიυბOאζקTן
101  0149GPαξדפნKθחთNσתLχკβףOךJיMנXეρEעκDקυU6רהμVH5იაץסן
102  0149GPαξדפნJηזზLρרIτXןוDFיקθטYכვUתωπ
103  0149GPαξדפნIζוვJοצFρდTכEא7χ8גHןYკψNეωU2עτXDლץחυλγWSQ
104  0149GPαξדפნHεהეνCაחυρ
105  0149GPαξדפნδდFλערLπმωיקU
106  0149GPαξדפნFγגგDιנ6θץHωსλთεვηმρ7יTიψOკוβAდחμSBპბסטבφσς
107  0149GPαξדפნEβבბBηמ3εעDυოζგYתZეιსאJשνCרςNპןρUAმצטφμδXTR
108  0149GPαξדפნDאაεלβןρკרS
109  0149GPαξדפნCZωת7γךტYל5νვVףMמLסSბθფוQკאRრםλKსצגκTF3პზაקץ
110  0149GPαξדפნBYψש5טრVיιბQמEךKმυFდωוκףτ
111  0149GPαξדפნAXχר3YזპSფεLיג7CלგλמβסმRקνU
112  0149GPαξדפნWφקהს
113  0149GPαξדפნ8VυצშUגლMאპWנBωყπტοქφ7כQთςDაρIმטζFრץבιSE2სკდתר
114  0149GPαξדפნ7UτץყSאიJχმל6ტκθპშגרηןδσתOვוφ
115  0149GPαξדפნ6TσღQψზτიOטοოδთζრמVსךיλרZ
116  0149GPαξדפნ5SςףქOφეDρვKהშκიXაT
117  0149GPαξדפნRρעფMτგAאεდץაჟθზD
118  0149GPαξדפნ3QπסუKςა7λתCφრZשLןFםHףRზκწךSსוTშעνJღרבζM5ფთקמחגωψ
119  0149GPαξדפნ2οנტIπשθק8ςUFיזכרZωვლWLპη
120  0149GPαξדפნOןსקεიω
121  0149GPαξדפნNνמრEμץჯβסκეKך3χძςცυזFשγჩטRფיYბψV5პףωηQCყჟკვდ
122  0149GPαξדפნჱMμםჟCκףჭYמხζაFוჯρქλუνჩχ5ןRპφEთυJტלηDფצωδK3ღკשניהבא
123  0149GPαξדפნჱLλלპAθסძVכβקאცჟδεსხוდκץηφგIתπX
124  0149GPαξדפნჱKκכო8ζןჩSטშXף5υქεკWვ
125  0149GPαξדפნჱJιך6δםყוქTןπრYდשOბVλჯטLυEმאწקσQოעψζBჴცტიზ
126  0149GPαξדפნჱIθיმβכქMגტλSרעდχაז7შ
127  0149GPαξדפნჱHηטლ2ZיუJωჟLחჭζზMעBכ8לDץQმμჴןUჩךVჰקοIძתאβFჲრაםבριγYW
128  0149GPαξדפნჱζחკXსφHჩბלה
129  0149GPαξדפნჱFεזიԲVוჟDσკωქקAԱχφჴ6עპρתθგყLסOჭმ

Ось така ялиночка. Найкращими є ті основи, навпроти яких ми бачимо спад відносно сусідніх «гілочок».

Як бачимо, 10 — не найкраща основа для задачі пошуку квадратів: шість цифр з десяти можливих. Непоганий результат дає основа 16: чотири цифри з шістнадцяти можливих — тобто, достатньо записати число в шістнадцятковій системі (чи просто взяти остачу від ділення на 16), щоб відсіяти 3/4 чисел, які не є квадратами. Ще кращі показники дають 48 (8 з 48), 32 (7 з 32) та інші степені двійки, 80 (12 з 80) тощо. Найгірші (тобто, ті, що мають відносно великі множини останніх цифр квадратів) можна поділити на дві великі категорії: прості числа (5, 7, 11, і т.д.) та подвоєні прості числа (6, 10, 14 і т.д. — як бачимо, сюди потрапляє й 10).

З розміру знайденої множини вже можна сказати, що число просте, якщо воно непарне. Ось той же пошук, але тільки для непарних основ — як бачимо, «гілочки» навпроти простих числел ідуть точно по краю «ялинки», для решти основ вони коротші:

⎕←⊃{⍵('0123456789',⎕a,⎕al,⎕ah,⎕ag,⎕aa)[∪⍵|2⋆⍨⍳⍵]}¨1+2×⍳80
  1  0
  3  01
  5  014
  7  0142
  9  0147
 11  014953
 13  01493CA
 15  0149A6
 17  0149G82FD
 19  0149G6HB75
 21  0149GF7I
 23  0149G2D3IC86
 25  0149GBOE6LJ
 27  0149GPMAJD7
 29  0149GP7K6ND5SOM
 31  0149GP5I2J7SKEA8
 33  0149GP3VFMCR
 35  0149GPETBULF
 37  0149GPαCR7QAXLB3YUS
 39  0149GPαA3MRDUC
 41  0149GPα8NεIδL5WKA2βXV
 43  0149GPα6LγEZFεOAζVNHDB
 45  0149GPαJAVYε
 47  0149GPα2HY6R3S8βL7ηWOIEC
 49  0149GPαFW2NλMTBιUI8θδβ
 51  0149GPαξDUJηθLYIXF
 53  0149GPαξBSμFγAβDιO6θTH7ρληε
 55  0149GPαξQκBYV5EFιK
 57  0149GPαξ7OθUτσSδJη6κ
 59  0149GPαξ5Mζ3QπJνKςT7λSCφκZRLHF
 61  0149GPαξ3KδωMμDηCκJυYEφζRF5χρνλ
 63  0149GPαξIβχθ7λMS
 65  0149GPαξדZυEδUאTAπεQτ
 67  0149GPαξדEXσAZבOτLυQהδFωεM6ψμβTNJH
 69  0149GPαξדCVρ6χIDντRλOδ3σ
 71  0149GPαξדATο2RσCθ5ε6κFχW8φβJ3ωνγUOKI
 73  0149GPαξד8RνךNο6βיWטZ3λIהζJכσγOC2זאφτ
 75  0149GPαξד6λטJVOאוYπσδL
 77  0149GPαξדNιזFηךχςυMβωEBי
 79  0149GPαξד2LηהBγזJρ8κ5λAτNכιIלπVDןבοεWQMK
 81  0149GPαξדJεג7YDλβןעθχSτVיρMAלזא
 83  0149GPαξדפHγא3Uψ7εמTחQטVסιCהβBיνSAנגπζXRNL
 85  0149GPαξדפFψקQτYטLωJוUןοπZי
 87  0149GPαξדפDYφץMπSגρ67σזXχUκסηO
 89  0149GPαξדפBWτףIμסMφ5ιרδקη2ςHכεAךκLაחοYK8תעלטז
 91  0149GPαξדפUςסEθםπაנTעδυMNηהZ
 93  0149GPαξדפ7SπןAδיκץטJIזסεגVותXგכ
 95  0149GPαξדפ5Qם6ZוδןKאστBOκιרJףU
 97  0149GPαξדפ3Oμכ2VבთXיCςიιდθზο8הRაσMბאZBשוνWI6ვרעמל
 99  0149GPαξדפMκיკRχდაYVץזβτ
101  0149GPαξדפნKθחთNσתLχკβףOךJיMנXეρEעκDקυU6רהμVH5იაץסן
103  0149GPαξדפნIζוვJοצFρდTכEא7χ8גHןYკψNეωU2עτXDლץחυλγWSQ
105  0149GPαξדפნδდFλערLπმωיקU
107  0149GPαξדפნEβבბBηמ3εעDυოζგYתZეιსאJשνCרςNპןρUAმצטφμδXTR
109  0149GPαξדפნCZωת7γךტYל5νვVףMמLסSბθფוQკאRრםλKსצגκTF3პზაקץ
111  0149GPαξדפნAXχר3YזპSფεLיג7CלგλמβסმRקνU
113  0149GPαξדפნ8VυצშUגლMאპWנBωყπტοქφ7כQთςDაρIმטζFრץבιSE2სკდתר
115  0149GPαξדפნ6TσღQψზτიOטοოδთζრמVსךיλרZ
117  0149GPαξדפნRρעფMτგAאεდץაჟθზD
119  0149GPαξדפნ2οנტIπשθק8ςUFיזכרZωვლWLპη
121  0149GPαξדפნNνמრEμץჯβסκეKך3χძςცυזFשγჩטRფיYბψV5პףωηQCყჟკვდ
123  0149GPαξדפნჱLλלპAθסძVכβקאცჟδεსხוდκץηφგIתπX
125  0149GPαξדפნჱJιך6δםყוქTןπრYდשOბVλჯטLυEმאწקσQოעψζBჴცტიზ
127  0149GPαξדפნჱHηטლ2ZיუJωჟLחჭζზMעBכ8לDץQმμჴןUჩךVჰקοIძתאβFჲრაםבριγYW
129  0149GPαξדפნჱFεזიԲVוჟDσკωქקAԱχφჴ6עპρתθგყLסOჭმ
131  0149GPαξדפნჱDγהზჵRבმ7νდ5ρოLםԴτცιუζფλჭψ3ףSქאFპωKჩנθBშקχYCჳსბמגςκδZX
133  0149GPαξדפნჱBגეჳNχთηרԵιვჯθპUSმδცZჰם7ტנφშ
135  0149GPαξדפნჱYאგJσდԵעჴרქVןAზძλტיτε
137  0149GPαξדפნჱ7WψაჯFοתԱUלხSנԳιმJס2הԵωԴגԻםEვβჰחIუאHშכYԺოטδBჲლןυγM8Ըჳძქსჟ
139  0149GPαξדפნჱ5UφשჭBλצჲOזშKטჰYბ7וԲπწιჩκხσԶךDიηԴעVჴףγԼმגTԻტסρS6ჵუდנהτμζβZ
141  0149GPαξדפნჱ3Sτקძ7ηעხIאტCშOԻσβპკRYყԵכჟπზνגი6מLԱფ
143  0149GPαξדפნჱQςץჩ3γמცCτრEטԱηჟNადRფνԸנԵეυMסו
145  0149GPαξדפნჱՃOπףყYךღ6ზՀκიψწUდםהԻԾ5שქԿԴZσჵTჰKძ
147  0149GPαξדפნჱՃMסქՁUזტθაԺβՀIעωԲჰλπԵרცχმპჳFכვφδ
149  0149GPαξדפნჱՃKμןუԿQגპՂβץԴTףԸδი6זԵλჩXრSჟVღηჵאՇაUჳטHწחMԲרκ7ჰשσOՄჯთלςZJ5ՁԷჴხცშ
151  0149GPαξדפნჱՃIκםსԽMψლԾVןჳLכჵTשՄτხWმHაAרBგKჟβჴב2თδԻקYԼდμ5წסη8ԲკטθJՇԳღზףחχοιεγ
153  0149GPαξדפნჱՃθכჟԻIτზԺיჭDJןტרՄזՊԲρხძY
155  0149GPαξדפნჱՃEζיოԹπგԶJყ5υქוჵVზךԿԴԱοψןAδKטףՈZჴεთκ
157  0149GPαξדפნჱՃCδחმԷAμשԲDχსՍνოՏυძJץՆφԱεჩVფUყβჲρՀמBტλՄბZԿგηՌქזRՅღןιEՂჭვךπXH3ՇԽԵჴჰხ
159  0149GPαξדפნჱՃAβוკԵ6θץჳ7ρმՇεვλსיԺშODგდFSჭՁסძφტσטპՌגՉიωη

43 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

▼Пошук «хороших» основ для перевірки квадратів за останньою цифрою
      ⎕al←⎕ucs(⎕ucs'α')+⍳25
⍝ αβγδεζηθικλμνξοπρςστυφχψω
      ⎕ah←⎕ucs(⎕ucs'א')+⍳27
⍝ אבגדהוזחטיךכלםמןנסעףפץצקרשת
      ⎕ag←⎕ucs(⎕ucs'ა')+⍳38
⍝ აბგდევზთიკლმნოპჟრსტუფქღყშჩცძწჭხჯჰჱჲჳჴჵ
      ⎕aa←⎕ucs(⎕ucs'Ա')+⍳38
⍝ ԱԲԳԴԵԶԷԸԹԺԻԼԽԾԿՀՁՂՃՄՅՆՇՈՉՊՋՌՍՎՏՐՑՒՓՔՕՖ
      ⎕af←⎕ucs(⎕ucs'ᚠ')+⍳80
⍝ ᚠᚡᚢᚣᚤᚥᚦᚧᚨᚩᚪᚫᚬᚭᚮᚯᚰᚱᚲᚳᚴᚵᚶᚷᚸᚹᚺᚻᚼᚽᚾᚿᛀᛁᛂᛃᛄᛅᛆᛇᛈᛉᛊᛋᛌᛍᛎᛏᛐᛑᛒᛓᛔᛕᛖᛗᛘᛙᛚᛛᛜᛝᛞᛟᛠᛡᛢᛣᛤᛥᛦᛧᛨᛩᛪ᛫᛬᛭ᛮᛯ
      ⎕b←⎕ucs(⎕ucs'⠀')+⍳256 ⍝⠀...⣿
      
      ⎕d←'0123456789',⎕a,⎕al,⎕ah,⎕ag,⎕aa,⎕af,⎕b
      
      ⎕dn←{⍵≥⍴⎕d:'#'⋄⎕d[⍵]}¨

      ⊃{(∊1,2</⌈\{⍵[1]}¨⍵)/⍵}{ld←∪⍵|2⋆⍨⍳⍵⋄⍵ (⍵÷⍴ld) (⎕dn ld)}¨2+⍳5000

Після тривалих обчислень (вони справді тривають довго), програма виводить результат:

   2  1                    01
   3  1.5                  01
   4  2                    01
   8  2.6666666666666665   014
  12  3                    0149
  16  4                    0149
  32  4.571428571428571    0149GPH
  48  6                    0149GPαX
  80  6.666666666666667    0149GPαξדKζה
  96  6.857142857142857    0149GPαξדפνלXφ
 112  7                    0149GPαξדפნWφקהს
 144  9                    0149GPαξדפნჱρშלკ
 240  10                   0149GPαξדפნჱՃᚥᛀᛝקՓᛅიՄᚰԴს
 288  10.285714285714286   0149GPαξדפნჱՃᚥᛀᛝ⠌לშՌ᛭ᛌ⠕კՓᛕᚽՄ
 336  10.5                 0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐სՇᚽ᛬φშᛠᛕ⠬ᚭק⠅⠝
 480  11.428571428571429   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅იՄ⠅⠼⢰Դ⠕⡜⢥Փ᛭ს⢌ᛅ⡽᛬⢍⡥⡍⣝
 560  11.666666666666666   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#הწᛜ⠥⡠⢝⣜სᚬ⠅⣬ק⡥⣀Ք⠐⡜⣍᛬⠽⢰⡕#⢍
 576  12                   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#Ռᛌ⠕⢍⣌#לᛕ⠰⡽⠵⢐⣭კ#Մᚽ⣕⢽#⡅⢥᛭⡝
 720  15                   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰####ᚰ᛭⠼⡽⣀##Փ⢥⣼#⡠#Մ#⠀#⣭#⢍⠕
1008  15.75                0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#########Շᛕ⠬⣀#####ᚽ⢍###შ⡠⣕######⡬##⡝#⣌###
1440  17.142857142857142   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰###############Փ᛭⢥⣼######Մ⡽#####⠼####⣭#####⢍####⠕############
1680  17.5                 0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰##################ק⡥⣀#########᛬############⡜####⠅#####⡠###########⢍⣬#⢰##ს
2016  18                   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰######################ᚽ⠬⢍############⣕#######⡬#####ᛕ#######⣌##############⡝####შ#########
2640  18.333333333333332   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#############################⠠⢍⣼#############⡥#########ᚰ#########⣝######⣵################⠕####ᛅ##################᛬#######
2880  20                   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰###############################Մ⡽##############⣭#########⢍#############᛭####⢥##########################################⠕#
3600  20.454545454545453   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#####################################⠀⡽⣼#############################⣀#########᛭###############⠼#################⣭#################################⢥#####
4032  21                   0149GPαξדפნჱՃᚥᛀᛝ⠌⠭⡐⡵⢜⣅⣰#########################################ᚽ⣕##################ᛕ#############⣌###########################⡝################################################################⢍

Що це за маячня і для чого вона може знадобитися. Ідея в тому, щоб узяти останню цифру числа в якійсь системі числення (десятковій, шістнадцятковій тощо) і перевірити, чи може квадрат цілого закінчуватись на неї — щоб відкинути якомога більше чисел, якіне є квадратами цілих. Як було сказано вище, система з основою 10 є «поганою»: квадратих цілих можуть закінчуватись на 6 десяткових цифр із десяти можливих — таким чином, більшість неквадратів не буде відфільтровано, і їх доведеться відокремлювати іншими методами. Програма пошуку, яку ви бачите під спойлером, шукає «хороші» основи систем числення — такі, щоб у системі числення з кожною основою можна було відсіяти якомога більше неквадратів — більше, ніж у всіх системах з меншими основами.

Перший стовпчик — основи систем числення (починаючи з двійкової).
Третій — список цифр у цій системі, на які можуть закінчуватись квадрати цілих чисел (позначені арабськими цифрами, латинськими буквами, буквами кількох інших алфавітів, значками системи Брайля; для дуже великих основ систем числення їх не вистачає, тому решту цифр замінено на # — особливої ролі це не грає, нас цікавить, у першу чергу, їх кількість, а конкретні цифри потрібні переважно для контролю справності роботи програми).

Другий стовпчик — показник якості, відношення загальної кількості цифр у системі до кількості тих цифр, на які можуть закінчуватись квадрати цілих. Саме за ним проводився відбір «хороших» основ. Як бачимо, двійкова система для прискореного пошуку квадратів повністю непридатна: квадрати можуть закінчуватись на обидві цифри цієї системи, показник якості 1 означає, що «можливим квадратом» за цим критерієм буде кожен перший. Дещо краща трійкова, де цифр усього три, але квадрати можуть закінчуватись лише на 0 або 1 — таким чином, в одному випадку з трьох ми вже можемо чітко сказати, що число не є квадратом, бо воно закінчується на 2 (цифру, відсутню в цьому списку). Наступні знайдені основи дають кращий результат: так, 12-кова система вважає потенційними квадратами лише кожне третє число, а 16-кова — кожне четверте, і т.д.
Насправді жодна з систем не дозволяє визначити, що число є квадратом (це можливо лише з числами, квадрат яких менший за основу системи) — навіть найкращі з них лише допомагають відкинути більшість тих чисел, що квадратами не є. Що може мати сенс як додаткова оптимізація перед подальшою перевіркою. Напр., якщо число в 16-ковій системі не закінчується на 0, 1, 4 чи 9, то ми одразу можемо сказати, що корінь цього числа буде ірраціональним числом; якщо ж остання цифра належить до цих чотирьох, то корінь з числа може бути як цілим, так і ірраціональним.

Подібним чином можна робити пошук не лише можливих квадратів, а й кубів та інших степенів цілих чисел. Ось, наприклад, такий пошук хороших основ для пошуку кубів:

      ⊃{(∊1,2</⌈\{⍵[1]}¨⍵)/⍵}{ld←∪⍵|3⋆⍨⍳⍵⋄⍵ (⍵÷⍴ld) (⎕dn ld)}¨2+⍳2000 ⍝ пошук хороших основ для пошуку кубів
      ⍝ спади, як навпроти 819, властиві не лише степеню 3, а й іншим непарним степеням (5, 7,..)
   ⍝ 2  1                    01
   ⍝ 4  1.3333333333333333   013
   ⍝ 7  2.3333333333333335   016
   ⍝ 9  3                    018
  ⍝ 27  3.857142857142857    018AHJQ
  ⍝ 36  4                    018RSHJ9Z
  ⍝ 63  7                    018RבSατZ
 ⍝ 117  7.8                  018RדმქιგდςწלIQ
 ⍝ 171  8.142857142857142    018RדჵκᚦՄԹIԱՖJλQՃუՌβՋ
 ⍝ 189  9                    018RדჵՍԹՕτხლԲᚸבךSᚱՔდZ
 ⍝ 252  9.333333333333334    018Rדჵᛔდᛝ⠀ךᚱᛜმατᚸᚹSᛁՌZԲ⠇ᛕגՔ
 ⍝ 351  10.028571428571428   018Rדჵᛔ⡣Ք⠶⠢⡐დ⠫ᛧ⡪ᚺԺხᛥᚱQᚦ⠿ςქწᛮιᛌՂלᛞ⡑⠐
 ⍝ 468  10.4                 018Rדჵᛔ⡣ι⠑⢗⡐⡑⢠მ⡬ᛥ⠿⡽⣟⠈ᚱ⠐⢴ς⣘⠫ქწ⡫Ճ⢫⡙ᛋᛌᛧԺ⢅⣅⡳ՔდלჭՂ
 ⍝ 504  11.2                 018Rדჵᛔ⡣ᛝ⣼⡏ᚱᛜ⡫⢅⠬⠿⣄ᚹך⠤ᛁτՌZ⠉⢇⢡#ᛕმ⠇ג⣍⢽⢩Բ⠣დ⣩⣅⠫⣡⡇Ք
 ⍝ 756  12                   018Rדჵᛔ⡣##⠀##⣨⡫⡈⢅#τ⣄ᚹך#ᚸSᛁ⠿⠐⢡##⣼Բ#⠇⣡#ᛜ#ᚱ####⡏⢽#⠉###⠤⣍#Z⢇##Քდ⠫ᛕ⢩
 ⍝ 819  18.2                 018Rדჵᛔ⡣##ᚱგ#⠫მ#⠿#⠈##⢅#####⡫ხ⢆#⡪ᚺ#⠐##დՔ⣠⣨⣆⣡⣅#
⍝ 1197  19                   018Rדჵᛔ⡣###Թ#⡪#######ᛁ#⢢⣍####⢇####Ռ#⣠#####⡈##⣨ᚹ#⡏Ա####ᛕ#⡇⡢ᚺ####
⍝ 1953  19.727272727272727   018Rדჵᛔ⡣#####⠀##ᚺ##ᚸ##⣍Ռ#⣡##⣼############⡆###⡾###⢽בג⣆⢡#ᛝ####⡢#############Z#Ս######ᛕ###Աდ⠣⠤###⠫#⠈##

44 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

Якщо цікаво, то далі для квадратів до 20000:

5040 26.25
7920 27.5
9360 27.857142857142858
10080 30.0
15840 31.428571428571427
18480 32.083333333333336

Для кубів:

2223 21.17142857142857
2457 23.4
3276 24.266666666666666
3591 24.428571428571427
4788 25.333333333333332
5733 25.48
6552 29.12
9576 30.4
9828 31.2
14364 32.57142857142857
15561 49.4
Подякували: P.Y.1

koala вебсайт

45 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Судячи з часу повідомлення... Ви користувались цим же кодом, чи, може, знайшли більш оптимальний шлях пошуку? У мене пошуки основ (до 5000) для перевірки квадратів тривали щось близько години.

46 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

Я APL не знаю. Код - найтупіший можливий на Python:

r = len(set((i**2)%n for i in range(n)))
Подякували: P.Y., leofun012

koala вебсайт

47 Відповідь від koala Востаннє редагувалося koala (07.11.2021 20:22:51)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

▼одна хвилина на плюсах
#include <chrono>
#include <vector>
#include <iostream>

using Number = long long unsigned int;

int count_remainders(Number n)
{
    std::vector<bool> reminders(n);
    reminders[0] = reminders[1] = true;
    for (Number i = 2; i < (n + 1) / 2; ++i)
        reminders[i*i%n] = true;
    int count = 0;
    for (bool r : reminders)
        if (r)
            count++;
    return count;
}

int main(void)
{
    using namespace std::chrono_literals;
    auto start = std::chrono::high_resolution_clock::now();
    std::vector<std::pair<Number, Number>> result;
    result.push_back(std::make_pair(2, 2));
    for (Number n=3; (start + 60s) > std::chrono::high_resolution_clock::now(); ++n)
    {
        int digits = count_remainders(n);
        if(n*result.back().second>result.back().first*digits)
            result.push_back(std::make_pair(n,digits));
    }
    for (auto p : result)
    {
        std::cout << p.first << "\t" << (double)p.first / p.second << "\tdigits: " << p.second << "\n";
    }
    std::cin.get();
}
▼результат на моєму компі
2       1       digits: 2
3       1.5     digits: 2
4       2       digits: 2
8       2.66667 digits: 3
12      3       digits: 4
16      4       digits: 4
32      4.57143 digits: 7
48      6       digits: 8
80      6.66667 digits: 12
96      6.85714 digits: 14
112     7       digits: 16
144     9       digits: 16
240     10      digits: 24
288     10.2857 digits: 28
336     10.5    digits: 32
480     11.4286 digits: 42
560     11.6667 digits: 48
576     12      digits: 48
720     15      digits: 48
1008    15.75   digits: 64
1440    17.1429 digits: 84
1680    17.5    digits: 96
2016    18      digits: 112
2640    18.3333 digits: 144
2880    20      digits: 144
3600    20.4545 digits: 176
4032    21      digits: 192
5040    26.25   digits: 192
7920    27.5    digits: 288
9360    27.8571 digits: 336
10080   30      digits: 336
15840   31.4286 digits: 504
18480   32.0833 digits: 576
20160   35      digits: 576
25200   35.7955 digits: 704
31680   36.6667 digits: 864
37440   37.1429 digits: 1008
39600   37.5    digits: 1056
44352   38.5    digits: 1152
50400   40.9091 digits: 1232
55440   48.125  digits: 1152
65520   48.75   digits: 1344
85680   49.5833 digits: 1728
95760   49.875  digits: 1920
102960  51.0714 digits: 2016
110880  55      digits: 2016
131040  55.7143 digits: 2352
171360  56.6667 digits: 3024
Подякували: P.Y., leofun012

koala вебсайт

48 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

▼для кубів
2       1       digits: 2
3       1.5     digits: 2
4       2       digits: 2
7       2.33333 digits: 3
8       2.66667 digits: 3
9       3       digits: 3
13      3.25    digits: 4
26      3.71429 digits: 7
27      3.85714 digits: 7
36      4       digits: 9
56      5.09091 digits: 11
63      7       digits: 9
117     7.8     digits: 15
171     8.14286 digits: 21
189     9       digits: 21
252     9.33333 digits: 27
351     10.0286 digits: 35
468     10.4    digits: 45
504     11.2    digits: 45
756     12      digits: 63
819     18.2    digits: 45
1197    19      digits: 63
1953    19.7273 digits: 99
2223    21.1714 digits: 105
2457    23.4    digits: 105
3276    24.2667 digits: 135
3591    24.4286 digits: 147
4788    25.3333 digits: 189
5733    25.48   digits: 225
6552    29.12   digits: 225
9576    30.4    digits: 315
9828    31.2    digits: 315
14364   32.5714 digits: 441
15561   49.4    digits: 315
25389   51.2909 digits: 495
30303   51.8    digits: 585
35217   52.1733 digits: 675
37107   53.5455 digits: 693
44289   54.0769 digits: 819
46683   63.5143 digits: 735
62244   65.8667 digits: 945
76167   65.9455 digits: 1155
90909   66.6    digits: 1365
101556  68.3879 digits: 1485
108927  69.16   digits: 1575
124488  79.04   digits: 1575
Подякували: P.Y.1

koala вебсайт

49 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Зрозумів, у чому проблема низької швидкодії мого APL-коду. Функція «\» (сканування) зроблена вкрай неоптимально — замість того, щоб рахувати кожен наступний елемент з використанням проміжного результату, вона щоразу перераховує цей результат на основі всіх елементів підпослідовності, тому час зростає пропорційно до О². Важко сказати, навіщо її зробили такою, але досі у всіх APL'ах вона така (хіба що, можливо, в більш просунутих діалектах транслятор у частині випадків підставляє на її місце щось більш оптимальне, якщо це не впливає на логіку), якоїсь альтернативи серед стандартних засобів нема. Те, за що APL справді можна ненавидіти (а зовсім не за кракозяблики).

50 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Нехай a, b, c — натуральні числа ≥2, число с є найменшим спільним кратним чисел a та b.
Ці числа є основами систем числення, які використовуються для пошуку квадратів.
Чи можна замінити перевірку за основою c на дві перевірки за основами a та b?
Або ж, чи існують такі випадки, коли перевірка за основою с показує, що число не є квадратом цілого, а перевірки за основами a та b при цьому показують, що число є можливим квадратом?

51 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Остання цифра числа еквівалентна остачі від ділення числа на основу системи числення. Сума цифр (та інші способи перевірки подільності) також еквівалентна остачі: так, кінцева одноцифрова сума цифр десяткового числа еквівалентна остачі від ділення на 9 (з тією різницею, що сума 9 відповідає нульовій остачі). Знаючи це, можна знайти суму цифр десяткового числа й використати її для визначення, чи може число бути кубом натурального числа: куби можуть давати лише суму 1, 8 або 9.

52 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Існує система числення з основою 210 (що є добутком чотирьох найменших простих чисел, більших за 1). Потрібно придумати короткі однослівні назви для її розрядів (тобто, для чисел 210, 44100, 9261000 та ін.). Ваші ідеї?

53 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

P.Y. написав:

Існує система числення з основою 210 (що є добутком чотирьох найменших простих чисел, більших за 1). Потрібно придумати короткі однослівні назви для її розрядів (тобто, для чисел 210, 44100, 9261000 та ін.). Ваші ідеї?

Ви скажіть, як називаються її цифри, а я тоді скажу, як називати розряди.

Подякували: flatliner1

koala вебсайт

54 Відповідь від P.Y. Востаннє редагувалося P.Y. (29.11.2021 15:57:20)

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Цифри 1—9 — так само, як і в десятковій. Для цифр A—K та X (10—100, 200) існують однослівні назви (десять, двадцять, ..., дев'яносто, сто, двісті). Z — зеро, нуль.

Тобто, назви придумувати треба лише для цифр M—W (110—190). Можна називати їх назвами букв (ем, ен, пе, ку, ер, ес, те, у, ве). Або ж, продовжуючи логіку решти назв цифр, назвами чисел, злитими в одне слово (стодесять, стодвадцять і т.д.) — що, втім, надто громіздко. Також для цифри R (150) є назва півтораста.

Таким чином, якщо максимально задіяти існуючі однослівні назви, де вони є, та назви букв, де однослівних числівників нема, вийде ось такий ряд:
один, два, три, чотири, п'ять, шість, сім, вісім, дев'ять,
десять, двадцять, тридцять, сорок, п'ятдесят (або півста, півсотня), шістдесят, сімдесят, вісімдесят, дев'яносто, сто,
ем, ен, пе, ку, півтораста, ес, те, у, ве, двісті, зеро.

55 Відповідь від koala Востаннє редагувалося koala (29.11.2021 16:06:12)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

Добре, це не 210-кова, це 21-10-кова система (двадцять один-десяткова).
Ну що ж, 210 - це, мабуть, буде омега. Далі беремо латинські назви чисел: 44100 - біомега, 9261000 - тріомега (не плутати з "три омеги", тобто 630) і т.д. Дуодециомега, 21012 = 7355827511386641000000000000.

Подякували: P.Y.1

koala вебсайт

56 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

koala написав:

Добре, це не 210-кова, це 21-10-кова система (двадцять один-десяткова).

Подібно до вавилонської 60-кової, яка теж, фактично, є 6-10-ковою. Проте, в обох випадках усередині великих розрядів запис непозиційний (тобто, одиниці й десятки позначаються різними символами), тоді як самі великі розряди утворюють позиційну систему.

57 Відповідь від P.Y. Востаннє редагувалося P.Y. (29.11.2021 17:03:46)

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

koala написав:

Добре, це не 210-кова, це 21-10-кова система (двадцять один-десяткова).
Ну що ж, 210 - це, мабуть, буде омега. Далі беремо латинські назви чисел: 44100 - біомега, 9261000 - тріомега (не плутати з "три омеги", тобто 630) і т.д. Дуодециомега, 21012 = 7355827511386641000000000000.

Якщо вже брати грецьку літеру в компанію до латинських літер та українських числівників, то чом би не взяти увесь грецький алфавіт (замість того, щоб вказувати степінь числівниковим префіксом)? Тоді 210¹ — альфа, 210² — бета,  і т.д. Омега, в цьому випадку, буде назвою 210²⁴ (чи 210²⁶, якщо використати архаїчні дигамму й коппу).
(Р.Ѕ. Варіант: грецький алфавіт з кінця: омега=210, псі=44100, і т.д.)

Або ж, якщо степені 210 позначати іншомовними числівниками, то, можливо, має сенс узяти щось неіндоєвропейське (вже згадана проблема «три», що в межах цієї сім'ї називається скрізь приблизно однаково) — тоді й без омеги можна обійтися. Проблеми з назвами виникнуть лише при перекладі на мову, з якої ці назви було взято. Тобто, мова має бути або мертвою (але з відомою нам вимовою), або хоча б достатньо рідкісною, і в неї не повинно бути родичів. Шумерська, етруська, баскська, айну... І так, слід підібрати таку мову, що не даватиме небажаних збігів з іншими назвами числівників.

58 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

Узагалі, було б непогано взяти якісь загальновідомі величини, що відповідають (точно чи приблизно) потрібним нам значенням. Напр., числа, близькі до 365 чи 360, могли б отримати назву «рік» (бо це відповідає кількості днів у році). Або сорок (назва одягу, на пошиття якого йде 40 шкурок). Ідеально було б знайти і для 210 щось подібне...

59 Відповідь від P.Y. Востаннє редагувалося P.Y. (30.11.2021 17:03:53)

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 355
    • Репутація: 4823

Re: Непрактичне

koala написав:
P.Y. написав:

Існує система числення з основою 210 (що є добутком чотирьох найменших простих чисел, більших за 1). Потрібно придумати короткі однослівні назви для її розрядів (тобто, для чисел 210, 44100, 9261000 та ін.). Ваші ідеї?

Ви скажіть, як називаються її цифри, а я тоді скажу, як називати розряди.

До речі, нема нічого складного в тому, щоб сконструювати короткі назви для кожної цифри в системі числення з досить великою основою. В українському алфавіті є 21 приголосна (не рахуючи Й) та 10 голосних — комбінуючи їх, можна отримати до 210 різних складів. Зрозуміло, такі односкладові назви не матимуть нічого спільного з існуючими числівниками, але, принаймні, їх можна буде вимовити, а з їхнього вигляду легко отримати їхні значення.

Якщо застосувати такий підхід, від запису числа цифрами можна відмовитись — якогось виграшу порівняно з літерами він не даватиме. Фактично, це теж буде 21-10-кова система, але кожна цифра малих розрядів у ній кодуватиметься одною літерою, що вимовлятиметься як приголосний чи голосний звук, а великий розряд, відповідно, вимовлятиметься як утворений з них склад.

60 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 309
    • Репутація: 13053

Re: Непрактичне

Іткуїл?

koala вебсайт