Поиск ключевой 17-ки жадным алгоритмом

Message boards : Cafe : Поиск ключевой 17-ки жадным алгоритмом
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13582 - Posted: 9 Feb 2024, 1:04:32 UTC
Last modified: 9 Feb 2024, 1:12:48 UTC

В какой-то теме я уже писала о жадном алгоритме.
Жадный алгоритм скачет по диапазону, делая очень большие пропуски.
Понятно, что это не тотальная проверка, и решения при поиске этим алгоритмом могут потеряться.

Однако тотальный поиск ключевой 17-ки - фактически топтание на одном месте, на котором ключевой 17-ки, вполне возможно, нет.
Надо делать большой разброс по диапазону, потому что расстояния между известными ключевыми 17-ми огромные
[даже если есть пропущенные ключевые 17-ки]

1006882292528806742267: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
3954328349097827424397: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
4896552110116770789773: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
6751407944109046348063: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
7768326730875185894807: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
19252814175273852997757: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
154787380396512840656507: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
901985248981556228168767: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240

Написала простенькую программку для жадного алгоритма и запустила.
Ищу, ищу... нет ни одного приближения к ключевой 17-ке.
Хотя программу протестировала на известной ключевой 17-ке Врублевского.

Подумала: может ошибка какая вкралась в программу.
Решила попробовать в диапазоне маленьких чисел, приближения посыпались!
Например, приближение с 9 правильными элементами, с центральной тройкой

9258247267: [0, 24, 54, 64, 66, 76, 90, 114, 120, 126, 136, 156, 174, 184, 190, 196, 240]
9258247267: [0, 18, 30, 28, 0, -8, 0, 0, 0, 0, -14, 0, 0, -20, -26, -38, 0]
9

Продолжаю крутить программу в диапазоне больших чисел - дальше 901985248981556228168767.

Пока не найдено ни одного приближения.
ID: 13582 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13589 - Posted: 10 Feb 2024, 12:41:31 UTC
Last modified: 10 Feb 2024, 13:09:10 UTC

В программе жадного алгоритма добавила вывод приближений к ключевой 17-ке, в которых только первый, последний и центральный элементы правильные (то есть нет даже центральной тройки).

Ну вот, такое приближение, наконец-то, найдено

1807258784571196215476759: [0, 14, 20, 24, 44, 48, 54, 62, 120, 122, 164, 180, 182, 204, 218, 234, 240]
1807258784571196215476759: [0, 8, -4, -12, -22, -36, -36, -52, 0, -4, 14, 24, 8, 0, 2, 0, 0]
5

Случайно совпали с паттерном ещё два элемента.

Сейчас разверну это приближение для проверки.

Готово!

{1807258784571196215476759, *1807258784571196215476773, *1807258784571196215476779, *1807258784571196215476783,
*1807258784571196215476803, *1807258784571196215476807, *1807258784571196215476813, *1807258784571196215476821,
1807258784571196215476879, *1807258784571196215476881, *1807258784571196215476923, *1807258784571196215476939,
*1807258784571196215476941, 1807258784571196215476963, *1807258784571196215476977, 1807258784571196215476993,
1807258784571196215476999
}

Всё верно.

Всего 5 правильных элементов, 12 "дырок".
Ничего лучше пока нет.
ID: 13589 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13591 - Posted: 11 Feb 2024, 1:10:17 UTC
Last modified: 11 Feb 2024, 1:28:23 UTC

Цитирую письмо gris

Давно я даже выкладывал на дикси статистику по длинам 19-кортежей. Длина 252 встречается всё реже и реже. Ну это понятно. Вот небольшие данные по 17-240 кортежам.
E12 5025 240 16 time = 6min
E15 463 22 3 time = 8min
E18 55 5 0 time = 11min
E21 9 1 0 time = 20min
E22 5 0 0 time = 22min
E23 1 0 0 time = 24min
E26 0 0 0 time = 28min
Это уровень диапазона, где случайно берётся 10 млн последовательных простяшек и количество кортежей такого вида: длина 240, плюс центр плюс центральная тройка и время перебора.
Можно считать данные близкие к средним.
Как видно, начиная с Е23 в случайно выбранных 10 млн 17-кортежей не только тройку или центр встретить трудно, но и даже кортеж длиной 240 редчайший гость.

М-да...
У меня встретилось в области 25-значных чисел приближение к ключевой 17-ке с центральным правильным элементом, ну, и с крайними правильными элементами, разумеется
1807258784571196215476759: [0, 14, 20, 24, 44, 48, 54, 62, 120, 122, 164, 180, 182, 204, 218, 234, 240]

(развёрнуто в предыдущем сообщении)

С центральной тройкой пока не появилось приближение.

Таким образом, поиск ключевых 17-ок очень сложен в области больших чисел, потому что их очень мало там.
Врублевскому удалось в области 22-значных чисел найти 5 ключевых 17-ок

1006882292528806742267: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
3954328349097827424397: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
4896552110116770789773: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
6751407944109046348063: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
7768326730875185894807: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240

Будем надеяться, что пропущенных ключевых 17-ок у него нет.
А дальше уже совсем мало ключевых 17-ок найдено

19252814175273852997757: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
154787380396512840656507: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
901985248981556228168767: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240

(две последние найдены г. Петуховым; есть ли тут пропущенные ключевые 17-ки - одному Богу известно)

Поиск ключевых 17-ок почти эквивалентен поиску 19-ки с минимальным диаметром с той только разницей, что 19-ок с минимальным диаметром ещё меньше.
Все 19-ки с минимальным диаметром содержат ключевую 17-ку, но далеко не все ключевые 17-ки продолжаются до 19-ки с минимальным диаметром.
Из известных ключевых 17-ок не продолжилась ни одна.
ID: 13591 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13592 - Posted: 11 Feb 2024, 2:05:54 UTC
Last modified: 11 Feb 2024, 2:38:58 UTC

Давайте посмотрим на выход 19-ок с другими диаметрами.

Ещё раз покажу все 17-ки, найденные Ярославом Врублевским в конкурсе по кортежам ( в развёрнутом виде)

6837359459759035391: 0 42 60 66 72 120 126 150 156 162 186 192 240 246 252 270 312
{6837359459759035391, 6837359459759035433, 6837359459759035451, 6837359459759035457, 6837359459759035463, 6837359459759035511,
6837359459759035517, 6837359459759035541, 6837359459759035547, 6837359459759035553, 6837359459759035577, 6837359459759035583,
6837359459759035631, 6837359459759035637, 6837359459759035643, 6837359459759035661, 6837359459759035703}
 
7902083290948579129: 0 12 18 102 132 138 150 168 180 192 210 222 228 258 342 348 360
{7902083290948579129, 7902083290948579141, 7902083290948579147, 7902083290948579231, 7902083290948579261, 7902083290948579267,
7902083290948579279, 7902083290948579297, 7902083290948579309, 7902083290948579321, 7902083290948579339, 7902083290948579351,
7902083290948579357, 7902083290948579387, 7902083290948579471, 7902083290948579477, 7902083290948579489} 

8053379680763235601: 0 18 48 60 102 132 138 150 180 210 222 228 258 300 312 342 360
{8053379680763235601, 8053379680763235619, 8053379680763235649, 8053379680763235661, 8053379680763235703, 8053379680763235733,
8053379680763235739, 8053379680763235751, 8053379680763235781, 8053379680763235811, 8053379680763235823, 8053379680763235829,
8053379680763235859, 8053379680763235901, 8053379680763235913, 8053379680763235943, 8053379680763235961}

11954696436290948869: 0 18 60 78 90 138 144 168 174 180 204 210 258 270 288 330 348
{11954696436290948869, 11954696436290948887, 11954696436290948929, 11954696436290948947, 11954696436290948959, 11954696436290949007,
11954696436290949013, 11954696436290949037, 11954696436290949043, 11954696436290949049, 11954696436290949073, 11954696436290949079,
11954696436290949127, 11954696436290949139, 11954696436290949157, 11954696436290949199, 11954696436290949217}

12196464604998841777: 0 36 84 96 114 120 126 150 180 210 234 240 246 264 276 324 360
{12196464604998841777, 12196464604998841813, 12196464604998841861, 12196464604998841873, 12196464604998841891, 12196464604998841897,
12196464604998841903, 12196464604998841927, 12196464604998841957, 12196464604998841987, 12196464604998842011, 12196464604998842017,
12196464604998842023, 12196464604998842041, 12196464604998842053, 12196464604998842101, 12196464604998842137}

14271237683005753507: 0 24 30 84 96 114 150 156 180 204 210 246 264 276 330 336 360
{14271237683005753507, 14271237683005753531, 14271237683005753537, 14271237683005753591, 14271237683005753603, 14271237683005753621,
14271237683005753657, 14271237683005753663, 14271237683005753687, 14271237683005753711, 14271237683005753717, 14271237683005753753,
14271237683005753771, 14271237683005753783, 14271237683005753837, 14271237683005753843, 14271237683005753867}

17667344133365404873: 0 30 48 84 90 108 114 150 174 198 234 240 258 264 300 318 348
{17667344133365404873, 17667344133365404903, 17667344133365404921, 17667344133365404957, 17667344133365404963, 17667344133365404981,
17667344133365404987, 17667344133365405023, 17667344133365405047, 17667344133365405071, 17667344133365405107, 17667344133365405113,
17667344133365405131, 17667344133365405137, 17667344133365405173, 17667344133365405191, 17667344133365405221}

18462005826764715791: 0 78 90 102 120 162 168 192 210 228 252 258 300 318 330 342 420
{18462005826764715791, 18462005826764715869, 18462005826764715881, 18462005826764715893, 18462005826764715911, 18462005826764715953,
18462005826764715959, 18462005826764715983, 18462005826764716001, 18462005826764716019, 18462005826764716043, 18462005826764716049,
18462005826764716091, 18462005826764716109, 18462005826764716121, 18462005826764716133, 18462005826764716211}

258406392900394343851: 0 12 30 42 60 72 78 102 120 138 162 168 180 198 210 228 240
{258406392900394343851, 258406392900394343863, 258406392900394343881, 258406392900394343893, 258406392900394343911,
258406392900394343923, 258406392900394343929, 258406392900394343953, 258406392900394343971, 258406392900394343989,
258406392900394344013, 258406392900394344019, 258406392900394344031, 258406392900394344049, 258406392900394344061,
258406392900394344079, 258406392900394344091}

311634572279873026493: 0 18 24 60 78 84 108 138 144 150 180 204 210 228 264 270 288
{311634572279873026493, 311634572279873026511, 311634572279873026517, 311634572279873026553, 311634572279873026571,
311634572279873026577, 311634572279873026601, 311634572279873026631, 311634572279873026637, 311634572279873026643,
311634572279873026673, 311634572279873026697, 311634572279873026703, 311634572279873026721, 311634572279873026757,
311634572279873026763, 311634572279873026781}

384703558068522780559: 0 24 30 42 72 84 90 114 132 150 174 180 192 222 234 240 264
{384703558068522780559, 384703558068522780583, 384703558068522780589, 384703558068522780601, 384703558068522780631,
384703558068522780643, 384703558068522780649, 384703558068522780673, 384703558068522780691, 384703558068522780709,
384703558068522780733, 384703558068522780739, 384703558068522780751, 384703558068522780781, 384703558068522780793,
384703558068522780799, 384703558068522780823}

401276622469261903031: 0 6 12 30 72 90 96 120 126 132 156 162 180 222 240 246 252
{401276622469261903031, 401276622469261903037, 401276622469261903043, 401276622469261903061, 401276622469261903103,
401276622469261903121,401276622469261903127, 401276622469261903151, 401276622469261903157, 401276622469261903163,
401276622469261903187, 401276622469261903193, 401276622469261903211, 401276622469261903253, 401276622469261903271,
401276622469261903277, 401276622469261903283}

443707110791502007579: 0 42 72 84 114 120 132 150 162 174 192 204 210 240 252 282 324
{443707110791502007579, 443707110791502007621, 443707110791502007651, 443707110791502007663, 443707110791502007693,
443707110791502007699, 443707110791502007711, 443707110791502007729, 443707110791502007741, 443707110791502007753,
443707110791502007771, 443707110791502007783, 443707110791502007789, 443707110791502007819, 443707110791502007831,
443707110791502007861, 443707110791502007903}

535010601740877140023: 0 18 54 60 78 84 120 138 144 150 168 204 210 228 234 270 288
{535010601740877140023, 535010601740877140041, 535010601740877140077, 535010601740877140083, 535010601740877140101,
535010601740877140107, 535010601740877140143, 535010601740877140161, 535010601740877140167, 535010601740877140173,
535010601740877140191, 535010601740877140227, 535010601740877140233, 535010601740877140251, 535010601740877140257,
535010601740877140293, 535010601740877140311}

568398209014995678701: 0 6 12 30 42 72 90 96 126 156 162 180 210 222 240 246 252
{568398209014995678701, 568398209014995678707, 568398209014995678713, 568398209014995678731, 568398209014995678743,
568398209014995678773, 568398209014995678791, 568398209014995678797, 568398209014995678827, 568398209014995678857,
568398209014995678863, 568398209014995678881, 568398209014995678911, 568398209014995678923, 568398209014995678941,
568398209014995678947, 568398209014995678953}

702939111495760681807: 0 90 102 132 144 174 180 210 222 234 264 270 300 312 342 354 444
{702939111495760681807, 702939111495760681897, 702939111495760681909, 702939111495760681939, 702939111495760681951,
702939111495760681981, 702939111495760681987, 702939111495760682017, 702939111495760682029, 702939111495760682041,
702939111495760682071, 702939111495760682077, 702939111495760682107, 702939111495760682119, 702939111495760682149,
702939111495760682161, 702939111495760682251}

752853880537802642981: 0 6 12 30 42 72 96 120 126 132 156 180 210 222 240 246 252
{752853880537802642981, 752853880537802642987, 752853880537802642993, 752853880537802643011, 752853880537802643023,
752853880537802643053, 752853880537802643077, 752853880537802643101, 752853880537802643107, 752853880537802643113,
752853880537802643137, 752853880537802643161,752853880537802643191, 752853880537802643203, 752853880537802643221,
752853880537802643227, 752853880537802643233}

1006882292528806742267: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{1006882292528806742267, 1006882292528806742273, 1006882292528806742291, 1006882292528806742303, 1006882292528806742333,
1006882292528806742351, 1006882292528806742357, 1006882292528806742381, 1006882292528806742387, 1006882292528806742393,
1006882292528806742417, 1006882292528806742423, 1006882292528806742441, 1006882292528806742471, 1006882292528806742483,
1006882292528806742501, 1006882292528806742507}

1338977422865229706499: 0 12 24 30 42 54 84 90 132 174 180 210 222 234 240 252 264
{1338977422865229706499, 1338977422865229706511, 1338977422865229706523, 1338977422865229706529, 1338977422865229706541,
1338977422865229706553, 1338977422865229706583, 1338977422865229706589, 1338977422865229706631, 1338977422865229706673,
1338977422865229706679, 1338977422865229706709, 1338977422865229706721, 1338977422865229706733, 1338977422865229706739,
1338977422865229706751, 1338977422865229706763}

2035559077035293441299: 0 12 24 42 54 84 90 114 132 150 174 180 210 222 240 252 264
{2035559077035293441299, 2035559077035293441311, 2035559077035293441323, 2035559077035293441341, 2035559077035293441353,
2035559077035293441383, 2035559077035293441389, 2035559077035293441413, 2035559077035293441431, 2035559077035293441449,
2035559077035293441473, 2035559077035293441479, 2035559077035293441509, 2035559077035293441521, 2035559077035293441539,
2035559077035293441551, 2035559077035293441563}

3954328349097827424397: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{3954328349097827424397, 3954328349097827424403, 3954328349097827424421, 3954328349097827424433, 3954328349097827424463,
3954328349097827424481, 3954328349097827424487, 3954328349097827424511, 3954328349097827424517, 3954328349097827424523,
3954328349097827424547, 3954328349097827424553, 3954328349097827424571, 3954328349097827424601, 3954328349097827424613,
3954328349097827424631, 3954328349097827424637}

4896552110116770789773: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{4896552110116770789773, 4896552110116770789779, 4896552110116770789797, 4896552110116770789809, 4896552110116770789839,
4896552110116770789857, 4896552110116770789863, 4896552110116770789887, 4896552110116770789893, 4896552110116770789899,
4896552110116770789923, 4896552110116770789929, 4896552110116770789947, 4896552110116770789977, 4896552110116770789989,
4896552110116770790007, 4896552110116770790013}

6751407944109046348063: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{6751407944109046348063, 6751407944109046348069, 6751407944109046348087, 6751407944109046348099, 6751407944109046348129,
6751407944109046348147, 6751407944109046348153, 6751407944109046348177, 6751407944109046348183, 6751407944109046348189,
6751407944109046348213, 6751407944109046348219, 6751407944109046348237, 6751407944109046348267, 6751407944109046348279,
6751407944109046348297, 6751407944109046348303}

7768326730875185894807: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{7768326730875185894807, 7768326730875185894813, 7768326730875185894831, 7768326730875185894843, 7768326730875185894873,
7768326730875185894891, 7768326730875185894897, 7768326730875185894921, 7768326730875185894927, 7768326730875185894933,
7768326730875185894957, 7768326730875185894963, 7768326730875185894981, 7768326730875185895011, 7768326730875185895023,
7768326730875185895041, 7768326730875185895047}

19252814175273852997757: 0 6 24 36 66 84 90 114 120 126 150 156 174 204 216 234 240
{19252814175273852997757, 19252814175273852997763, 19252814175273852997781, 19252814175273852997793, 19252814175273852997823,
19252814175273852997841, 19252814175273852997847, 19252814175273852997871, 19252814175273852997877, 19252814175273852997883,
19252814175273852997907, 19252814175273852997913, 19252814175273852997931, 19252814175273852997961, 19252814175273852997973, 
19252814175273852997991, 19252814175273852997997}

20278587540464136529199: 0 12 30 42 60 72 78 102 120 138 162 168 180 198 210 228 240
{20278587540464136529199, 20278587540464136529211, 20278587540464136529229, 20278587540464136529241, 20278587540464136529259,
20278587540464136529271, 20278587540464136529277, 20278587540464136529301, 20278587540464136529319, 20278587540464136529337,
20278587540464136529361, 20278587540464136529367, 20278587540464136529379, 20278587540464136529397, 20278587540464136529409,
20278587540464136529427, 20278587540464136529439}

24300494153317939112651: 0 12 18 30 42 72 78 102 120 138 162 168 198 210 222 228 240
{24300494153317939112651, 24300494153317939112663, 24300494153317939112669, 24300494153317939112681, 24300494153317939112693,
24300494153317939112723, 24300494153317939112729, 24300494153317939112753, 24300494153317939112771, 24300494153317939112789,
24300494153317939112813, 24300494153317939112819, 24300494153317939112849, 24300494153317939112861, 24300494153317939112873,
24300494153317939112879, 24300494153317939112891}

25651315879379564172971: 0 12 18 30 42 72 78 102 120 138 162 168 198 210 222 228 240
{25651315879379564172971, 25651315879379564172983, 25651315879379564172989, 25651315879379564173001, 25651315879379564173013,
25651315879379564173043, 25651315879379564173049, 25651315879379564173073, 25651315879379564173091, 25651315879379564173109,
25651315879379564173133, 25651315879379564173139, 25651315879379564173169, 25651315879379564173181, 25651315879379564173193,
25651315879379564173199, 25651315879379564173211}

32686971428909208943211: 0 12 30 42 60 72 78 102 120 138 162 168 180 198 210 228 240
{32686971428909208943211, 32686971428909208943223, 32686971428909208943241, 32686971428909208943253, 32686971428909208943271,
32686971428909208943283, 32686971428909208943289, 32686971428909208943313, 32686971428909208943331, 32686971428909208943349,
32686971428909208943373, 32686971428909208943379, 32686971428909208943391, 32686971428909208943409, 32686971428909208943421,
32686971428909208943439, 32686971428909208943451}

29 17-ок нашёл Ярослав!
Ни одна из них не оказалась матрёшечной, то есть не продолжилась до 19-ки.

В BOINC-проекте TBEG найдено 15 17-ок.
Ни одна из них не оказалась матрёшечной!

В BOINC-проекте SPT найдено 20 17-ок, три из них из списка 17-ок, найденных Врублевским (подтверждены).
Остаётся 17 оригинальных 17-ок.
Только две из них оказались матрёшечными и дали нам две 19-ки.

Итак, выход такой: 61 шт. 17-ок --> 2 шт. 19-ок
То есть, примерно 1:30.

Для 19-ки с минимальным диаметром на данный момент имеем:
ключевых 17-ок 8 шт. --> 19-ок с минимальным диаметром 0 шт.

Может быть, когда ключевых 17-ок будет 30 шт., одна из них сматрёшничает в 19-ку с минимальным диаметром.
Есть робкая надежда, что это случится раньше :)
ID: 13592 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13593 - Posted: 11 Feb 2024, 5:40:13 UTC
Last modified: 12 Feb 2024, 0:55:50 UTC

А вот чуть получше приближение к ключевой 17-ке найдено жадным алгоритмом

1892624490778114045973617: [0, 6, 10, 22, 34, 36, 94, 102, 120, 130, 132, 136, 174, 
190, 214, 234, 240]
1892624490778114045973617: [0, 0, -14, -14, -32, -48, 4, -12, 0, 4, -18, -20, 0, -14, -2, 0, 0]
6

По-прежнему правильные крайние и центральный элементы, однако случайно совпали ещё три элемента, итог - 6 правильных элементов.

Тэк-с, прогресс наблюдается :)

Ещё одно приближение найдено, похуже, всего 3 правильных элемента

29493872188837481634885551: [0, 12, 18, 32, 36, 50, 68, 98, 120, 156, 162, 168,
176, 200, 228, 236, 240]
29493872188837481634885551: [0, 6, -6, -4, -30, -34, -22, -16, 0, 30, 12, 12, 2,  -4, 12, 2, 0]
3

А здесь уже центральная тройка наклёвывается :)

2097105135878405519729773: [0, 4, 10, 36, 40, 58, 60, 114, 120, 138, 166, 184, 196, 214, 226, 238, 240]
2097105135878405519729773: [0, -2, -14, 0, -26, -26, -30, 0, 0, 12, 16, 28, 22, 10, 10, 4, 0]
5

5 правильных элементов.
ID: 13593 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13610 - Posted: 12 Feb 2024, 3:51:21 UTC
Last modified: 12 Feb 2024, 3:52:45 UTC

На Ахиллесе-3 работает жадный алгоритм



Пока видим приближения с 3 правильными элементами.
Ну, и то хлеб :)
А то и посмотреть было не на что.

Да, жадный алгоритм забрасывает сети с очень большими дырами, трудно поймать что-нибудь в эти сети.
Даже самая крупная рыба может выскочить.
Однако жадный алгоритм позволяет не топтаться на одном месте, как при брутфорсе.
Пока я не вижу другой возможности создать большой разброс по диапазону.
Конечно, если бы было много техники, это просто сделать.
Но где же взять много техники?
Хорошо, что хотя бы Ахиллесы вернулись.
ID: 13610 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13611 - Posted: 12 Feb 2024, 5:23:17 UTC
Last modified: 12 Feb 2024, 5:42:18 UTC

Ого!
Отличное приближение к ключевой 17-ке найдено жадным алгоритмом - 10 правильных элементов

2232102066624229011552853: [0, 6, 24, 34, 66, 88, 90, 94, 120, 126, 144, 156, 174, 216, 234, 238, 240]
2232102066624229011552853: [0, 0, 0, -2, 0, 4, 0, -20, 0, 0, -6, 0, 0, 12, 18, 4, 0]
10

Хотя центральной тройки нет, только два элемента из неё правильные.

Сейчас разверну это приближение.

{2232102066624229011552853, 2232102066624229011552859, 2232102066624229011552877, *2232102066624229011552887, 2232102066624229011552919, *2232102066624229011552941, 2232102066624229011552943, *2232102066624229011552947, 2232102066624229011552973, 2232102066624229011552979, *2232102066624229011552997, 2232102066624229011553009, 2232102066624229011553027, *2232102066624229011553069, *2232102066624229011553087, *2232102066624229011553091, 2232102066624229011553093}

Очень хорошее приближение нашёл жадный алгоритм, всего 7 "дырок".

Какова вероятность попасть на полную ключевую 17-ку?
Разумеется, она близка к нулю, когда нет массовости поиска.
Запустить бы потоков 100, тогда можно чего-то ждать.
ID: 13611 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13612 - Posted: 12 Feb 2024, 17:20:14 UTC
Last modified: 13 Feb 2024, 18:31:34 UTC

В этом приближении наклёвывается центральная тройка

2251954556439791305064873: [0, 26, 30, 50, 80, 86, 98, 114, 120, 128, 138, 144, 180, 206, 218, 234, 240]
2251954556439791305064873: [0, 20, 6, 14, 14, 2, 8, 0, 0, 2, -12, -12, 6, 2, 2, 0, 0]
5

Чуть-чуть не получилась.

И снова центральная тройка наклёвывается :)

39163128499406940055472057: [0, 2, 44, 60, 72, 74, 104, 116, 120, 126, 156, 174, 186, 200, 204, 210, 240]
39163128499406940055472057: [0, -4, 20, 24, 6, -10, 14, 2, 0, 0, 6, 18, 12, -4, -12, -24, 0]
4

и ещё
2490184434226538730177121: [0, 6, 18, 22, 52, 76, 78, 100, 120, 126, 130, 162, 190, 196, 210, 216, 240]
2490184434226538730177121: [0, 0, -6, -14, -14, -8, -12, -14, 0, 0, -20, 6, 16, -8, -6, -18, 0]
5

61060338082919329390766447: [0, 26, 30, 36, 74, 92, 102, 114, 120, 150, 152, 156, 180, 186, 206, 210, 240]
61060338082919329390766447: [0, 20, 6, 0, 8, 8, 12, 0, 0, 24, 2, 0, 6, -18, -10, -24, 0]
6

Ой, а это черепашка нашла
45141432132285906365958697: [0, 30, 36, 46, 52, 70, 100, 114, 120, 132, 160, 162, 202, 204, 216, 234, 240]
45141432132285906365958697: [0, 24, 12, 10, -14, -14, 10, 0, 0, 6, 10, 6, 28, 0, 0, 0, 0]
7

Здесь тоже центральная тройка наклёвывается :)

И ещё, это с Ахиллеса-3

2615255120064581062794169: [0, 22, 30, 48, 64, 72, 100, 114, 120, 124, 160, 178, 184, 192, 204, 208, 240]
2615255120064581062794169: [0, 16, 6, 12, -2, -12, 10, 0, 0, -2, 10, 22, 10, -12, -12, -26, 0]
4
ID: 13612 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13703 - Posted: 20 Feb 2024, 8:08:27 UTC

А вот, наконец-то, и центральная тройка найдена жадным алгоритмом

2759179579215046026300353: [0, 14, 24, 30, 54, 78, 110, 114, 120, 126, 134, 170, 186, 204, 218, 224, 240]
2759179579215046026300353: [0, 8, 0, -6, -12, -6, 20, 0, 0, 0, -16, 14, 12, 0, 2, -10, 0]
7
ID: 13703 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13723 - Posted: 24 Feb 2024, 3:31:19 UTC
Last modified: 24 Feb 2024, 3:33:08 UTC

Жадным алгоритмом найдено неплохое приближение к ключевой 17-ке

287759664577066374552954733: [0, 18, 28, 30, 36, 84, 90, 114, 130, 148, 150, 156, 178, 204, 216, 228, 240]
287759664577066374552954733: [0, 12, 4, -6, -30, 0, 0, 0, 10, 22, 0, 0, 4, 0, 0, -6, 0]
9

В этом приближении центральный элемент не совпадает.
Получился оригинальный элемент спектра

1846
287759664577066374552954733

За ночь жадный алгоритм нашёл около 100 приближений, оригинальных среди них очень мало, в основном идут повторы.
Ну, всё приписываю к спектру приближений, повторы тоже интересны, они показывают географию поиска.
ID: 13723 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 13216
Credit: 0
RAC: 0
Message 13726 - Posted: 24 Feb 2024, 8:16:22 UTC
Last modified: 24 Feb 2024, 8:23:36 UTC

Неплохое приближение ещё найдено жадным алгоритмом

119948205416745318463015553: [0, 6, 24, 68, 78, 90, 104, 110, 126, 138, 156, 176, 188, 198, 230, 234, 240]
119948205416745318463015553: [0, 0, 0, 32, 12, 6, 14, -4, 6, 12, 6, 20, 14, -6, 14, 0, 0]
5

Приближение дало оригинальный элемент спектра

24577
119948205416745318463015553

Интересно: обратный элемент спектра 8190 не найден.
Посмотрите на вектора совпадений

8190
[1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1]
24577
[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1]

Да, элемент 8190 очень трудно найти, 14 правильных элементов!
ID: 13726 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : Cafe : Поиск ключевой 17-ки жадным алгоритмом


©2024 (C) Progger