# ​Cuban​ ​Primes

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

• Can we return the first n primes not sorted? – J42161217 May 14 '19 at 13:29
• @J42161217 No, the primes should be in increasing order. – flawr May 14 '19 at 14:30

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

# 05AB1E, 1612 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

• You've made a typo in your explanation: "put a copy of N^2+3 on the stack" should be 3*N^2. Also, why the ) instead of ¯? Because it's easier to type? And for some reason I have the feeling the NnN‚3*¬sO‚ can be 1 byte shorter, but I'm not seeing it. A slight equal-byte alternative is Nn3*DN3*+‚. But I'm probably just seeing things that aren't there.. ;) Nice answer, so +1 from me. – Kevin Cruijssen May 14 '19 at 14:30
• I actually tried to port my answer to 05AB1E, but failed miserably. :D – Arnauld May 14 '19 at 15:09
• Actually, generating an infinite list is more convenient: 9 bytes with ∞n3*4÷>ʒp – Grimmy May 14 '19 at 15:45
• OK, I'm not used to specs that contradict themselves. :-) – WGroleau May 14 '19 at 21:11
• @WGroleau I assume you've never developed software professionally then. I'm more concerned when I get specs that don't contradict themselves. – MikeTheLiar May 14 '19 at 21:29

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

• what about avoiding a loop by using an upper bound on the nth Cuban prime? – Xi'an May 15 '19 at 7:31
• @Xi'an I thought about that, but couldn't come up with such a bound. Do you have one? – Robin Ryder May 15 '19 at 13:32

# Wolfram Language (Mathematica), 666556 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]
• 65 bytes. Welcome to ppcg. Nice first answer! +1 – J42161217 May 14 '19 at 18:39
• Thanks! (Long time lurker.) I couldn't quite parse your existing answer so I wrote my own and it came out a little shorter. I might do a Python one too. – speedstyle May 14 '19 at 18:57
• 56 bytes – attinat May 14 '19 at 21:54
• @attinat I thought Arnauld's formula only worked for n>2 so I didn't start with 0 - although as in your example it works for all n (because it starts 1 1 4 7 13 ... so the primes are 7 13 ...) – speedstyle May 14 '19 at 22:33

# Java 8, 948886 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)

• I don't really think it's feasible, but another way of finding the cuban primes uses this formula: v->{for(int n=7,i=3,p,x,d,r=0;;i+=++r%2*3,n+=i,System.out.print(x>1?x+" ":""))for(x=n,d=1;++d<n;x=x%d<1?0:n);}, maybe someone can use this to golf? I couldn't. – Olivier Grégoire May 16 '19 at 9:03
• @OlivierGrégoire You can golf yours a bit more by removing the unused ,p and changing i+=++r%2*3,n+=i to n+=i+=++r%2*3, but then I'll still end up at 106 bytes. Using Java 11's String#repeat with prime-regex is 105 bytes: v->{for(int n=7,i=3,r=0;;n+=i+=++r%2*3)if(!"x".repeat(n).matches(".?|(..+?)\\1+"))System.out.println(n);}. – Kevin Cruijssen May 16 '19 at 9:40
• Yeah, I guessed it wasn't much golfable despite my (now obvious) mistakes. Thanks for giving it a ride ;) – Olivier Grégoire May 16 '19 at 14:02
• @OlivierGrégoire Maybe also good to know for you, but there is apparently a shorter prime-check loop in Java. See my edit and SaraJ's prime-check answer. – Kevin Cruijssen May 16 '19 at 14:30
• I might be wrong, but the last %n isn't required, is it? – Olivier Grégoire May 16 '19 at 14:44

# 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!

# Jelly, 12 bytes

²×3:4‘
ÇẒ$#Ç  Try it online! Based on @Arnauld’s method. Takes n on stdin and returns that many Cuban primes. # 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! # 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  # Python 3, 110108102 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 +1 so that the and x>1 in the prime checker I borrowed is unnecessary -7 • The answer going into a variable is usually not considered a valid form of "output". Could you rework your answer so that the result is either output to stdout or returned by a function? – mypetlion May 14 '19 at 23:01 • since anonymous functions are allowed, and the challenge explicitly allows an infinite generator, I've removed g=. I had only included it in the first place because it allowed a quick visual on TIO with print(next(g) for i in range(52)). – speedstyle May 15 '19 at 1:15 # Japt, 14 13 bytes Adapted from Arnauld's formula. 1-indexed. @µXj}f@Ò(X²*¾  Try it 1 byte saved thanks to EmbodimentOfIgnorance. • 13 bytes? Not tested thoroughly though. – Embodiment of Ignorance May 15 '19 at 2:15 • Thanks, @EmbodimentofIgnorance. I'd tried that but it didn't work; turns out I'd forgotten the (. – Shaggy May 15 '19 at 9:47 # 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 # 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\$$. # 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

• 1+0+| can be just 1+| – Grimmy May 16 '19 at 10:49

# 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!

# 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
`