У десятковій позиційній системі остання цифра квадрату будь-якого цілого числа може бути лише 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ჭՁסძφტσטპՌגՉიωη