A pontosan 10-hatvány számjegyből álló faktoriális értékek ritkák. Melyik a következő?

Írtam rá programot A Stirling formulával számolja a számjegyek számát:

lg n! ≈ n·lg(n/e) + lg(2π·n)/2

A program C-ben van, long double-vel, aminek 18 számjegy a pontossága, ezért csak 10^18-ig tud számolni. Addig nem volt egyetlen másik ilyen tulajdonságú faktoriális sem. Az utolsó számolás ez volt:

Number of digits (log10) of 61154108320430278! = 999999999999999984.312500

Number of digits (log10) of 61154108320430279! = 1000000000000000000.687500

Akkor lenne éppen 10^18 számjegy, ha 999999999999999 egész valahány tized lenne a logaritmus értéke.

(A 205022 kijött a programból is, azt így számolta ki:

Number of digits (log10) of 100000! = 456573.450900

Number of digits (log10) of 200000! = 973350.152357

Number of digits (log10) of 300000! = 1512851.169495

Number of digits (log10) of 210000! = 1026467.270894

Number of digits (log10) of 201000! = 978652.267367

Number of digits (log10) of 202000! = 983956.543049

Number of digits (log10) of 203000! = 989262.968708

Number of digits (log10) of 204000! = 994571.533752

Number of digits (log10) of 205000! = 999882.227693

Number of digits (log10) of 206000! = 1005195.040148

Number of digits (log10) of 205100! = 1000413.413776

Number of digits (log10) of 205010! = 999935.345348

Number of digits (log10) of 205020! = 999988.463215

Number of digits (log10) of 205030! = 1000041.581294

Number of digits (log10) of 205021! = 999993.775014

Number of digits (log10) of 205022! = 999999.086814

Number of digits (log10) of 205023! = 1000004.398617

)

Egyébként 10^18 környékén már ha eggyel növeljük a számot, akkor a faktoriálisa 16-17 számjeggyel lesz hosszabb, hiszen log10(61154108320430278) = 16,7864. Ezért annak a valószínűsége, hogy pont jó hossz jön ki, az ennek a reciproka, ami 5,95%, elég pici.

Ha lesz időm, átírom a programot "végtelen" pontosságú aritmetikára, akkor meg lehet nézni tovább is.

Itt fent a 18 jegyről szóló részt jól elrontotta a gyk: nem szereti az ismétlődő karaktereket, a sok 9-es meg a sok 0 végét levágta, pl. 16 darab 9-es helyett csak 6-ot adott vissza...

Viszont megvan a következő szám:

9474875935975369079112264502856242312901931449369611864801262070802451056152868441819310476933407516414459

Ez egy 106 jegyű szám, a faktoriálisa pedig 10^108 jegyű.

(Ebben a tartományban már 1% alatt van a valószínűsége, hogy pont 10 hatvány lesz a számjegyek száma.)

bc-ben írtam rá programot...

Ha egy üzlet egyszer beindul :)

Van egy újabb megoldás is:

929937062421139258908023507265616632776171326343214803405402921718472678875427171383081748029612986487661163

Ennek a faktoriálisa 10^110 jegyű.

Jobb a programod, mint az enyém :) Az enyém még csak 445-nél tart. Hogyan találtad?

Most megnéztem 613-ra, nekem is kijött ugyanaz a megoldás.

Biztos, hogy végtelen sok van ilyenekből. Bizonyítani nem igazán tudom, csak úgy, hogy annak a valószínűsége, hogy egy K (pontosabban 10^K) küszöb fölött nincs egy megoldás sem, az 0.

Ugyanis annak a valószínűsége, hogy NINCS 10^n számjegyű faktoriális, az körülbelül 1 - 1/n. Hogy nincs egy sem 10^(K+1) és 10^M között, az pedig:

  M

  Π (1 - 1/n) = K/M

n=K+1

aminek a határértéke M → ∞ esetén nulla.

Elkezdtem leprogramozni, de mire idenéztem már írtatok, bináris kereséssel kerestem én is. 1000-ig akartam futtatni, közben meg próbáltam optimalizálni, próbálkoztam végül rájöttem a megoldásra hogy kéne, aztán mentem aludni. Nem futott le 3 óra alatt 1000-ig hanem 789-ig futott, nem akartam úgy hagyni a gépet.

A megoldást a közelítő inverz faktoriális zárt alakban lévő formulájából vezettem, így egy megoldás jelöltet kellett visszatetszeni mindig és nem kellett bináris keresést csinálni. A korábbi 1000-ig lefutattam kicserélve a zárt formulára a bináris keresés helyett 1000-ig 1 perc alatt lefutott, 1300-ig 3 percen belül, lehet 2 perc nem mértem pontosan. Aztán egyre lassabb, majdnem 3 óra alatt futott le 3999-ig. Az inverz faktoriális számításánál sikerült kihasználni hogy csak 10 hatványokat keresek azaz átírni más alakba a formulát dehát kioptimalizálni. Kíváncsiságból kipróbáltam, ha rajta múlna kb 10 másodperc alatt végezne 3999-ig, azaz visszatesztelés nélkül, de vissza is kell tesztelni Stirling formula lassít sokat rajta. Végig magas pontosságot használtam.

Talált megoldások az eddigieken felül:

10^1453 -> 6 899 385 154 554 652 039 533 333 598 705 892 188 455 428 054 842 788 147 502 442 539 238 742 229 042 344 339 112 456 992 686 417 253 185 865 847 359 961 619 438 727 321 736 804 010 943 229 224 697 420 630 107 826 870 407 723 337 936 709 672 214 182 963 368 884 691 020 253 549 970 069 362 892 347 271 248 797 398 852 373 265 427 432 558 079 623 045 306 193 022 475 324 221 543 596 382 109 306 178 936 616 826 719 753 121 144 087 389 773 729 453 356 874 402 521 199 774 262 291 666 321 730 382 907 996 934 774 998 494 937 632 386 676 593 533 597 115 240 491 889 952 753 992 393 180 021 703 815 851 993 285 463 716 445 722 396 429 679 699 588 979 769 073 935 158 886 887 697 817 128 052 699 056 313 333 630 172 074 263 327 264 534 565 653 289 444 393 979 836 882 040 940 696 433 193 574 381 690 441 531 000 707 946 840 859 961 047 412 516 003 448 828 769 633 311 298 825 544 540 163 817 462 788 156 812 697 093 556 072 487 736 408 071 808 021 608 564 248 529 205 029 539 891 277 367 522 412 646 589 824 672 768 296 108 848 896 247 245 308 449 685 053 901 233 874 628 930 884 566 908 514 130 567 602 182 184 708 384 983 153 045 055 062 247 559 187 255 651 459 747 979 640 072 074 507 484 505 339 725 565 302 221 548 062 629 120 797 913 959 883 971 442 043 877 800 924 815 149 751 860 484 337 801 122 886 471 444 213 268 371 986 336 467 512 425 130 398 330 067 252 664 077 504 591 831 520 570 667 415 894 018 831 108 509 501 378 689 950 326 992 369 749 346 049 290 604 984 909 730 660 586 591 492 254 111 376 328 966 535 941 641 832 608 061 291 104 172 684 289 625 537 986 919 461 349 378 256 959 569 561 631 300 422 694 064 288 936 428 949 762 654 411 591 008 138 118 327 883 733 211 498 788 196 765 890 235 764 917 466 343 214 740 395 825 760 238 740 133 978 366 858 761 869 030 456 687 426 075 146 301 504 738 264 113 716 140 181 451 172 223 792 203 874 073 953 170 230 741 607 029 685 392 670 997 866 329 242 049 032 997 904 496 479

10^1792 -> 5 591 861 455 670 704 690 275 016 490 228 401 713 821 201 765 448 160 348 243 913 782 167 515 130 208 045 842 321 873 843 074 169 060 691 438 810 499 371 821 844 012 017 156 758 122 494 305 064 937 851 349 132 184 365 939 315 494 265 707 793 596 574 007 891 028 783 638 438 387 335 778 077 100 622 049 071 371 503 640 151 639 062 183 116 235 592 094 223 183 604 043 073 719 985 046 028 522 478 898 055 228 767 815 823 784 831 962 340 788 700 180 830 778 544 473 898 342 734 523 019 844 361 410 503 614 697 892 762 587 573 103 879 536 235 428 290 527 812 179 377 223 063 195 952 107 935 184 076 781 409 306 293 724 448 777 181 059 219 425 781 627 536 332 162 659 275 657 082 638 327 228 965 716 647 061 090 388 436 089 069 621 112 920 784 891 695 919 186 915 610 005 198 252 283 402 225 633 375 995 245 366 526 329 349 376 311 164 833 403 386 337 623 703 853 781 745 331 182 991 915 090 832 034 786 648 368 188 769 389 785 790 037 245 619 345 947 556 967 480 540 436 968 689 589 818 278 635 590 344 112 635 915 744 429 566 296 051 421 104 758 239 164 382 172 274 838 687 843 112 853 339 267 997 357 170 459 376 012 428 825 559 471 269 040 771 681 584 510 435 019 480 815 615 570 380 284 756 446 321 418 790 998 756 897 069 801 503 717 733 209 313 557 146 624 162 275 532 221 134 750 158 095 282 284 462 644 302 789 830 130 819 405 116 575 636 774 347 902 609 650 613 313 895 289 724 561 958 918 900 357 023 167 716 456 730 128 049 379 705 264 612 233 479 889 425 527 767 339 496 686 155 729 357 090 244 368 738 184 051 244 906 219 923 366 347 711 374 014 774 385 818 501 022 252 761 204 851 905 630 069 385 046 322 180 257 475 611 469 471 813 996 360 338 306 663 094 987 360 855 487 284 617 637 530 178 400 802 460 209 409 412 050 356 475 904 838 342 278 307 538 734 621 058 020 756 730 341 066 663 899 553 477 604 572 554 765 919 231 356 374 948 153 904 379 918 887 870 254 743 833 152 760 684 726 269 377 257 338 600 977 514 730 008 383 997 081 035 683 863 003 526 938 686 995 162 551 668 836 377 894 680 767 920 482 787 660 602 699 850 994 226 631 025 677 516 440 928 336 433 045 867 634 320 390 627 664 831 780 022 282 196 241 920 795 304 187 617 591 455 179 920 396 487 380 577 797 272 168 122 969 370 277 701 886 408 604 037 961 927 394 808 058 395 883 845 696 532 385 303 239 998 011 981 660 223 512 838 463 004 514 063 371 095 706 891 302 834 784 492 391 128 573 683 289 676 781

10^1840 -> 5 445 728 044 180 266 742 832 941 291 099 473 945 225 760 075 017 344 441 783 432 542 344 541 612 119 319 337 482 833 138 518 781 660 899 760 271 684 219 880 208 901 633 536 770 594 289 010 958 989 635 640 627 067 719 751 208 532 696 616 276 084 347 200 254 007 967 333 656 426 416 735 581 851 343 030 843 130 139 291 043 361 855 687 152 388 510 212 436 927 694 514 100 060 323 756 985 475 067 465 123 388 065 844 953 244 067 628 563 932 518 870 184 509 282 663 864 075 934 649 470 022 670 393 459 525 960 834 482 881 827 363 472 976 235 630 076 205 712 865 693 046 942 976 745 575 257 667 841 408 449 149 432 800 361 629 832 446 278 150 010 606 249 540 573 447 350 684 776 445 909 256 167 589 372 976 194 343 811 488 786 059 223 709 405 160 191 648 671 543 989 005 854 715 162 833 854 507 601 863 283 339 116 705 335 245 573 116 264 475 618 544 827 112 960 958 116 793 762 225 380 618 387 144 920 445 070 251 115 596 241 433 335 098 319 776 223 191 002 679 060 585 341 412 642 541 400 323 153 254 629 396 423 704 452 942 525 840 760 524 909 280 520 306 324 234 350 267 919 082 081 896 860 094 365 526 282 373 885 365 505 668 012 800 521 820 845 159 987 826 017 007 484 807 743 198 772 421 170 008 770 116 456 513 438 192 077 094 808 421 143 518 266 366 783 437 412 649 798 375 904 552 168 337 198 118 637 546 179 526 947 415 456 821 115 410 322 121 417 960 093 824 774 943 912 214 993 456 072 990 283 489 373 251 208 991 501 673 500 882 114 931 765 441 407 545 701 253 458 168 337 725 089 784 367 924 763 801 679 359 169 647 876 114 762 731 559 625 697 548 344 884 390 513 517 456 780 984 277 828 834 047 300 096 023 467 995 732 193 305 552 574 870 601 907 691 870 778 817 975 521 220 096 234 455 434 267 912 092 428 249 585 771 066 273 855 726 409 573 429 203 410 318 299 423 468 589 940 365 084 546 091 167 281 615 533 996 526 088 117 438 362 604 469 641 575 757 147 985 287 177 964 433 216 824 945 185 032 208 677 146 599 089 447 602 181 428 470 669 734 923 163 130 164 921 429 428 494 374 039 673 963 794 454 462 377 822 906 744 981 899 522 987 406 781 853 856 175 864 684 568 856 595 078 968 564 788 741 215 944 426 768 645 372 037 186 345 015 742 876 963 107 437 167 855 263 511 796 779 225 844 631 620 117 733 253 751 480 923 602 365 574 379 128 715 998 339 502 988 223 397 896 798 164 989 626 001 158 457 290 806 865 094 964 630 143 256 870 468 834 499 987 457 000 654 574 031 621 306 449 408 155 846 047 423 495 135 953 087 352 238 418 221

10^2902 -> 3 450 532 282 192 962 117 262 539 916 573 314 156 024 979 136 276 733 058 660 653 747 686 851 731 047 114 601 952 362 764 635 750 477 915 530 704 039 254 545 307 522 029 651 680 828 592 890 044 879 442 256 886 774 003 905 271 323 719 353 924 803 723 580 190 769 568 239 623 702 485 309 098 150 927 607 210 124 315 225 811 188 287 939 569 482 384 599 199 664 082 780 080 329 404 875 128 515 364 167 809 682 311 453 501 272 787 909 614 670 848 011 373 639 186 045 654 491 465 296 049 963 712 129 361 805 124 815 802 876 197 573 164 876 255 485 243 291 393 999 184 548 611 226 251 312 341 148 065 551 490 393 489 179 293 435 608 757 821 046 598 875 777 167 804 032 947 698 848 274 518 265 599 764 702 983 677 687 754 982 773 691 859 813 426 521 715 630 068 930 846 369 309 722 354 087 364 879 123 084 853 063 918 191 777 795 451 005 355 227 625 212 968 548 770 251 250 272 735 184 315 499 131 567 760 600 424 079 673 943 672 156 981 446 586 657 813 749 278 398 973 092 962 946 896 907 067 677 060 828 513 821 212 486 923 505 473 104 849 346 600 549 998 198 090 372 860 083 554 351 846 206 125 198 439 450 308 967 358 676 983 275 819 188 654 733 333 699 241 931 056 653 400 203 983 280 532 743 289 618 024 438 633 687 285 468 614 371 821 207 553 281 994 636 473 396 118 631 611 854 308 763 384 858 458 539 136 126 720 350 960 395 428 496 936 178 682 375 195 719 758 769 158 081 221 092 775 355 231 210 780 430 505 484 624 244 297 700 926 472 032 335 476 532 928 618 940 659 974 302 189 482 979 425 118 067 246 012 149 882 684 022 715 713 356 893 651 698 392 368 067 570 685 026 491 625 184 458 023 618 977 420 714 364 562 240 278 596 478 695 119 587 359 190 558 284 442 252 247 279 139 786 686 159 252 864 907 681 656 285 816 377 635 750 602 852 603 117 733 173 386 282 818 496 389 899 727 403 927 479 774 827 720 478 868 553 851 744 745 789 436 199 747 471 658 168 811 992 973 629 435 253 887 328 347 049 211 482 681 181 562 807 625 310 218 362 732 522 900 474 925 106 049 390 167 812 119 027 588 629 134 154 458 376 027 374 121 799 198 920 970 067 267 801 979 746 543 960 644 550 177 403 519 774 455 799 058 740 505 696 508 177 421 555 769 927 967 565 460 327 683 951 579 240 860 982 765 104 041 139 507 437 808 948 179 041 335 292 396 010 582 708 472 773 938 577 434 641 174 144 524 900 282 759 894 049 432 035 391 187 896 565 010 551 591 325 618 568 073 178 449 856 644 070 014 549 600 205 883 458 953 058 978 123 671 229 101 111 400 433 073 165 316 773 840 488 269 525 372 492 039 067 644 601 427 600 479 107 911 109 134 787 953 347 939 173 542 756 802 863 207 657 273 610 963 448 412 560 861 818 725 356 652 037 158 375 570 134 748 537 996 490 220 053 657 653 143 907 996 245 950 589 838 959 480 835 550 713 024 922 554 112 551 993 658 255 152 963 781 285 667 474 265 731 772 601 066 667 092 075 550 181 101 578 196 685 214 930 437 314 464 168 059 915 718 794 998 147 811 170 191 794 599 459 958 873 777 057 487 501 893 074 201 787 233 147 086 031 771 044 163 670 782 619 439 397 084 577 237 915 808 340 128 976 998 485 265 807 805 197 004 720 265 499 005 567 693 428 624 869 871 509 482 554 162 310 578 232 114 889 204 697 642 471 520 863 404 798 355 957 030 592 048 520 471 160 384 535 711 472 214 849 001 988 349 552 709 593 918 099 423 969 014 357 656 531 592 491 267 345 045 505 318 117 638 624 233 584 264 430 546 982 731 673 119 890 000 602 293 589 991 561 179 042 036 198 616 520 531 828 650 666 580 497 023 951 602 444 032 608 933 447 196 856 147 399 620 716 556 748 365 399 337 114 108 961 715 965 482 929 376 241 061 954 454 978 413 664 125 767 774 310 741 691 306 974 083 873 579 650 659 240 000 444 862 265 818 589 781 191 992 448 510 841 667 177 344 126 235 982 838 102 356 655 420 578 082 616 632 146 051 993 527 439 971 967 977 670 703 539 579 714 733 868 022 301 445 507 176 472 234 848 761 189 723 405 118 511 874 563 040 768 031 590 449 720 860

"kb 10 másodperc alatt végezne 3999-ig, azaz visszatesztelés nélkül"

Bocsi ezt benéztem, ez nem igaz.