20
\$\begingroup\$

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

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

16 Answers 16

23
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen May 14 at 14:30
  • 1
    \$\begingroup\$ I actually tried to port my answer to 05AB1E, but failed miserably. :D \$\endgroup\$ – Arnauld May 14 at 15:09
  • 1
    \$\begingroup\$ Actually, generating an infinite list is more convenient: 9 bytes with ∞n3*4÷>ʒp \$\endgroup\$ – Grimy May 14 at 15:45
  • 1
    \$\begingroup\$ OK, I'm not used to specs that contradict themselves. :-) \$\endgroup\$ – WGroleau May 14 at 21:11
  • 5
    \$\begingroup\$ @WGroleau I assume you've never developed software professionally then. I'm more concerned when I get specs that don't contradict themselves. \$\endgroup\$ – MikeTheLiar May 14 at 21:29
7
\$\begingroup\$

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.

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

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]
New contributor
speedstyle is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 1
    \$\begingroup\$ 65 bytes. Welcome to ppcg. Nice first answer! +1 \$\endgroup\$ – J42161217 May 14 at 18:39
  • \$\begingroup\$ 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. \$\endgroup\$ – speedstyle May 14 at 18:57
  • 2
    \$\begingroup\$ 56 bytes \$\endgroup\$ – attinat May 14 at 21:54
  • \$\begingroup\$ @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 ...) \$\endgroup\$ – speedstyle May 14 at 22:33
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Olivier Grégoire May 16 at 9:03
  • 1
    \$\begingroup\$ @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);}. \$\endgroup\$ – Kevin Cruijssen May 16 at 9:40
  • \$\begingroup\$ Yeah, I guessed it wasn't much golfable despite my (now obvious) mistakes. Thanks for giving it a ride ;) \$\endgroup\$ – Olivier Grégoire May 16 at 14:02
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen May 16 at 14:30
  • \$\begingroup\$ I might be wrong, but the last %n isn't required, is it? \$\endgroup\$ – Olivier Grégoire May 16 at 14:44
2
\$\begingroup\$

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!

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

Jelly, 12 bytes

²×3:4‘
ÇẒ$#Ç

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

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 +1 so that the and x>1 in the prime checker I borrowed is unnecessary -7
New contributor
speedstyle is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – mypetlion May 14 at 23:01
  • 1
    \$\begingroup\$ 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)). \$\endgroup\$ – speedstyle May 15 at 1:15
1
\$\begingroup\$

Japt, 14 13 bytes

Adapted from Arnauld's formula. 1-indexed.

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

Try it

1 byte saved thanks to EmbodimentOfIgnorance.

\$\endgroup\$
  • \$\begingroup\$ 13 bytes? Not tested thoroughly though. \$\endgroup\$ – Embodiment of Ignorance May 15 at 2:15
  • \$\begingroup\$ Thanks, @EmbodimentofIgnorance. I'd tried that but it didn't work; turns out I'd forgotten the (. \$\endgroup\$ – Shaggy May 15 at 9:47
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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\$.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 1+0+| can be just 1+| \$\endgroup\$ – Grimy May 16 at 10:49
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 102 chars, 204 bytes

r←h w;y;c;v
r←c←y←0⋄→4
y+←1⋄→3×⍳∼0πv←1+3×y×1+y⋄r←v⋄→0×⍳w≤c+←1
v+←3×y+1⋄→2×⍳∼0πv⋄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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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