experimental-projects/oeis-research/Thomas Ordowski/Tomasz new sequences/conjecture_new.pl

#!/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,