16
\$\begingroup\$

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
\$\endgroup\$
0

15 Answers 15

7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I'm just wondering: Since you appear to be using non-ASCII characters, shouldn't those count more than a single byte? Or is it fine on CodeGolf to assume an encoding scheme that is able to represent all used characters as a single byte? But in that case, shouldn't the shortest answer in characters win, rather than in bytes? \$\endgroup\$
    – Raven
    Oct 25, 2022 at 14:26
  • 1
    \$\begingroup\$ @Raven I am not using arbitrary Unicode, just the characters that represent the actual bytes of source code - see the bytes link in the post header for the single-byte character set used by Jelly. \$\endgroup\$ Oct 25, 2022 at 18:47
  • \$\begingroup\$ @Raven There are quite a few links here of meta threads discussing this very issue. I don't see one on Jelly, but Jonathan Allan's link covers that pretty well IMO. \$\endgroup\$
    – Arthur
    Oct 26, 2022 at 11:48
6
\$\begingroup\$

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)
\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Seeing as this is a sequence challange, you should be able to drop the t. \$\endgroup\$
    – Shaggy
    Oct 24, 2022 at 22:43
5
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 42 26 bytes

≔¹θ⊞υθFN«W№υθ≦⊕θ≔⁺υ×υθυ⟦Iθ

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].

FN«

Repeat n times.

W№υθ≦⊕θ

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.

⟦Iθ

Output the prime on its own line.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
+250
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ @DLosc Thanks for the tips, I implemented them all and even use your version of prime checking (had to use your older version of the prime checking with the increment because it wasn't working in DSO for some reason). \$\endgroup\$
    – Aiden Chow
    Dec 6, 2022 at 8:45
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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]])&
\$\endgroup\$
2
  • \$\begingroup\$ 80-byter works not correct, there are no 4, 16 etc \$\endgroup\$
    – lesobrod
    Jun 9, 2023 at 7:47
  • \$\begingroup\$ 81 bytes \$\endgroup\$
    – lesobrod
    Jun 9, 2023 at 12:59
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.