Al Zimmerman - Delacorte Numbers

[Yadryara]

Pavlovsky в сообщении #937268 писал(а):

С ростом N таких примеров становится очень много.
Например
для N=7
$|M_k|=2$ p=17,19,23

Так это только подходящие простые числа. В этом посте Вами почему-то не совершенно не указаны значения $D_p$ для максимума.

[dimkadimon]

sevir в сообщении #937297 писал(а):

А Вы не могли бы привести некоторые решения для $N > 10$: я заметил особенность своего алгоритма - чем больше $N$, тем меньше отличается мое решение, полученное практически мгновенно от вашего. Например, для $N = 10$ мне машина сразу выдала решение $592831$. Но $592831 / 593249 = 0,9993$. Это я к тому, что стоит ли мне дальше "огород городить".

592831 совсем неплохо для такого быстрого результата. Правда с тех пор я немного улучшил N=10 MAX. Советую сначала загрузить все решения (когда сайт заработает) и посмотреть насколько каждое отстает от лидеров. А потом можно будет решить какое лучше улучшать - то которое даст больше всего баллов.

Для сравнения у меня N=27: MIN=110983910, MAX=343833681.

-- 28.11.2014, 16:08 --

Herbert Kociemba в сообщении #934878 писал(а):

For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.

Strange I am getting quite good improvements with the new algorithm. In fact I reverted back to a simpler method, which I thought was rubbish. I guess before I was running it for 5 minutes and when it didn't give improvements I terminated it. But now with a 30-50 speed-up I get almost immediate improvements and it is encouraging me to continue using the method.

[sevir]

dimkadimon в сообщении #937307 писал(а):

[Для сравнения у меня N=27: ... MAX=343833681.

Мой мгновенный результат 343474617 меня не впечатлил:
343474617/343833681=0,9989557 (подскажите, как вывести грамотно таблицу большой ширины):
420 360 624 728 330 400 460 132 90 455 705 651 328 138 368 130 688 135 665 198 490 585 440 510 468 700 540
504 240 462 570 476 192 372 322 196 418 658 410 539 207 712 678 729 54 275 112 176 228 696 264 520 450 672
432 300 408 340 160 564 290 152 258 75 172 143 18 77 212 116 507 488 366 363 110 165 276 294 315 546 648
684 288 448 608 492 325 430 584 319 145 295 177 155 524 291 237 716 301 44 52 686 175 105 357 532 378 612
280 308 444 676 710 642 477 335 85 652 327 94 703 34 26 58 123 39 55 299 657 425 494 429 620 640 594
120 352 345 512 472 242 221 388 206 533 14 371 511 415 517 289 134 589 361 309 187 50 575 78 351 666 693
384 500 70 370 45 404 57 62 497 535 417 698 447 538 6 519 723 302 334 118 267 628 603 426 682 544 126
150 609 318 279 287 625 158 515 49 543 566 19 347 353 157 37 458 633 427 629 46 51 203 632 102 484 708
567 459 296 81 556 667 481 718 386 622 23 137 61 191 281 127 59 71 466 501 194 178 436 64 147 442 84
286 518 568 95 129 218 655 454 337 113 163 5 449 443 1 257 7 227 398 394 565 274 16 305 261 174 238
464 36 664 724 15 451 478 614 79 197 2 569 461 677 457 523 619 263 47 586 717 707 27 412 536 506 555
561 402 28 213 82 445 453 542 67 251 503 593 587 491 673 409 521 109 43 554 446 505 527 596 369 171 190
646 498 161 508 611 669 662 317 107 661 499 701 467 727 389 659 599 691 131 179 626 685 166 141 91 530 375
496 424 119 303 551 699 597 229 13 379 709 617 373 463 509 631 719 541 151 29 579 254 146 249 692 606 645
513 438 549 265 346 413 573 313 277 367 607 601 397 613 643 401 577 563 53 331 634 679 377 93 20 153 162
399 63 387 253 403 298 482 89 73 3 487 653 647 439 431 571 421 271 307 502 635 553 713 428 323 248 483
272 104 711 452 111 121 537 422 293 17 547 683 419 433 557 479 211 31 4 382 695 689 38 205 332 184 627
486 88 725 268 548 391 485 381 526 167 139 193 383 641 223 199 311 181 359 25 559 278 362 259 376 48 72
522 354 610 341 217 69 671 581 9 101 173 83 149 269 11 283 233 241 674 623 74 86 159 284 30 592 60
220 182 42 316 188 235 22 314 411 8 514 97 41 239 529 349 103 489 10 437 649 21 65 99 250 435 416
675 414 310 333 92 209 247 202 545 365 471 591 562 706 694 393 687 395 697 226 321 12 243 574 621 96 558
320 348 297 170 534 68 343 668 493 583 721 214 469 262 681 122 473 326 183 219 355 148 474 434 285 392 144
495 324 156 441 186 117 98 722 215 125 604 358 106 169 407 142 201 33 133 292 338 256 470 100 636 572 210
390 552 260 273 615 598 114 618 124 32 578 185 339 87 35 115 329 76 164 605 246 670 154 405 342 168 690
396 702 350 306 200 255 266 602 245 24 236 423 244 356 639 531 654 637 590 374 638 304 108 580 704 680 560
336 588 270 525 234 380 715 663 230 344 56 40 582 475 128 222 136 282 232 195 225 516 650 312 616 576 600
630 528 714 180 216 550 726 224 231 385 208 80 465 66 406 656 189 595 204 644 140 364 456 252 480 660 720

[Pavlovsky]

Yadryara в сообщении #937305 писал(а):

Так это только подходящие простые числа. В этом посте Вами почему-то не совершенно не указаны значения $D_p$ для максимума.

А зачем вам еще примеры? Ведь истинность

Цитата:

Утверждение. Пусть у нас есть два простых числа $p_1 < p_2$, такие что $\left\lfloor\frac{N^2}{p_1}\right\rfloor=\left\lfloor\frac{N^2}{p_2}\right\rfloor$ Тогда в максимальном решении, $D_{p_1} \le D_{p_2}$. Где $D_{p_1} (D_{p_2})$ сумма квадратов расстояний между числами кратными $p_1 (p_2)$

легко доказывается. Пусть в решении $D_{p_1} > D_{p_2}$. Тогда поменяв местами числа $ip_1 <-> ip_2$, где $i=[1,\left\lfloor\frac{N^2}{p_1}\right\rfloor]$ мы получим решение с большим числом Делакорта.

[sevir]

sevir в сообщении #937340 писал(а):

dimkadimon в сообщении #937307 писал(а):

[Для сравнения у меня N=27: ... MAX=343833681.

Мой мгновенный результат 343474617 меня не впечатлил:
343474617/343833681=0,9989557

Понял. где "затык": для $N= 27$ Вас обошел (для $N = 10$ пока не получается). Спасибо за информацию.

[Yadryara]

Pavlovsky в сообщении #937354 писал(а):

Пусть в решении $D_{p_1} > D_{p_2}$. Тогда поменяв местами числа $ip_1 <-> ip_2$, где $i=[1,\left\lfloor\frac{N^2}{p_1}\right\rfloor]$ мы получим решение с большим числом Делакорта.

Если не затруднит, поподробней, пожалуйста.

[dimkadimon]

sevir в сообщении #937372 писал(а):

sevir в сообщении #937340 писал(а):

dimkadimon в сообщении #937307 писал(а):

[Для сравнения у меня N=27: ... MAX=343833681.

Мой мгновенный результат 343474617 меня не впечатлил:
343474617/343833681=0,9989557

Понял. где "затык": для $N= 27$ Вас обошел (для $N = 10$ пока не получается). Спасибо за информацию.

Уже?! Круто! Я днем и ночью гонял комп чтобы получить этот результат. Значит ваш метод хороший. А это мгновенный результат? Если да, то это полностью меняет игру!

[Pavlovsky]

Вот формула whitefox

$$D=\frac{n^4(n^2-1)}6+\sum\limits_{k=2}^{\frac{n^2}2}\varphi(k)\cdot D_k$$

Рассмотрим только два члена суммы $k=p_1$ и $k=p_2$

$$\varphi(p_1)\cdot D_{p_1}+\varphi(p_2)\cdot D_{p_2} = (p_1-1)\cdot D_{p_1}+(p_2-1)\cdot D_{p_2}$$

После замены чисел $ip_1 <-> ip_2$, где $i=[1,\left\lfloor\frac{N^2}{p_1}\right\rfloor]$ это выражение станет таким

$$(p_1-1)\cdot D_{p_2}+(p_2-1)\cdot D_{p_1}$$

При условии $p_1 < p_2$ и предположении $D_{p_1} > D_{p_2}$ выражение после замены будет больше, чем до замены.

[Yadryara]

Pavlovsky в сообщении #937397 писал(а):

При условии $p_1 < p_2$ и предположении $D_{p_1} > D_{p_2}$ выражение после замены будет больше, чем до замены.

Это понятно, но должен ли этот статус-кво непременно сохраняться и в максимальном решении, в котором многие другие $\varphi(k)\cdot D_k$ причудливым образом переплетены друг с другом?

Надо ещё раз подумать, возможно, Вы правы. Это может работать именно для простых чисел. Чтобы лучше убедиться, надо исследовать старшие порядки.

[Pavlovsky]

Специфика замены $ip_1 <-> ip_2$, где $i=[1,\left\lfloor\frac{N^2}{p_1}\right\rfloor]$ такова, что в формуле whitefox изменяются только $\varphi(p_1)\cdot D_{p_1}+\varphi(p_2)\cdot D_{p_2}$ Значения $\varphi(k)\cdot D_{k}$ для $k \ne p_1,p_2$ остаются неизменными.

-- Пт ноя 28, 2014 15:59:33 --

Нарисовался алгоритм частичной оптимизации.

Пусть у нас есть решение. Выпишем k пар чисел $(a_i,b_i)$, где $i=[1,k]$, все числа $a_i,b_i$ различны и удовлетворяют условию:
Для всех $i=[1,k]$ $\frac{a_i}{gcd(a_i,b_i)}=p_1$ $\frac{b_i}{gcd(a_i,b_i)}=p_2$, где $p_1,p_2$ простые числа.

Реалезуем алгоритм, где разрешены только замены $a_i <-> b_i$. Тогда пересчет суммы Делакорта и собственно замена чисел будет выполняться за $O(1)$ операций.

Вместо пар чисел $(a_i,b_i)$, можно использовать тройки, четверки и т.д.

[sevir]

dimkadimon в сообщении #937395 писал(а):

А это мгновенный результат? Если да, то это полностью меняет игру!

Около 40 минут на 20 ядрах. И потом, для $N = 10$ не удается Вас обойти: вероятностные методы лучше работают на больших порядках.

[dimkadimon]

sevir в сообщении #937415 писал(а):

dimkadimon в сообщении #937395 писал(а):

А это мгновенный результат? Если да, то это полностью меняет игру!

Около 40 минут на 20 ядрах. И потом, для $N = 10$ не удается Вас обойти: вероятностные методы лучше работают на больших порядках.

Спасибо за пояснение. Еще вопросик есть. А это только для максимум работает? Что значит "вероятностные методы"?

[sevir]

dimkadimon
К минимуму я еще не прикасался. И это не генетические алгоритмы.

[whitefox]

Может кому пригодится: статья о квадратичной задаче о назначениях.

[sevir]

dimkadimon в сообщении #937307 писал(а):

Herbert Kociemba в сообщении #934878 писал(а):

For n=27 the program runs 50x faster than before. So the the algorithm of whitefox is really a big progress. But I did not get better solutions.

Strange I am getting quite good improvements with the new algorithm. In fact I reverted back to a simpler method, which I thought was rubbish. I guess before I was running it for 5 minutes and when it didn't give improvements I terminated it. But now with a 30-50 speed-up I get almost immediate improvements and it is encouraging me to continue using the method.

Herbert Kociemba хотел этим сказать, что очень хорошие результаты не помогают улучшить даже формулы whitefox'а. У меня подозрение, что он имеет доступ к кластеру, тем более, что он писал о возможности использования хорошего "железа".