123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400 |
- #!/usr/bin/perl
- #~ Consider the following sequences:
- #~ Let a(n) be the smallest prime p such that n^p == n (mod q), for n = 0,1,2,...
- #~ (*) where q is the smallest prime > p such that p-1 | q-1.
- #~ (**) where q is the next prime after p.
- #~ (*) 2, 2, 11, 2, 2, 3, 2, 2, 5, 2, ... Is this sequence periodic?
- #~ (**) 2, 2, 113, 2, 2, 3, 2, 2, 5, 2, ... Is this sequence bounded?
- #~ Have a nice day!
- #~ Corrected set: A = {9, 15, 21, 25, 33, 39, 49, 51, 57, 65, 69, 85, 87, 91, 93, 111, 121, 123, 129, 133, 141, 145, 159, 169, 177, 183, 185, 201, 205, 213, 217, 219, 237, 249, 259, 265, 267, 289, 291, 301, 303, 305, 309, 321, 327, 339, 341, 361, 365, 381, 393, 411, 417, 427, 445, 447, 451, 453, 469, 471, 481, 485, 489, 501, 505, 511, 519, 529, 537, 543, 545, 553, 561, 565, 573, 579, 591, 597, 633, 645, 669, 671, 679, 681, 685, 687, 699, 703, 717, 721, 723, 745, 753, 763, 771, 781, 785, 789, 793, 807, 813, 831, 841, 843, 849, 865, 879, 889, 905, 921, 933, 939, 949, 951, 961, 965, 973, 985, 993, 1011, 1041, 1047, 1057, 1059, 1065, 1077, 1099, 1101, 1111, 1119, 1137, 1141, 1145, 1149, 1165, 1167, 1191, 1203, 1205, 1227, 1247, 1257, 1261, 1263, 1267, 1285, 1293, 1299, 1317, 1329, 1345, 1347, 1351, 1369, 1371, 1383, 1385, 1387, 1389, 1393, 1401, 1405, 1417, 1437, 1441, 1461, 1465, 1473, 1477, 1497, 1509, 1527, 1541, 1561, 1563, 1565, 1569, 1585, 1603, 1623, 1641, 1649, 1661, 1671, 1681, 1685, 1687, 1689, 1707, 1713, 1729}
- #~ LCM(A) = 19974189529267233805048246587648609684002517045072696325440852333740211305925469232124401559514495489578549049794060699217424449904662437604539103637539339468499990506897971814716522960950895471907013503223284820116877757184319629345000591535688675
- use 5.014;
- use ntheory qw(:all);
- sub find_q {
- my ($p) = @_;
- foreach my $k(2..1e10) {
- if (is_prime(($p-1)*$k + 1)) {
- return (($p-1)*$k + 1);
- }
- }
- }
- sub a { # p-1 | q-1
- my ($n) = @_;
- my $iter = prime_iterator();
- for (my $p = $iter->(); ; $p = $iter->()) {
- my $q = find_q($p);
- if (powmod($n, $p, $q) == ($n % $q)) {
- return $p; #($p, $q);
- }
- }
- }
- sub b { # nextprime (**)
- my ($n) = @_;
- my $iter = prime_iterator();
- for (my $p = $iter->(); ; $p = $iter->()) {
- my $q = next_prime($p);
- if (powmod($n, $p, $q) == ($n % $q)) {
- return $p;
- }
- }
- }
- sub c {
- my ($n) = @_;
- for(my $k = 3; $k <= 1729; $k += 2) {
- next if is_prime($k);
- my $t = powmod($n, ($k+1)>>1, $k);
- if($t == ($n%$k) or $t == (-$n)%$k) {
- return $k;
- }
- }
- }
- use Math::GMPz;
- my $period = Math::GMPz->new("19974189529267233805048246587648609684002517045072696325440852333740211305925469232124401559514495489578549049794060699217424449904662437604539103637539339468499990506897971814716522960950895471907013503223284820116877757184319629345000591535688675");
- foreach my $k(1..1e6) {
- my $x = c($k);
- my $y = c($k + $period);
- if ($x != $y) {
- die "non period: $x != $y for k = $k";
- }
- }
- __END__
- #~ foreach my $k(1..1e8) {
- #~ if (c($k) == 1247) {
- #~ say "c($k) = 1247";
- #~ last;
- #~ }
- #~ }
- #~ __END__
- #say c(2153846);
- #~ use Math::GMPz;
- #~ say c(Math::GMPz->new("560500033"));
- #~ say c(Math::GMPz->new("13668555257082559489"));
- #~ say c(Math::GMPz->new("9498733884118309169"));
- #~ say c(Math::GMPz->new("9621022700125202321"));
- #~ __END__
- my %seen;
- use Math::GMPz;
- my %known;
- @known{
- 9, 15, 21, 25, 33, 39, 49, 51, 57, 65, 69, 85, 87, 91, 93, 111, 121, 123, 129, 133, 141, 145, 159, 169, 177, 183, 185, 201, 205, 213, 217, 219, 237, 249, 259, 265, 267, 289, 291, 301, 303, 305, 309, 321, 327, 339, 341, 361, 365, 381, 393, 411, 417, 427, 445, 447, 451, 453, 469, 471, 481, 485, 489, 501, 505, 511, 519, 529, 537, 543, 545, 553, 561, 565, 573, 579, 591, 597, 633, 645, 669, 671, 679, 681, 685, 687, 699, 703, 717, 721, 723, 745, 753, 763, 771, 781, 785, 789, 793, 807, 831, 841, 849, 865, 879, 889, 905, 921, 933, 939, 949, 951, 961, 965, 973, 985, 1041, 1057, 1059, 1065, 1099, 1101, 1111, 1137, 1141, 1145, 1149, 1203, 1247, 1261, 1263, 1267, 1299, 1317, 1329, 1345, 1369, 1385, 1387, 1393, 1417, 1441, 1461, 1477, 1541, 1561, 1565, 1585, 1661, 1685, 1687, 1713, 1729,
- 1681,
- 1689,
- 1383,
- 1119,
- 1437,
- 1191,
- 1649,
- 1011,
- 1371,
- 1671,
- 1167,
- 1285,
- 1293,
- 843,
- 1077,
- 993,
- 1473,
- 813,
- 1047,
- 1509,
- 1257,
- 1389,
- 1165,
- 1351,
- 1227,
- 1465,
- 1347,
- 1405,
- 1527,
- 1569,
- 1707,
- 1497,
- 1563,
- 1401,
- 1603,
- 1641,
- 1205,
- 1623,
- } = ();
- foreach my $k(1..1e8) {
- if (not exists $known{c($k)}) {
- say "Found: a($k) = ", c($k);
- $known{c($k)} = $k;
- }
- }
- __END__
- use Math::AnyNum;
- say c(Math::AnyNum->new("13668555257082559489"));
- exit;
- #~ say join ', ', keys %known;
- #~ exit;
- #~ foreach my $n(1..1e8) {
- #~ if (not exists $known{c($n)}) {
- #~ say "Found: $n -- ", c($n);
- #~ $known{c($n)} = $n;
- #~ }
- #~ }
- #~ __END__
- #say scalar keys %known;
- # %known = ();
- #~ foreach my $n(1e8..1e9) {
- #~ if (not exists $known{c($n)}) {
- #~ say "Found: $n -- ", c($n);
- #~ $known{c($n)} = $n;
- #~ }
- #~ }
- #~ __END__
- @seen{keys %known} = ();
- #foreach my $k(1..2e6) {
- # $seen{c($k)} = $k;
- #}
- while (<>) {
- next if /^#/;
- next if !/\S/;
- my $n = (split(' '))[-1];
- $n || next;
- #if ($n > ~0) {
- $n = Math::GMPz->new("$n");
- # }
- #say "Testing: $n";
- my $t = c($n);
- if (not exists $seen{$t}) {
- say "New: a($n) = $t";
- $seen{$t} = $n;
- }
- }
- #foreach my $k(sort {$a <=> $b }keys %seen) {
- # say "a($seen{$k}) = $k";
- #}
- say "There are ", scalar(keys %seen), " unique values";
- foreach my $k(keys %seen) {
- if (not exists $known{$k}) {
- say "New: $k (for $seen{$k})";
- }
- }
- say join ', ', sort {$a <=> $b} keys %seen;
- __END__
- New: 119 (for 13668555257082559489)
- New: 1267 (for 560500033)
- New: 35 (for 9498733884118309169)
- New: 27 (for 9621022700125202321)
- #my $max = 0;
- #~ say c(0);
- #~ __END__
- my %seen;
- foreach my $k(1..2e6) {
- undef $seen{c($k)};
- #my $t = c($k);
- #if ($t > $max) {
- # $max = $t;
- # say "a($k) = $t";
- #}
- }
- say join ', ', sort {$a <=> $b} keys %seen;
- say scalar keys %seen;
- # A = {9, 15, 21, 25, 33, 39, 49, 51, 57, 65, 69, 85, 87, 91, 93, 111, 121, 123, 129, 133, 141, 145, 159, 169, 177, 183, 185, 201, 205, 213, 217, 219, 237, 249, 259, 265, 267, 289, 291, 301, 303, 305, 309, 321, 327, 339, 341, 361, 365, 381, 393, 411, 417, 427, 445, 447, 451, 453, 469, 471, 481, 485, 489, 501, 505, 511, 519, 529, 537, 543, 545, 553, 561, 565, 573, 579, 591, 597, 633, 645, 671, 679, 681, 685, 687, 699, 703, 717, 721, 723, 745, 753, 763, 771, 781, 785, 789, 793, 831, 841, 843, 849, 865, 879, 889, 905, 921, 933, 939, 949, 951, 961, 965, 973, 985, 993, 1011, 1041, 1057, 1059, 1065, 1077, 1099, 1101, 1111, 1119, 1137, 1141, 1145, 1167, 1191, 1247, 1261, 1263, 1285, 1293, 1329, 1369, 1371, 1383, 1387, 1417, 1437, 1441, 1461, 1477, 1541, 1561, 1585, 1649, 1661, 1671, 1681, 1689, 1729}
- __END__
- use Math::GMPz;
- my $period = lcm(map{find_q($_)}(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 139, 149, 163, 167));
- $period = Math::GMPz->new("$period");
- foreach my $p(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 139, 149, 163, 167) {
- say "Q($p) = ", find_q($p);
- }
- __END__
- $period/=499;
- $period/=739;
- $period/=743;
- say $period;
- #~ exit;
- #~ use Math::AnyNum qw(irand);
- foreach my $n(1..100000) {
- #my $n = irand(factorial($k));
- my $x = a($n);
- my $y = a($n+$period);
- say "Testing: $n ($x == $y)";
- if ($x != $y) {
- die "Not a period: $x != $y for n = $n";
- }
- }
- __END__
- use Math::GMPz;
- my $max = 0;
- while (<>) {
- next if /^#/;
- next if !/\S/;
- my $n = (split(' '))[-1];
- $n || next;
- if ($n > ~0) {
- $n = Math::GMPz->new("$n");
- }
- #my ($p, $q) = a($n);
- my $x = a($n);
- my $y = a($n+$period);
- say "$x $y";
- if ($x != $y) {
- die "Period fail: $x != $y for n = $n";
- }
- #if ($p > $max) {
- # $max = $p;
- # say "a($n) = $p (with q = $q)";
- #}
- }
- __END__
- foreach my $n(0..1e4) {
- say a($n);
- }
- __END__
- #~ my %seen;
- #~ foreach my $k(1..1e7) {
- #~ undef $seen{a($k)};
- #~ }
- #~ say join ', ', sort {$a <=> $b} keys %seen;
- #~ __END__
- #say join ', ', map{a($_)} 0..10;
- #say join ', ', map{b($_)} 0..10;
- #OUTER: foreach my $k(1..1e6) {
- use Math::GMPz;
- my $k = Math::GMPz->new("59135093664847200");
- say "Testing: $k";
- foreach my $n(1..1e6) {
- my $x = a($n);
- my $y = a($n+$k);
- if ($x != $y) {
- die "Not a period $x != $y for n = $n";
- }
- }
- say "Period seems to be $k";
- # last;
- #}
- __END__
- my $max = 163;
- foreach my $k(1e7..1e8) {
- my ($t, $q) = a($k);
- if ($t > $max) {
- $max = $t;
- say "a($k) = $t (with q = $q)";
- }
- }
- __END__
- my %seen;
- foreach my $k(0..1e4) {
- undef $seen{b($k)};
- }
- say join ', ', sort {$a <=> $b} keys %seen;
|