Generate the n'th Fermi-Dirac Prime

Question

A Fermi-Dirac Prime is a prime power of the form \$p^{2^k}\$, where \$p\$ is prime and \$k \geq 0\$, or in other words, a prime to the power of an integer power of two. They are listed as integer sequence A050376. While a normal prime factorization generally does not contain a set of distinct primes (for example \$24=2 \times 2 \times 2 \times 3\$), a Fermi-Dirac prime factorization contains each Fermi-Dirac-prime at most once \$24=2 \times 3 \times 4\$.

Your task is to write a program that takes an integer n as input and prints out the n'th Fermi-Dirac prime or chose any other options from the standard sequence IO rules

Shortest code in bytes wins, no funny business.

1-indexed

1, 2
2, 3
3, 4
4, 5
5, 7
6, 9
7, 11
8, 13
9, 16
10, 17
100, 461
1000, 7649
6605, 65536
10000, 103919
100000, 1296749
1000000, 15476291

Answer 1

Jelly, 9 bytes

2ƽƲ¿Ẓ$#

A monadic Link that accepts an integer, \$n\$, and yields the first \$n\$ Fermi-Dirac primes.

Try it online!

How?

2ƽƲ¿Ẓ$# - Link: integer, n
2       # - count up, starting at 2, and find the first n integers for which:
       $  -   last two links as a monad:
     ¿    -     while...
   Ʋ     -     ...condition: is square?
 ƽ       -     ...action: integer square root
      Ẓ   -     is prime?

Note: The integer-square-root, ƽ could be square-root ½, but we'd need to cast to an integer (e.g. floor, Ḟ) to use Ẓ anyway (e.g. 2.0 is not considered prime), but using ƽ avoids any floating point arithmetic entirely.

Answer 2

Brachylog, 11 bytes (generator), 16 bytes (full program)

.ℕ₂ḋ=l~^h2∧

Try it online!

;I{.ḋ=l~^h2∧}ᶠ⁽b

Try it online!

The generator is 1-indexed. The full program outputs the first n prime powers, 0 indexed.

Actually not that slow.

Explanation

.ℕ₂                  Output is an integer in [2,+inf)
   ḋ                 Its prime decomposition…
    =                …is a list of equal elements…
     l               …with a length…
      ~^h2∧          …being a power of 2



;I{          }ᶠ⁽      Find the first <Input> results of the following predicate:
   .ḋ                   The prime decomposition of the Output…
     =                  …is a list of equal elements…
      l                 …with a length…
       ~^h2∧            … being a power of 2
                b     Remove the first result (1, whose prime decomposition is the empty list)

Answer 3

Python, 60 bytes

L={n:=1}
while{n}<=L or[print(n),L:=L|{n*l for l in L}]:n+=1

Attempt This Online!

Outputs indefinitely.

Complexity is exponential in N, the number of Fermi-Dirac primes to find.

How?

Exploits the factorisation property described in OP: Maintains the set of products of each subset of the set of Fermi-Dirac primes found so far. The smallest number not in this set is the next Fermi-Dirac prime no matter whether it happens to be a conventional prime or a power-of-2th power of one.

Answer 4

Vyxal, 9 8 bytes

ʀEĖeæa)ȯ

Try it Online!

Times out for numbers larger than 20. 1-indexed.

-1 thanks to @Shaggy

Explained

ʀEĖeæa)ȯ  # takes a single integer n
      )ȯ  # first n numbers where:
ʀ         #   the range [0, that number]
 EĖe      #   to the power of 1/(2 to the power of each number in that range) 
    æa    #   contains a prime number

Answer 5

05AB1E, 12 bytes

>Åp¤Ýoδm˜êNè

0-indexed.
Brute-force approach, so slower the larger the input is.

Try it online or verify the first 10 test cases (with ¤ replaced with I> to speed it up a bit, although still times out for \$n\geq15\$).

Explanation:

>             # Increase the (implicit) input by 1 (for edge-case n=0)
 Åp           # Pop and push a list of the first input+2 amount of prime numbers
   ¤          # Push its last/largest prime (without popping the list)
    Ý         # Pop and push a list in the range [0,max_prime]
     o        # Get 2 to the power each value in this list
      δ       # Apply double-vectorized on the two lists:
       m      #  Exponentiation
        ˜     # Flatten the list of lists
         ê    # Sorted-uniquify it
          Iè  # Get the input'th value of this list
              # (after which it is output implicitly as result)

Answer 6

Charcoal, 42 26 bytes

≔¹θ⊞υθＦＮ«Ｗ№υθ≦⊕θ≔⁺υ×υθυ⟦Ｉθ

Try it online! Link is to verbose version of code. Outputs the first n Fermi-Dirac primes. Explanation: Now a port of @loopywalt's Python answer.

≔¹θ⊞υθ

Start with a list of [1].

ＦＮ«

Repeat n times.

Ｗ№υθ≦⊕θ

Find the smallest positive integer not already in the list, which is the next Fermi-Dirac prime.

≔⁺υ×υθυ

Multiply all of the elements of the list by the prime and append them to the list.

⟦Ｉθ

Output the prime on its own line.

Answer 7

Haskell, 78 51 bytes

(2![1]!!)
n!l|elem n l=(n+1)!l|k<-l++map(*n)l=n:2!k

Try it online!

• saved 27 Bytes using @loopy walt approach.

Outputs n-th 0-indexed element

Answer 8

JavaScript (V8), 63 bytes

-1 byte thanks to @jdt

Prints the sequence indefinitely.

for(n=2;k=1;g(k),n++)for(g=k=>k-n?k>n||g(k*k):print(n);n%++k;);

Try it online!

Commented

for(             // infinite outer loop:
  n = 2;         //   start with n = 2
  k = 1;         //   start each iteration with k = 1
  g(k), n++      //   after each iteration: invoke g and increment n
)                //
  for(           //   inner loop:
    g = k =>     //     start by defining the helper function g which
                 //     tests whether n = k ** (2 ** i) for some i
    k - n ?      //     if k is not equal to n:
      k > n ||   //       abort if k is greater than n
        g(k * k) //       otherwise, do a recursive call with k²
    :            //     else:
      print(n);  //       success --> print n
    n % ++k;     //     increment k until it divides n
  );             //   end of inner loop
                 // implicit end of outer loop

Answer 9

Retina, 76 bytes

K`
"$+"{`$
_
)/^(()(((?<-2>)|\4_)\4_)+\4_(?=\4__$))*(?!(__+)\5+$)__/^+`$
_
_

Try it online! No test cases because of the way the program uses history. Explanation:

K`

Clear the working area.

"$+"{`
)`

Repeat n times.

$
_

Increment the working area.

/^(()(((?<-2>)|\4_)\4_)+\4_(?=\4__$))*(?!(__+)\5+$)__/^+`

While the working area is not a Fermi-Dirac prime...

$
_

Increment the working area.

_

Convert to decimal.

Explanation of the test:

()(((?<-2>)|\4_)\4_)+\4_(?=\4__$)

Take the square root. A test for the square root is ((^_|__\2)+)$ but the square root is held in $#1 which is inconvenient, so instead of summing odd numbers this sums pairs of consecutive integers, and the test is not repeatable, even with the adjusted version ((?(1)\1__|_))+ that can be used within a larger expression, so it is necessary to set a dummy group with () and then use (?<-2>) to consume it on the first pass through the main loop. The last loop iteration is unrolled to allow the remainder of the value to be the square root to satisfy either the next iteration of the square root loop or the primality test.

(...)*

Take the square root as many times as possible. (Although obviously this is necessary anyway for the final root to be prime.)

(?!(__+)\5+$)

Test that the remainder is not composite.

__

Test that the remainder is at least 2.

Answer 10

sclin, 45 bytes

$W2+"."fltr
P/"len1="Q rev >A0:1:2log"I"Q = &

Try it here! Returns an infinite list. Feels very golfable...

For testing purposes (use -i flag if running locally):

; 100tk >A
$W2+"."fltr
P/"len1="Q rev >A0:1:2log"I"Q = &

Explanation

Prettified code:

$W2+ \; fltr
  P/ ( len 1= ) Q rev >A 0:1: 2log \I Q = &

• $W2+ \; fltr filter range [2, ∞)...
  • P/ prime factor
    • results in frequency map {prime => frequency}
  • ( len 1= ) Q rev duplicate, check if frequency map has only one prime, swap to save for later
  • >A 0:1: get frequency
    • i.e. get value from 0th key-value pair
  • 2log \I Q = check if power of 2
    • i.e. check if log base 2 of the frequency is an integer
  • & AND

Answer 11

PARI/GP 53 bytes

k=1;while(n,n-=2^#binary(j=isprimepower(k++))==j*2);k

1-indexed; given n, returns n-th Fermi-Dirac prime.

Revised version uses M.F. Hasler's is_A050376(n) provided in OEIS A050376.

Answer 12

Pip, 49 33 32 bytes

-16 bytes thanks to DLosc's suggestions

Wa{Yx:UoT(RT:x)%1Yxa-:1=0Ny%,y}o

Try It Online!

Ok I swear, the prime checking part of the code wasn't working before without the increment U, but now I test it again and it works?!?! Whatever, it's -1 byte.

Answer 13

Raku, 40 bytes

grep {is-prime any $_,*.sqrt...*%1},2..*

Try it online!

This is probably not the best approach but whatever. Outputs as an infinite sequence.

Answer 14

Wolfram Language(Mathematica), 94 81 bytes

Saved 13 bytes thanks to the comment of @lesobrod

---

This sequence is A050376

81 bytes. Try it online!

(k=1;Union@@Reap[While[(m=#^(1/k))>2,Sow[Prime@Range@PrimePi@m^k];k=2k]][[2,1]])&

Answer 15

Wolfram Language (Mathematica), 58 bytes

(a={x=2};Do[While@Mod[Times@@a,++x]==0;AppendTo[a,x],#];a)&

Try it online!

Print given number of sequence members.
Based on the next statement from Wiki:

Another way of defining this sequence is that each element is the smallest positive integer that does not divide the product of all of the previous elements of the sequence.