-
Notifications
You must be signed in to change notification settings - Fork 0
/
conjecture_new.pl
62 lines (46 loc) · 8.61 KB
/
conjecture_new.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#!/usr/bin/perl
# Let a"(n) be the least odd number k > 1 such that b^((k-1)/2) == 1 (mod k) for every natural base b < prime(n).
# Conjecture: a"(n) is composite for all sufficiently large n > N. Such N > 16.
# If a"(n) is a composite k, then it is the least absolute Euler pseudoprime k such that lpf(k) >= prime(n).
#~ Here are a few more terms for a"(n):
#~ 3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249, 2301745249
#~ Is a"(n) also equivalent to:
#~ the least odd number k > 1 such that p^((k-1)/2) == 1 (mod k) for every prime p < prime(n) ?
#~ I checked up to a"(113) and they are identical.
#~ __END__
use 5.014;
use ntheory qw(:all);
my $p = 2;
sub isok {
my ($k) = @_;
#vecall { powmod($_, ($k-1)>>1, $k) == 1 } @primes;
my $t = ($k-1)>>1;
foreach my $n(2..$p-1) {
(powmod($n, $t, $k) == 1) || return;
}
1;
}
#~ sub check_conjecture {
#~ my ($k) = @_;
#~ }
my $n = 2;
$| = 1;
for(my $k = 3; ; $k+=2) {
while(isok($k)) {
print "$k, ";
if ($n > 18 and is_prime($k)) {
die "Conjecture disproved for n = $n and k = $k\n";
}
#push @primes, nth_prime($n);
$p = nth_prime($n);
++$n;
}
}
__END__
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881,
3, 7, 23, 71, 311, 479, 1559, 5711, 10559, 18191, 31391, 366791, 366791, 366791, 3818929, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801, 17236801, 17236801, 17236801, 17236801, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 56052361, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 118901521, 172947529, 172947529, 172947529, 172947529, 172947529, 216821881, 216821881, 216821881, 216821881, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 366652201, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881, 413138881,