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 2d − 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
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