​Cuban​ ​Primes

Question

Given a natural number \$n\$, return the \$n\$-th cuban prime.

Cuban Primes

A cuban prime is a prime number of the form

$$p = \frac{x^3-y^3}{x-y}$$

where \$y>0\$ and \$x = 1+y\$ or \$x = 2+y\$

Details

• You may use 0 or 1 based indexing, whatever suits you best.
• You can return the \$n\$-th prime given the index \$n\$ or the first \$n\$ primes in increasing order, or alternatively you can return an infinite list/generator that produces the primes in increasing order.

Test cases

The first few terms are following:

(#1-13)   7, 13, 19, 37, 61, 109, 127, 193, 271, 331, 397, 433, 547,
(#14-24) 631, 769, 919, 1201, 1453, 1657, 1801, 1951, 2029, 2269, 2437,
(#25-34) 2791, 3169, 3469, 3571, 3889, 4219, 4447, 4801, 5167, 5419,
(#35-43) 6211, 7057, 7351, 8269, 9241, 10093, 10267, 11719, 12097,
(#44-52) 12289, 13267, 13669, 13873, 16651, 18253, 19441, 19927, 20173

More terms can be found on OEIS: They are split up in two sequences, depending on wheter \$x = 1+y \$ or \$x = 2+y\$: A002407 and A002648

Answer 1

JavaScript (V8), 54 bytes

A full program that prints cuban primes forever.

for(x=0;;){for(k=N=~(3/4*++x*x);N%++k;);~k||print(-N)}

Try it online!

^{NB: Unless you have infinite paper in your printer, do not attempt to run this in your browser console, where print() may have a different meaning.}

---

JavaScript (ES6),  63 61 60  59 bytes

Returns the \$n\$-th cuban prime, 1-indexed.

f=(n,x)=>(p=k=>N%++k?p(k):n-=!~k)(N=~(3/4*x*x))?f(n,-~x):-N

Try it online!

How?

This is based on the fact that cuban primes are primes of the form:

$$p_n=\left\lfloor\frac{3n^2}{4}\right\rfloor+1,\;n\ge3$$

The above formula can be written as:

$$p_n=\begin{cases} \dfrac{3n^2+1}{4}\;\text{ if }n\text{ is odd}\\ \dfrac{3n^2+4}{4}\;\text{ if }n\text{ is even} \end{cases} $$

or for any \$y>0\$:

$$p_{2y+1}=\dfrac{3(2y+1)^2+1}{4}=3y^2+3y+1$$ $$p_{2y+2}=\dfrac{3(2y+2)^2+4}{4}=3y^2+6y+4$$

which is \$\dfrac{x^3-y^3}{x-y}\$ for \$x=y+1\$ and \$x=y+2\$ respectively.

Answer 2

05AB1E, 16 12 9 bytes

Generates an infinite list.
Saved 4 bytes with Kevin Cruijssen's port of Arnaulds formula.
Saved another 3 bytes thanks to Grimy

∞n3*4÷>ʒp

Try it online!

Explanation

∞          # on the list of infinite positive integers
 n3*4÷>    # calculate (3*N^2)//4+1 for each
       ʒp  # and filter to only keep primes

Answer 3

R, 75 73 bytes

n=scan()
while(F<n)F=F+any(!(((T<-T+1)*1:4-1)/3)^.5%%1)*all(T%%(3:T-1))
T

Try it online!

-2 bytes by noticing that I can remove brackets if I use * instead of & (different precedence).

Outputs the nth Cuban prime (1-indexed).

It uses the fact (given in OEIS) that Cuban primes are of the form \$p=1+3n^2\$ or \$4p=1+3n^2\$ for some \$n\$, i.e. \$n=\sqrt{\frac{a\cdot p-1}{3}}\$ is an integer for \$a=1\$ or \$a=4\$.

The trick is that no prime can be of the form \$2p=1+3n^2\$ or \$3p=1+3n^2\$ (*), so we can save 2 bytes by checking the formula for \$a\in\{1, 2, 3, 4\}\$ (1:4) instead of \$a\in\{1, 4\}\$ (c(1,4)).

Slightly ungolfed version of the code:

# F and T are implicitly initialized at 0 and 1
# F is number of Cuban primes found so far
# T is number currently being tested for being a Cuban prime
n = scan()                       # input
while(F<n){
  T = T+1                        # increment T 
  F = F +                        # increment F if
    (!all(((T*1:4-1)/3)^.5 %% 1) # there is an integer of the form sqrt(((T*a)-1)/3)
     & all(T%%(3:T-1)))          # and T is prime (not divisible by any number between 2 and T-1)
  }
T                                # output T

(*) No prime can be of the form \$3p=1+3n^2\$, else \$1=3(p-n^2)\$ would be divisible by \$3\$.

No prime other than \$p=2\$ (which isn't a Cuban prime) can of the form \$2p=1+3n^2\$: \$n\$ would need to be odd, i.e. \$n=2k+1\$. Expanding gives \$2p=4+12k(k+1)\$, hence \$p=2+6k(k+1)\$ and \$p\$ would be even.

Answer 4

Wolfram Language (Mathematica), 66 65 56 bytes

(f=1+⌊3#/4#⌋&;For[n=i=0,i<#,PrimeQ@f@++n&&i++];f@n)&

Try it online!

• J42161217 -1 by using ⌊ ⌋ instead of Floor[ ]

• attinat

  • -1 by using ⌊3#/4#⌋ instead of ⌊3#^2/4⌋
  • -8 for For[n=i=0,i<#,PrimeQ@f@++n&&i++] instead of n=2;i=#;While[i>0,i-=Boole@PrimeQ@f@++n]

Answer 5

Java 8, 94 88 86 84 bytes

v->{for(int i=3,n,x;;System.out.print(x<1?++n+" ":""))for(x=n=i*i++*3/4;~n%x--<0;);}

-6 bytes by using the Java prime-checker of @SaraJ, so make sure to upvote her!
-2 bytes thanks to @OlivierGrégoire. Since the first number we check is 7, we can drop the trailing %n from Sara's prime-checker, which is to terminate the loop for n=1.
-2 bytes thanks to @OlivierGrégoire by porting @Arnauld's answer.

Outputs space-delimited indefinitely.

Try it online.

Explanation (of the old 86 bytes version): TODO: Update explanation

Uses the formula of @Arnauld's JavaScript answer: \$p_n=\left\lfloor\frac{3n^2}{4}\right\rfloor+1,\;n\ge3\$.

v->{                     // Method with empty unused parameter and no return-type
  for(int i=3,           //  Loop-integer, starting at 3
          n,x            //  Temp integers
      ;                  //  Loop indefinitely:
      ;                  //    After every iteration:
       System.out.print( //     Print:
        n==x?            //      If `n` equals `x`, which means `n` is a prime:
         n+" "           //       Print `n` with a space delimiter
        :                //      Else:
         ""))            //       Print nothing
    for(n=i*i++*3/4+1,   //   Set `n` to `(3*i^2)//4+1
                         //   (and increase `i` by 1 afterwards with `i++`)
        x=1;             //   Set `x` to 1
        n%++x            //   Loop as long as `n` modulo `x+1`
                         //   (after we've first increased `x` by 1 with `++x`)
             >0;);}      //   is not 0 yet
                         //   (if `n` is equal to `x`, it means it's a prime)

Answer 6

Wolfram Language (Mathematica), 83 bytes

(t=1;While[Length[l=Select[Join@@Array[{(v=3#^2+1)+3#,v}&,t++],PrimeQ]]<#];Sort@l)&

Try it online!

Answer 7

Jelly, 12 bytes

²×3:4‘
ÇẒ$#Ç

Try it online!

Based on @Arnauld’s method. Takes n on stdin and returns that many Cuban primes.

Answer 8

Wolfram Language (Mathematica), 83 bytes

This solution will output the n-th Cuban prime with the added benefits of being fast and remembering all previous results in the symbol f.

(d:=1+3y(c=1+y)+3b c;e:=If[PrimeQ@d,n++;f@n=d];For[n=y=b=0,n<#,e;b=1-b;e,y++];f@#)&

Try it online!

Answer 9

Python 3, 110 108 102 bytes

Similar method to my Mathematica answer (i.e. isPrime(1+⌊¾n²⌋) else n++) using this golfed prime checker and returning an anonymous infinite generator

from itertools import*
(x for x in map(lambda n:1+3*n**2//4,count(2)) if all(x%j for j in range(2,x)))

Try it online!

• mypetlion -2 because arguably anonymous generators are more allowed than named ones
• -6 by starting count at 2 ₊₁ so that the and x>1 in the prime checker I borrowed is unnecessary _-7

Answer 10

Japt, 14 13 bytes

Adapted from Arnauld's formula. 1-indexed.

@µXj}f@Ò(X²*¾

Try it

1 byte saved thanks to EmbodimentOfIgnorance.

Answer 11

Racket, 124 bytes

(require math)(define(f n[i 3])(let([t(+(exact-floor(* 3/4 i i))1)][k(+ 1 i)])(if(prime? t)(if(= 0 n)t(f(- n 1)k))(f n k))))

Try it online!

Returns the n-th cuban prime, 0-indexed.

Uses the formula of @Arnauld's JavaScript answer

Answer 12

Whitespace, 180 bytes

[S S S T    S N
_Push_2][S N
S _Duplicate][N
S S N
_Create_Label_OUTER_LOOP][S N
N
_Discard_top_stack][S S S T N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][T S S N
_Multiply][S S S T  T   N
_Push_3][T  S S N
_Multiply][S S S T  S S N
_Push_4][T  S T S _Integer_divide][S S S T  N
_Push_1][T  S S S _Add][S S S T N
_Push_1][S N
S _Duplicate_1][N
S S S N
_Create_Label_INNER_LOOP][S N
N
_Discard_top_stack][S S S T N
_Push_1][T  S S S _Add][S N
S _Duplicate][S N
S _Duplicate][S T   S S T   T   N
_Copy_0-based_3rd][T    S S T   _Subtract][N
T   S T N
_Jump_to_Label_PRINT_if_0][S T  S S T   S N
_Copy_0-based_2nd][S N
T   _Swap_top_two][T    S T T   _Modulo][S N
S _Duplicate][N
T   S S S N
_Jump_to_Label_FALSE_if_0][N
S N
S N
_Jump_to_Label_INNER_LOOP][N
S S T   N
_Create_Label_PRINT][T  N
S T _Print_as_integer][S S S T  S T S N
_Push_10_(newline)][T   N
S S _Print_as_character][S N
S _Duplicate][N
S S S S N
_Create_Label_FALSE][S N
N
_Discard_top_stack][S N
N
_Discard_top_stack][N
S N
N
_Jump_to_Label_OUTER_LOOP]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Outputs newline-delimited indefinitely.

Try it online (with raw spaces, tabs, and new-lines only).

Explanation in pseudo-code:

Port of my Java 8 answer, which also uses the formula from @Arnauld's JavaScript answer: \$p_n=\left\lfloor\frac{3n^2}{4}\right\rfloor+1,\;n\ge3\$.

Integer i = 2
Start OUTER_LOOP:
  i = i + 1
  Integer n = i*i*3//4+1
  Integer x = 1
  Start INNER_LOOP:
    x = x + 1
    If(x == n):
      Call function PRINT
    If(n % x == 0):
      Go to next iteration of OUTER_LOOP
    Go to next iteration of INNER_LOOP

function PRINT:
  Print integer n
  Print character '\n'
  Go to next iteration of OUTER_LOOP

Answer 13

Python 3, 83 bytes

prints the cuban primes forever.

P=k=1
while 1:P*=k*k;x=k;k+=1;P%k>0==((x/3)**.5%1)*((x/3+.25)**.5%1-.5)and print(k)

Try it online!

Based on this prime generator. For every prime it checks whether an integer y exists that fulfills the equation for either \$x = 1+y\$ or \$x=2+y\$.

$$ p=\frac{(1+y)^3-y^3}{(1+y)-y} = 1 + 3y +3y^2 \Leftrightarrow y = -\frac{1}{2}\pm\sqrt{\frac{1}{4}+\frac{p-1}{3}}$$

$$ p=\frac{(2+y)^3-y^3}{(1+y)-y} = 4 + 6y +3y^2 \Leftrightarrow y = -1 \pm\sqrt{\frac{p-1}{3}}$$ As we only care whether \$y\$ has an integer solution, we can ignore the \$\pm\$ and \$-1\$.

Answer 14

Perl 6, 33 31 bytes

-2 bytes thanks to Grimy

{grep &is-prime,1+|¾*$++²xx*}

Try it online!

Anonymous code block that returns a lazy infinite list of Cuban primes. This uses Arnauld's formula to generate possible cuban primes, then &is-prime to filter them.

Explanation:

{                           }  # Anonymous code block
 grep &is-prime,               # Filter the primes from
                         xx*   # The infinite list
                   ¾*          # Of three quarters
                     $++²      # Of an increasing number squared
                1+|            # Add one by ORing with 1

Answer 15

Pari/GP, 51 bytes

Using Arnauld's formula.

n->a=0;for(i=1,n,until(isprime(p=3*a^2\4+1),a++));p

Try it online!

Answer 16

APL(NARS), 98 chars, 196 bytes

r←h w;y;c;v
r←c←y←0⋄→4
→3×⍳∼0πv←1+3×y×1+y+←1⋄r←v⋄→0×⍳w≤c+←1
→2×⍳∼0πv+←3×y+1⋄c+←1⋄r←v
→2×⍳w>c

indented :

r←h w;y;c;v
r←c←y←0⋄→4
    →3×⍳∼0πv←1+3×y×1+y+←1⋄r←v⋄→0×⍳w≤c+←1
    →2×⍳∼0πv+←3×y+1⋄c+←1⋄r←v
    →2×⍳w>c

test:

  h ¨1..20
7 13 19 37 61 109 127 193 271 331 397 433 547 631 769 919 1201 1453 1657 1801 
  h 1000
25789873
  h 10000
4765143511

it is based on: if y in N, one possible Cuban Prime is

S1=1+3y(y+1)

the the next possible Cuban Prime will be

S2=3(y+1)+S1