stau.space
My omnium-gatherom of scripts and source code.
1{
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 1,
6 "id": "cde771ec-e96e-49c8-bf3f-017bde583b16",
7 "metadata": {},
8 "outputs": [],
9 "source": [
10 "from main import *\n",
11 "from math import *\n",
12 "def mod_ast(x: int, mod: int) -> list[int]:\n",
13 " if (type(x) == int):\n",
14 " return x % mod\n",
15 " return x\n",
16 "def f(mod: int):\n",
17 " return lambda x: mod_ast(x, mod)"
18 ]
19 },
20 {
21 "cell_type": "code",
22 "execution_count": 2,
23 "id": "df2bf1a7-1304-4011-97b2-c1dc638e77bf",
24 "metadata": {},
25 "outputs": [],
26 "source": [
27 "lsts = diff_square(11, 2)"
28 ]
29 },
30 {
31 "cell_type": "code",
32 "execution_count": 3,
33 "id": "368cf981-e6f8-471e-b384-a4d3bc92f35d",
34 "metadata": {},
35 "outputs": [
36 {
37 "data": {
38 "text/plain": [
39 "[[-2, -1, 5, -6, 7, -4, 2, 3, '*', '*', 'k = 1'],\n",
40 " [-3, 4, -1, 1, 3, -2, 5, '*', -4, '*', 'k = 2'],\n",
41 " [2, -2, 6, -3, 5, 1, '*', -1, -6, '*', 'k = 3'],\n",
42 " [-4, 5, 2, -1, 8, '*', 1, -3, -7, '*', 'k = 4'],\n",
43 " [3, 1, 4, 2, '*', -3, -1, -4, -2, '*', 'k = 5'],\n",
44 " [-1, 3, 7, '*', 4, -5, -2, 1, -8, '*', 'k = 6'],\n",
45 " [1, 6, '*', -2, 2, -6, 3, -5, -1, '*', 'k = 7'],\n",
46 " [4, '*', 3, -4, 1, -1, -3, 2, -5, '*', 'k = 8'],\n",
47 " ['*', 2, 1, -5, 6, -7, 4, -2, -3, '*', 'k = 9']]"
48 ]
49 },
50 "execution_count": 3,
51 "metadata": {},
52 "output_type": "execute_result"
53 }
54 ],
55 "source": [
56 "lsts"
57 ]
58 },
59 {
60 "cell_type": "code",
61 "execution_count": 5,
62 "id": "84e69ed4-8684-4291-984c-22678745c809",
63 "metadata": {},
64 "outputs": [
65 {
66 "name": "stdout",
67 "output_type": "stream",
68 "text": [
69 "[8, 9, 5, 4, 7, 6, 2, 3, '*', '*', 'k = 1'] 8 8\n",
70 "[7, 4, 9, 1, 3, 8, 5, '*', 6, '*', 'k = 2'] 8 8\n",
71 "[2, 8, 6, 7, 5, 1, '*', 9, 4, '*', 'k = 3'] 8 8\n",
72 "[6, 5, 2, 9, 8, '*', 1, 7, 3, '*', 'k = 4'] 8 8\n",
73 "[3, 1, 4, 2, '*', 7, 9, 6, 8, '*', 'k = 5'] 8 8\n",
74 "[9, 3, 7, '*', 4, 5, 8, 1, 2, '*', 'k = 6'] 8 8\n",
75 "[1, 6, '*', 8, 2, 4, 3, 5, 9, '*', 'k = 7'] 8 8\n",
76 "[4, '*', 3, 6, 1, 9, 7, 2, 5, '*', 'k = 8'] 8 8\n",
77 "['*', 2, 1, 5, 6, 3, 4, 8, 7, '*', 'k = 9'] 8 8\n"
78 ]
79 }
80 ],
81 "source": [
82 "for lst in [list(map(f(10), lst)) for lst in lsts]:\n",
83 " print(lst, len(set(ints(lst))), len(ints(lst)))"
84 ]
85 },
86 {
87 "cell_type": "code",
88 "execution_count": 64,
89 "id": "82b0e21a-41bc-4b62-b180-b6769adaa983",
90 "metadata": {},
91 "outputs": [
92 {
93 "data": {
94 "text/plain": [
95 "[2, 6, 7, 8]"
96 ]
97 },
98 "execution_count": 64,
99 "metadata": {},
100 "output_type": "execute_result"
101 }
102 ],
103 "source": [
104 "primitive_roots(11)"
105 ]
106 },
107 {
108 "cell_type": "code",
109 "execution_count": 21,
110 "id": "9f7848c4-e2de-4494-b0bb-cd5a4c5631c1",
111 "metadata": {},
112 "outputs": [
113 {
114 "name": "stdout",
115 "output_type": "stream",
116 "text": [
117 "10 10\n",
118 "10 10\n",
119 "10 10\n",
120 "10 10\n",
121 "10 10\n",
122 "10 10\n"
123 ]
124 }
125 ],
126 "source": [
127 "for lst in lsts:\n",
128 " print(len(set(ints(lst))), len(ints(lst)))"
129 ]
130 },
131 {
132 "cell_type": "code",
133 "execution_count": 46,
134 "id": "93051848-7dff-4bc6-b81f-7a5ec1a36f30",
135 "metadata": {},
136 "outputs": [],
137 "source": [
138 "lhs = test[:len(test) // 2]\n",
139 "rhs = test[ceil(len(test) / 2):]"
140 ]
141 },
142 {
143 "cell_type": "code",
144 "execution_count": 47,
145 "id": "618ba557-f427-4544-b2b8-856819f55086",
146 "metadata": {},
147 "outputs": [
148 {
149 "name": "stdout",
150 "output_type": "stream",
151 "text": [
152 "10 7 3\n",
153 "11 8 3\n",
154 "5 2 3\n",
155 "6 3 3\n"
156 ]
157 }
158 ],
159 "source": [
160 "for l, r in zip(lhs, rhs):\n",
161 " print(l, r, int(l - r) % 12)"
162 ]
163 },
164 {
165 "cell_type": "code",
166 "execution_count": 55,
167 "id": "e0c5029e-500f-4d19-9e81-ed76474266bd",
168 "metadata": {},
169 "outputs": [],
170 "source": [
171 "lsts = diff_square(11, 2)\n",
172 "lsts = [list(map(lambda x: x % 12, ints(lst))) for lst in lsts]\n",
173 "\n",
174 "first = lsts[0]\n",
175 "lsts = [lst[:-idx] for idx, lst in enumerate(lsts)]\n",
176 "lsts[0] = first\n",
177 "\n",
178 "for lst in lsts:\n",
179 " lhs = lst[:len(lst) // 2]\n",
180 " rhs = lst[ceil(len(lst) / 2):]\n",
181 " diff = (lhs[0] - rhs[0]) % 12\n",
182 " assert(all(map(lambda x: (x[0] - x[1]) % 12 == diff, zip(lhs, rhs))))"
183 ]
184 },
185 {
186 "cell_type": "code",
187 "execution_count": 4,
188 "id": "e9ca3cfd-c6d7-4001-94d3-67934c1dcdfe",
189 "metadata": {},
190 "outputs": [],
191 "source": [
192 "primes = load_file(\"primes.h\")"
193 ]
194 },
195 {
196 "cell_type": "code",
197 "execution_count": 67,
198 "id": "9dfde2de-3379-41cb-bd83-39bdab613df4",
199 "metadata": {},
200 "outputs": [],
201 "source": [
202 "for idx, prime in enumerate(primes):\n",
203 " if idx == 50:\n",
204 " break"
205 ]
206 },
207 {
208 "cell_type": "code",
209 "execution_count": 5,
210 "id": "09fb6792-1f48-4885-808c-38d3f206959b",
211 "metadata": {},
212 "outputs": [],
213 "source": [
214 "def predicate(prime: int, alpha: int) -> bool:\n",
215 " diffs = diff_square(prime, alpha)\n",
216 " diffs = [list(map(lambda x: x % (prime + 1), ints(lst))) for lst in diffs]\n",
217 " diffs = [diffs[0]] + [lst[:-idx] for idx, lst in enumerate(diffs[1:], 1)]\n",
218 "\n",
219 " def inner_pred(prime: int, lst: [int]) -> bool:\n",
220 " lhs = lst[:len(lst) // 2]\n",
221 " rhs = lst[ceil(len(lst) / 2):]\n",
222 " diff = (lhs[0] - rhs[0]) % (prime + 1)\n",
223 " return all(map(lambda x: (x[0] - x[1]) % (prime + 1) == diff, zip(lhs, rhs)))\n",
224 "\n",
225 " return all(map(lambda lst: inner_pred(prime, lst), diffs))"
226 ]
227 },
228 {
229 "cell_type": "code",
230 "execution_count": 18,
231 "id": "0844f3f2-ff4f-44b9-b771-aaf0c1536842",
232 "metadata": {},
233 "outputs": [
234 {
235 "ename": "SyntaxError",
236 "evalue": "incomplete input (3622495773.py, line 6)",
237 "output_type": "error",
238 "traceback": [
239 "\u001b[0;36m Cell \u001b[0;32mIn[18], line 6\u001b[0;36m\u001b[0m\n\u001b[0;31m \u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m incomplete input\n"
240 ]
241 }
242 ],
243 "source": [
244 "for idx, prime in enumerate(sorted(list(primes))[4:]):\n",
245 " if idx == 10:\n",
246 " break\n",
247 " for root in primitive_roots(prime):\n",
248 " # print(prime, root, predicate(prime, root))\n",
249 " "
250 ]
251 },
252 {
253 "cell_type": "code",
254 "execution_count": 115,
255 "id": "50831976-1716-4836-95d9-57474c344671",
256 "metadata": {},
257 "outputs": [],
258 "source": [
259 "diffs = diff_square(11, 7)\n",
260 "diffs = [list(map(lambda x: x % 12, ints(lst))) for lst in diffs]\n",
261 "diffs = [diffs[0]] + [lst[:-idx] for idx, lst in enumerate(diffs[1:], 1)]"
262 ]
263 },
264 {
265 "cell_type": "code",
266 "execution_count": 116,
267 "id": "695b1a4c-f02e-46b3-9061-e52ccbb7fff7",
268 "metadata": {},
269 "outputs": [
270 {
271 "data": {
272 "text/plain": [
273 "[[11, 4, 3, 7, 6, 10, 9, 2],\n",
274 " [3, 7, 10, 1, 4, 7, 11],\n",
275 " [6, 2, 4, 11, 1, 9],\n",
276 " [1, 8, 2, 8, 3],\n",
277 " [7, 6, 11, 10]]"
278 ]
279 },
280 "execution_count": 116,
281 "metadata": {},
282 "output_type": "execute_result"
283 }
284 ],
285 "source": [
286 "diffs"
287 ]
288 },
289 {
290 "cell_type": "code",
291 "execution_count": 114,
292 "id": "abf7a34b-238d-484c-8578-dbe97867db9d",
293 "metadata": {},
294 "outputs": [
295 {
296 "data": {
297 "text/plain": [
298 "[[-1, 4, 3, -5, 6, -2, -3, 2, '*', '*'],\n",
299 " [3, 7, -2, 1, 4, -5, -1, '*', -4, '*'],\n",
300 " [6, 2, 4, -1, 1, -3, '*', -2, -5, '*'],\n",
301 " [1, 8, 2, -4, 3, '*', -5, -3, -1, '*'],\n",
302 " [7, 6, -1, -2, '*', -7, -6, 1, 2, '*']]"
303 ]
304 },
305 "execution_count": 114,
306 "metadata": {},
307 "output_type": "execute_result"
308 }
309 ],
310 "source": [
311 "diff_square(11, 7)"
312 ]
313 },
314 {
315 "cell_type": "code",
316 "execution_count": 43,
317 "id": "82ea7838-94cd-49f0-ae19-b889c4d7ca85",
318 "metadata": {},
319 "outputs": [],
320 "source": [
321 "# fn is_costas(Vec<UInt> const& vec) -> Bool {\n",
322 "# using Set = std::unordered_set<UInt>;\n",
323 "\n",
324 "# if (Set(vec.cbegin(), vec.cend()).size() != vec.size())\n",
325 "# return false;\n",
326 "\n",
327 "# bool flag = false;\n",
328 "# auto const l = vec.size();\n",
329 "# #pragma omp parallel for num_threads(16) shared(flag)\n",
330 "# for (Size h = 1; h < l; ++h) {\n",
331 "# if (flag)\n",
332 "# continue;\n",
333 "# var set = Set((l - 2) - (h - 1));\n",
334 "# for (Size i = h - 1; i <= l - 2; --i)\n",
335 "# set.insert(vec[(h + i) % l] - vec[i]);\n",
336 "\n",
337 "# if (set.size() != (l - 2) - (h - 1)) {\n",
338 "# #pragma omp atomic write\n",
339 "# flag = true;\n",
340 "# }\n",
341 "# }\n",
342 "# return !flag;\n",
343 "# }\n",
344 "\n",
345 "def uniq(vec: list) -> bool:\n",
346 " for idx, x in enumerate(vec):\n",
347 " for idy, y in enumerate(vec):\n",
348 " if idx == idy:\n",
349 " continue\n",
350 " if x == y:\n",
351 " return False\n",
352 " return True\n",
353 "\n",
354 "def is_costas(vec: list[int]) -> bool:\n",
355 " n = len(vec)\n",
356 "\n",
357 " if not uniq(vec):\n",
358 " return False\n",
359 "\n",
360 " flag = False\n",
361 " for i in range(n): # parallel\n",
362 " if flag:\n",
363 " continue\n",
364 " \n",
365 " s = set()\n",
366 " for k in range(1, n):\n",
367 " result = vec[(i + k) % n] - vec[i]\n",
368 " if result in s:\n",
369 " print(\"here\")\n",
370 " return False\n",
371 " else:\n",
372 " s.add(result)\n",
373 "\n",
374 " if len(s) != n - 1:\n",
375 " return False\n",
376 "\n",
377 " return True"
378 ]
379 },
380 {
381 "cell_type": "code",
382 "execution_count": 44,
383 "id": "f72ae2f3-bc33-44d0-9880-11b45034066f",
384 "metadata": {},
385 "outputs": [
386 {
387 "name": "stdout",
388 "output_type": "stream",
389 "text": [
390 "True\n",
391 "True\n",
392 "True\n",
393 "True\n",
394 "True\n"
395 ]
396 }
397 ],
398 "source": [
399 "print(is_costas([1, 2, 4, 3]))\n",
400 "print(is_costas([1, 2, 3, 4]))\n",
401 "print(is_costas([1, 2]))\n",
402 "print(is_costas([2, 1]))\n",
403 "print(is_costas([2, 1, 4, 3]))"
404 ]
405 },
406 {
407 "cell_type": "code",
408 "execution_count": 26,
409 "id": "c1167d60-c9de-41a7-9525-197ebd0f898a",
410 "metadata": {},
411 "outputs": [
412 {
413 "data": {
414 "text/plain": [
415 "False"
416 ]
417 },
418 "execution_count": 26,
419 "metadata": {},
420 "output_type": "execute_result"
421 }
422 ],
423 "source": [
424 "uniq(list(range(100)) + [1])"
425 ]
426 },
427 {
428 "cell_type": "code",
429 "execution_count": null,
430 "id": "c3ececd8-87ea-40aa-bf40-896a5ced353f",
431 "metadata": {},
432 "outputs": [],
433 "source": []
434 }
435 ],
436 "metadata": {
437 "kernelspec": {
438 "display_name": "Python 3 (ipykernel)",
439 "language": "python",
440 "name": "python3"
441 },
442 "language_info": {
443 "codemirror_mode": {
444 "name": "ipython",
445 "version": 3
446 },
447 "file_extension": ".py",
448 "mimetype": "text/x-python",
449 "name": "python",
450 "nbconvert_exporter": "python",
451 "pygments_lexer": "ipython3",
452 "version": "3.12.3"
453 }
454 },
455 "nbformat": 4,
456 "nbformat_minor": 5
457}