Uniform twelve-step Syracuse descent on 1602 fifteen-branch progressions modulo
Provedsyracuse_descent_fifteen_mod16_mod1048576_step12Let be the odd part of (the Syracuse map, syracuseStep on the platform), and let denote twelve successive applications. Let be the explicit list of 1602 distinct residues modulo enumerated in the formal statement. For every natural number ,
The statement is uniform over 1602 infinite arithmetic progressions; it is not a check of least representatives. Every listed residue satisfies and lies in a class left open by the fifteen-branch residual descent theorem modulo . That residual consists of 4723 classes modulo , hence classes modulo , and is the set of those lifts on which the first twelve Syracuse steps divide by exactly in total. Since , the twelfth iterate on such a class is an affine function of with slope .
The theorem removes of the density of the fifteen-branch residual and is the certified half of its refinement from modulus to . No class of that residual is certifiable at modulus .
Formalization Note. The residue table is a literal List ℕ. The recursion-depth option only permits elaboration of the long literal.
import Definitions.Def_syracuseStep import Mathlib.Logic.Function.Iterate set_option maxRecDepth 16384
theorem syracuse_descent_fifteen_mod16_mod1048576_step12 (n : ℕ)
(h : n % 1048576 ∈ ([239, 1439, 2175, 2255, 2511, 2879, 3199, 3279, 3871, 4351, 4511, 5247, 5679, 7583,
7615, 7999, 8319, 8607, 8751, 9023, 9343, 10687, 11471, 11711, 12847, 13871, 14463, 15231,
15807, 16079, 16799, 16943, 17215, 17375, 17535, 18127, 18303, 18879, 20223, 21247, 21375, 22223,
23087, 23295, 23423, 23519, 25631, 26319, 26495, 27391, 27679, 28367, 29727, 31279, 31439, 31487,
32047, 32639, 32799, 33535, 35327, 35871, 36895, 37359, 37375, 37583, 39423, 40127, 40239, 40447,
41455, 42495, 44527, 45087, 45551, 45567, 46271, 46383, 46543, 46591, 47599, 50639, 50671, 51263,
51695, 52463, 54463, 54783, 55359, 56559, 56815, 58751, 58831, 59455, 59855, 59887, 61087, 64575,
64895, 65599, 65647, 65775, 68047, 68287, 68415, 68735, 69631, 69743, 70655, 70783, 71039, 71679,
72815, 73791, 73839, 73951, 74559, 74719, 74751, 74879, 75887, 78847, 78959, 79407, 79983, 79999,
80095, 80255, 80575, 81343, 82479, 82751, 82911, 83071, 84415, 85103, 85711, 87199, 88175, 88623,
88783, 89055, 90271, 90863, 90879, 91855, 93903, 93935, 96575, 96815, 96975, 97023, 97919, 98031,
98943, 99055, 99071, 99487, 99967, 102127, 103039, 103119, 104927, 106111, 107135, 107999, 108271, 108863,
109183, 111087, 112095, 112255, 113119, 113135, 113279, 115647, 116191, 116463, 117231, 117695, 121471, 121791,
122335, 122351, 122927, 124991, 125423, 125887, 127023, 127935, 129231, 130527, 131007, 131135, 131295, 134399,
135215, 135375, 136239, 136575, 136607, 137151, 137471, 139327, 139375, 139487, 140543, 140703, 141423, 141519,
141567, 143775, 144383, 144431, 144799, 145519, 145631, 145791, 146111, 146847, 149759, 149919, 150511, 150639,
150735, 150943, 151711, 153711, 154607, 155807, 156063, 158703, 159135, 162687, 163823, 164591, 164847, 164895,
165023, 165759, 167551, 167663, 168831, 168991, 169599, 169855, 171647, 172063, 172671, 173039, 173087, 173807,
174399, 174719, 175135, 177791, 178047, 178207, 178655, 178799, 178815, 179231, 179503, 181727, 181759, 181999,
182895, 183599, 184351, 184831, 185279, 185807, 186991, 187007, 187423, 187583, 187871, 188351, 188463, 190111,
191423, 191727, 191791, 191951, 192111, 192559, 192815, 193135, 193183, 193471, 193727, 194047, 194799, 195823,
195839, 196063, 196543, 197279, 197887, 198095, 198303, 199919, 199935, 200751, 201007, 201327, 201375, 201775,
202687, 202991, 203007, 206079, 207055, 207103, 207311, 207519, 209967, 210047, 210335, 212383, 214575, 215295,
215711, 215871, 216271, 216479, 216623, 218559, 219583, 220719, 221599, 221631, 222015, 222175, 222335, 224127,
224239, 224671, 224815, 225727, 226175, 226271, 226863, 228223, 229823, 229935, 230383, 231167, 231295, 231871,
233167, 234367, 234463, 235375, 235391, 235487, 236079, 236239, 238335, 238575, 238623, 239311, 239359, 239471,
240335, 240671, 243567, 243583, 243679, 244479, 244767, 244927, 245039, 246271, 248527, 248687, 249135, 249711,
249759, 249887, 250367, 252399, 252527, 252959, 253119, 253855, 257327, 257903, 257951, 258351, 258671, 259263,
259583, 263071, 263631, 263839, 264095, 264687, 265455, 266543, 266863, 266911, 268527, 272287, 272447, 272847,
273055, 273215, 275135, 278047, 278207, 278591, 278751, 280687, 281247, 281407, 281599, 282143, 282303, 282847,
283327, 284207, 286239, 286399, 287279, 287551, 287711, 287871, 289215, 290351, 290975, 291039, 291359, 291807,
292063, 292383, 292399, 292543, 292975, 294047, 294607, 295071, 295359, 295471, 296655, 297407, 298703, 298751,
299167, 299759, 299775, 299999, 300255, 300575, 300735, 301023, 301615, 301775, 301807, 301823, 302239, 303423,
303871, 304847, 304895, 305871, 305903, 306495, 309103, 309215, 309999, 310015, 310591, 311615, 312047, 313823,
313983, 314063, 314687, 315119, 315247, 315871, 317055, 319967, 320831, 321263, 323439, 323487, 324063, 326111,
326271, 327727, 329023, 329183, 329631, 329791, 330223, 332735, 333871, 334623, 335103, 335327, 335807, 337823,
337983, 338719, 338879, 339199, 339903, 340015, 342271, 342815, 343295, 344127, 344287, 345343, 347935, 348095,
348383, 348415, 348863, 348959, 349231, 349439, 350207, 351647, 351775, 351935, 354559, 356575, 357151, 357599,
357631, 357919, 358079, 358511, 363391, 363935, 364703, 365791, 366111, 366271, 367487, 367775, 369391, 370559,
371583, 371695, 372463, 373631, 375535, 376703, 377151, 377583, 377727, 377839, 378495, 379935, 380223, 380655,
382591, 382847, 383455, 384303, 385535, 385919, 386367, 386527, 386799, 388607, 389599, 389631, 390447, 391647,
391807, 392223, 392383, 393727, 394175, 394559, 394719, 396223, 396479, 396591, 396799, 398271, 399007, 399983,
400863, 401055, 401343, 402671, 403695, 404415, 404671, 405151, 405439, 405551, 405695, 405743, 405807, 406127,
408351, 408831, 409247, 409839, 410879, 411295, 413631, 413887, 413935, 414367, 414495, 414767, 414975, 415983,
416895, 419967, 420095, 420511, 420671, 422687, 423167, 424063, 424767, 425087, 426975, 428159, 429039, 429471,
429503, 431663, 432959, 433119, 433871, 433983, 434303, 434735, 436671, 437119, 437231, 437695, 437807, 437967,
438015, 438831, 439039, 439167, 439263, 440063, 441039, 442063, 442175, 442495, 442815, 443135, 443263, 443375,
444111, 446207, 447023, 447183, 447231, 448207, 448383, 448479, 449279, 451455, 452351, 453327, 453375, 456399,
456559, 457327, 457759, 457919, 459247, 459263, 461567, 462015, 462127, 462319, 462335, 462703, 465519, 466415,
467439, 468639, 470207, 470511, 470943, 471231, 471343, 471663, 471711, 473327, 474783, 476543, 476655, 476831,
477087, 477247, 479423, 479471, 479903, 480639, 481343, 481519, 483551, 484031, 484735, 484847, 486047, 486079,
486207, 487535, 489471, 489535, 489695, 489855, 490175, 490303, 490559, 490607, 490623, 490879, 492543, 493103,
493695, 494271, 494703, 495151, 495727, 495839, 496319, 497087, 497199, 497663, 498111, 498495, 498751, 498799,
499071, 499231, 499391, 499519, 499839, 500159, 500271, 500735, 501919, 502207, 502943, 503231, 503343, 504367,
504799, 504943, 504991, 505055, 505375, 505535, 507599, 507647, 507711, 508031, 508351, 509087, 509647, 509695,
511743, 512319, 512559, 512767, 513135, 513183, 513743, 513903, 514015, 514367, 514815, 515231, 516847, 517759,
517887, 518463, 518863, 518911, 519919, 520831, 521855, 521935, 522095, 522559, 522991, 524015, 524607, 525951,
527103, 527679, 528239, 528287, 529023, 530911, 532207, 532975, 533439, 533823, 533983, 536047, 536479, 537055,
537535, 538079, 540607, 541631, 542191, 542623, 542783, 543679, 546271, 546751, 546879, 547023, 547775, 550143,
550271, 550383, 551119, 552895, 553663, 555071, 555215, 555807, 555967, 556095, 556415, 556575, 556735, 558495,
559103, 559807, 560127, 560335, 561263, 561359, 561375, 561567, 561855, 561951, 562431, 563199, 564287, 564335,
564607, 564767, 564927, 565663, 566271, 566687, 569551, 569759, 570479, 570591, 570911, 571071, 572575, 575903,
576495, 578287, 578431, 578671, 578719, 580335, 580591, 580767, 581951, 582383, 584095, 585023, 585455, 586783,
588095, 588527, 588783, 589551, 589807, 589855, 590143, 590719, 591487, 592351, 593215, 593951, 594399, 594559,
594975, 596447, 596479, 597183, 597503, 597743, 597999, 598047, 599359, 599519, 599551, 602591, 603327, 603599,
603615, 603647, 604191, 604783, 607167, 607695, 607743, 608879, 609215, 609471, 609791, 611791, 611807, 612383,
613151, 613311, 613615, 616095, 616911, 617071, 617935, 618095, 618431, 618687, 619167, 620751, 620783, 621343,
621503, 621807, 622239, 623263, 625471, 625791, 626127, 626287, 626895, 626927, 627487, 627839, 627967, 631455,
631615, 631935, 632223, 632367, 635087, 635295, 636031, 636351, 636463, 637375, 637759, 638079, 638399, 639535,
640559, 641151, 641439, 641471, 642031, 642607, 644543, 645567, 645679, 646127, 646703, 646975, 647295, 647615,
648911, 649631, 650687, 651711, 651823, 654079, 654319, 654895, 655343, 656255, 657151, 659903, 660511, 661199,
661359, 663535, 663583, 665455, 666367, 667135, 668143, 669727, 670191, 670319, 673279, 673647, 674287, 674415,
674671, 675007, 675327, 675743, 677327, 677535, 677919, 678383, 679583, 679839, 680431, 681199, 681631, 682047,
682223, 682607, 682863, 683471, 683503, 683631, 684223, 684271, 684703, 686319, 687343, 687775, 688031, 688191,
688799, 689055, 689647, 691663, 691823, 692463, 694335, 695423, 696431, 696991, 697247, 697727, 698479, 698495,
699391, 701119, 701439, 701567, 702575, 703295, 703551, 703615, 703871, 704031, 704191, 705983, 706095, 706671,
706687, 707263, 707583, 708031, 708127, 708143, 708287, 708719, 710079, 711103, 711791, 712239, 712511, 712831,
712863, 713151, 713727, 716223, 716319, 716479, 717247, 717343, 717359, 717551, 717935, 718591, 720031, 720431,
721055, 721647, 722687, 724719, 725439, 725535, 725743, 726175, 726735, 726895, 727791, 728703, 729407, 729727,
730863, 730991, 731615, 731775, 731887, 731903, 732479, 735551, 735711, 735871, 736575, 737007, 737775, 738783,
739183, 739807, 739967, 740079, 740207, 740847, 741279, 741855, 742015, 743919, 744767, 744927, 745375, 745519,
745951, 745967, 748399, 748479, 749039, 749615, 751071, 753567, 753711, 754143, 754591, 755071, 755183, 756991,
758831, 759855, 759871, 760063, 760607, 760767, 762559, 762783, 763263, 764159, 764607, 764703, 765183, 766063,
766655, 767391, 768047, 768207, 768255, 769023, 769087, 769135, 769407, 769439, 769567, 769727, 771071, 772207,
772799, 772895, 773119, 773535, 773663, 773823, 773919, 774255, 774351, 774399, 777327, 777631, 779263, 779679,
780447, 781295, 781471, 781855, 782015, 782111, 782591, 782751, 782879, 783471, 783519, 785279, 785567, 786591,
787439, 788351, 788895, 790847, 791071, 791279, 791711, 792447, 792895, 793327, 793471, 793583, 794943, 795679,
796543, 797423, 797727, 798015, 799359, 801087, 801823, 802095, 802111, 802543, 802687, 802799, 805343, 805503,
805615, 805919, 806191, 807391, 807423, 807551, 807967, 809583, 810287, 810303, 810879, 811039, 811487, 814591,
815407, 815615, 815727, 816431, 816607, 816799, 817183, 819247, 819679, 820463, 820735, 820895, 821487, 821871,
822511, 823967, 824623, 824783, 824991, 825391, 825551, 825583, 826143, 826303, 827039, 828655, 829679, 830111,
830239, 830719, 830927, 831087, 831135, 831727, 833583, 833743, 833791, 834799, 835823, 836255, 837023, 838431,
839327, 839455, 839887, 839935, 840095, 842879, 843167, 844015, 844767, 845215, 845951, 847407, 847647, 848127,
848287, 848863, 849023, 850047, 852415, 852959, 854431, 855487, 855759, 857855, 858079, 858239, 858831, 859007,
859103, 859119, 859695, 860927, 861951, 862079, 862927, 863951, 864703, 865311, 866047, 866159, 867023, 867295,
868223, 868335, 868383, 869119, 871455, 872303, 873167, 873503, 875007, 875823, 876031, 876415, 876575, 878079,
878447, 880127, 880543, 881151, 881359, 881967, 882127, 882719, 885231, 886271, 886687, 887407, 887663, 888303,
890095, 890159, 890319, 890527, 891375, 892143, 892399, 892575, 892831, 894191, 895215, 896463, 896623, 896671,
897263, 900335, 900591, 901343, 901359, 901791, 901823, 902047, 902527, 904319, 904863, 905439, 905919, 906367,
906623, 908415, 908831, 908991, 909535, 909551, 910015, 911487, 912063, 913519, 914559, 914655, 914815, 914975,
915135, 915583, 915679, 915839, 916159, 916591, 916927, 918495, 918527, 919663, 919711, 920687, 920735, 921023,
921119, 921279, 921759, 923775, 923871, 924031, 924351, 924639, 924831, 925231, 927903, 928879, 928927, 929487,
930111, 930239, 930335, 930975, 931583, 932559, 932591, 932831, 934047, 934207, 934655, 935071, 937279, 938303,
938703, 939647, 940351, 943263, 943423, 943983, 944447, 944879, 946655, 946671, 946815, 946895, 947839, 948719,
949567, 950767, 952639, 952959, 953199, 953839, 955327, 956911, 957935, 958367, 958399, 958943, 962495, 963519,
965407, 965887, 966127, 966591, 966703, 967583, 967935, 968063, 971551, 972031, 972159, 972735, 972847, 973007,
974959, 975071, 975551, 976127, 977007, 977103, 977599, 977695, 978175, 979055, 979967, 980351, 980927, 981215,
981247, 981375, 981695, 982127, 984063, 984479, 985199, 985295, 986223, 986319, 986655, 986815, 986911, 987391,
987551, 989343, 989407, 989567, 989887, 990623, 991391, 991647, 993439, 994175, 994415, 994463, 994511, 995871,
996223, 996511, 999583, 999839, 1000319, 1000607, 1003839, 1004415, 1005887, 1006463, 1007231, 1008255, 1008799, 1009535,
1009983, 1010303, 1010415, 1012351, 1012767, 1013375, 1014271, 1014975, 1015103, 1015295, 1015679, 1015839, 1016319, 1018175,
1018495, 1018911, 1019071, 1019391, 1019935, 1022463, 1023167, 1023279, 1023487, 1024047, 1024479, 1025535, 1028127, 1028287,
1028607, 1029055, 1029311, 1029423, 1029583, 1029631, 1031839, 1032127, 1032239, 1033679, 1035519, 1036527, 1037503, 1037823,
1038271, 1038383, 1038543, 1038591, 1039599, 1041663, 1041871, 1042639, 1042895, 1043231, 1043263, 1043583, 1043711, 1044127,
1045919, 1046463, 1046783, 1047359, 1047679, 1047967] : List ℕ)) :
syracuseStep^[12] n < n := by sorry