Super-Poulet numbers

Super-Poulet numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A super-Poulet number is a Poulet number (or Fermat pseudoprime to base 2) whose every divisor d evenly divides 2^d − 2.

Task

• Find and display the first 20 super-Poulet numbers.

Stretch

• Find and display the index and value of the first super-Poulet number greater than one million.

See also

• Task: Fermat pseudoprimes
• Wikipedia: super-Poulet number
• OEIS:A050217 - super-Poulet numbers

Phix

with javascript_semantics
include mpfr.e 
constant two = mpz_init(2)

function super_poulet(integer x)
    if is_prime(x) or x<=1 then return false end if
    mpz z = mpz_init(x)
    mpz_powm_ui(z, two, x-1, z)
    if mpz_cmp_si(z,1)!=0 then return false end if
    sequence f = factors(x)
    for i=1 to length(f) do
        mpz_set_si(z,f[i])
        mpz_powm(z, two, z, z)
        if mpz_cmp_si(z,2)!=0 then return false end if
    end for
    return true
end function
 
integer count = 0, x = 1
sequence first20 = {}
while count<20 do
    if super_poulet(x) then
        if count<20 then first20 &= x end if
        count += 1
    end if
    x += 1
end while
printf(1,"First 20 super-Poulet numbers:\n%v\n\n",{first20})
for lim in {1e6,1e7} do
    while true do
        if super_poulet(x) then
            count += 1
            if x>lim then exit end if
        end if
        x += 1
    end while
    printf(1,"The %d%s super-Poulet number is %,d and the first > %g\n",
             {count,ord(count),x,lim})
    x += 1
end for

Output:

First 20 super-Poulet numbers:
{341,1387,2047,2701,3277,4033,4369,4681,5461,7957,8321,10261,13747,14491,15709,18721,19951,23377,31417,31609}

The 109th super-Poulet number is 1,016,801 and the first > 1e+6
The 317th super-Poulet number is 10,031,653 and the first > 1e+7

Raku

<lang perl6>use Prime::Factor; use Lingua::EN::Numbers;

my @poulet = lazy (2..*).hyper(:2000batch).grep: { !.is-prime && (1 == expmod 2, $_ - 1, $_) } my @super-poulet = @poulet.grep: { all .&divisors.skip(1).map: { 2 == expmod 2, $_, $_ } }

say "First 20 super-Poulet numbers:\n" ~ @super-poulet[^20].gist;

for 1e6.Int, 1e7.Int -> $threshold {

   say "\nIndex and value of first super-Poulet greater than {$threshold.&cardinal}:";
   my $index = @super-poulet.first: * > $threshold, :k;
   say "{(1+$index).&ordinal-digit} super-Poulet number == " ~ @super-poulet[$index].,

}</lang>

Output:

First 20 super-Poulet numbers:
(341 1387 2047 2701 3277 4033 4369 4681 5461 7957 8321 10261 13747 14491 15709 18721 19951 23377 31417 31609)

Index and value of first super-Poulet greater than one million:
109th super-Poulet number == 1,016,801

Index and value of first super-Poulet greater than ten million:
317th super-Poulet number == 10,031,653