Kubańskie liczby pierwsze

20

Biorąc pod uwagę liczbę naturalną n , zwraca n -tej kubańskie Prime .

Kubańskie liczby pierwsze

Liczba kubańska jest liczbą pierwszą formy

p=x3y3xy

gdzie y>0 i x=1+y lub x=2+y

Detale

  • Możesz użyć indeksowania opartego na 0 lub 1, cokolwiek najbardziej ci odpowiada.
  • Możesz zwrócić n liczbę pierwszą, biorąc pod uwagę indeks n lub pierwsze n liczb pierwszych w kolejności rosnącej, lub alternatywnie możesz zwrócić nieskończoną listę / generator, który wytwarza liczby pierwsze w kolejności rosnącej.

Przypadki testowe

Pierwsze kilka warunków jest następujące:

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

Więcej terminów można znaleźć w OEIS: Są one podzielone na dwie sekwencje, w zależności od tego, czy x=1+y lub x=2+y : A002407 i A002648

wada
źródło
2
Czy możemy zwrócić pierwsze n liczb pierwszych nieposortowanych?
J42161217
@ J42161217 Nie, liczby pierwsze powinny być w porządku rosnącym.
flawr

Odpowiedzi:

23

JavaScript (V8) , 54 bajty

Pełny program, który zawsze drukuje kubańskie liczby pierwsze.

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

Wypróbuj online!

UWAGA: Jeśli nie masz nieskończoną papieru w drukarce, nie próbuj uruchomić to w konsoli przeglądarki , gdzie print()może mieć inne znaczenie.


JavaScript (ES6),  63 61 60  59 bajtów

Zwraca n liczbę pierwszą kubańską, indeksowaną 1.

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

Wypróbuj online!

W jaki sposób?

Jest to oparte na fakcie, że liczby pierwsze kubańskie są liczbami pierwszymi:

pn=3n24+1,n3

Powyższy wzór można zapisać jako:

pn={3n2+14 if n is odd3n2+44 if n is even

lub dla dowolnego y>0 :

p2y+1=3(2y+1)2+14=3y2+3y+1
p2y+2=3(2y+2)2+44=3y2+6y+4

czyli x3y3xy dlax=y+1ix=y+2.

Arnauld
źródło
7

05AB1E , 16 12 9 bajtów

Generuje nieskończoną listę.
Zaoszczędzono 4 bajty dzięki formule Arnaulds dla portu Kevina Cruijssena .
Zaoszczędził kolejne 3 bajty dzięki Grimy

∞n3*4÷>ʒp

Wypróbuj online!

Wyjaśnienie

∞          # on the list of infinite positive integers
 n3*4÷>    # calculate (3*N^2)//4+1 for each
       ʒp  # and filter to only keep primes
Emigna
źródło
W swoim objaśnieniu napisałeś literówkę: „ umieść kopię N^2+3na stosie ” powinno być 3*N^2. Ponadto, dlaczego )zamiast ¯? Ponieważ łatwiej jest pisać? I z jakiegoś powodu mam wrażenie, że NnN‚3*¬sO‚może być o 1 bajt krótszy, ale nie widzę tego. Niewielka alternatywa dla bajtów to Nn3*DN3*+‚. Ale prawdopodobnie widzę tylko rzeczy, których tam nie ma ..;) Dobra odpowiedź, więc daj +1 ode mnie.
Kevin Cruijssen
1
Próbowałem przenieść swoją odpowiedź do 05AB1E, ale niestety nie udało mi się. : D
Arnauld
1
W rzeczywistości generowanie nieskończonej listy jest wygodniejsze: 9 bajtów z ∞n3 * 4 ÷> ʒp
Grimmy
1
OK, nie jestem przyzwyczajony do specyfikacji, które są sobie sprzeczne. :-)
WGroleau
6
@WGroleau Zakładam, że nigdy wcześniej nie rozwijałeś oprogramowania profesjonalnie. Bardziej martwię się, gdy dostaję specyfikacje, które się nie zaprzeczają.
MikeTheLiar
7

R , 75 73 bajtów

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

Wypróbuj online!

-2 bajty, zauważając, że mogę usunąć nawiasy, jeśli użyję *zamiast& (inny priorytet).

Wysyła n th kubańską liczbę pierwszą (indeksowany 1).

Wykorzystuje fakt (podany w OEIS), że liczby pierwsze w Kubie mają postać p=1+3n2 lub 4p=1+3n2 dla niektórych n , tj. n=ap13 jest liczbą całkowitą dlaa=1luba=4.

Trick że nie pierwsza może być Formie 2p=1+3n2 lub 3p=1+3n2 (*), a więc można zaoszczędzić 2 bajty przez sprawdzenie wzoru na { 1 , 2 , 3 , 4 } ( ) zamiast z { 1 , 4 } ( ).a{1,2,3,4}1:4za{1,4}c(1,4)

Nieco golfowa wersja kodu:

# 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

3)p=1+3)n2)1=3)(p-n2))3) .

p=2)2)p=1+3)n2)nn=2)k+12)p=4+12k(k+1)p=2)+6k(k+1)p byłoby parzyste.

Robin Ryder
źródło
co z unikaniem pętli przy użyciu górnej granicy n-tej kubańskiej liczby pierwszej?
Xi'an
@ Xi'an Myślałem o tym, ale nie mogłem wymyślić takiego ograniczenia. Czy masz
Robin Ryder
5

Wolfram Language (Mathematica) , 66 65 56 bajtów

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

Wypróbuj online!

  • J42161217 -1 przy użyciu ⌊ ⌋zamiastFloor[ ]

  • attinat

    • -1 przy użyciu ⌊3#/4#⌋zamiast⌊3#^2/4⌋
    • -8 za For[n=i=0,i<#,PrimeQ@f@++n&&i++]zamiastn=2;i=#;While[i>0,i-=Boole@PrimeQ@f@++n]
speedstyle
źródło
1
65 bytes. Welcome to ppcg. Nice first answer! +1
J42161217
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
2
56 bytes
attinat
@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
3

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: pn=3n24+1,n3.

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)
Kevin Cruijssen
źródło
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
1
@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
Yeah, I guessed it wasn't much golfable despite my (now obvious) mistakes. Thanks for giving it a ride ;)
Olivier Grégoire
@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
I might be wrong, but the last %n isn't required, is it?
Olivier Grégoire
1

Wolfram Language (Mathematica), 83 bytes

To rozwiązanie da n-tą kubańską liczbę pierwszą z dodatkowymi korzyściami polegającymi na szybkości i zapamiętywaniu wszystkich poprzednich wyników w symbolu 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@#)&

Wypróbuj online!

Kelly Lowder
źródło
1

Biała spacja , 180 bajtów

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

Litery S(spacja), T(tab) i N(nowa linia) dodane tylko jako wyróżnienia.
[..._some_action]dodano tylko jako wyjaśnienie.

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: pn=3)n2)4+1,n3).

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
Kevin Cruijssen
źródło
1

Python 3 , 110 108 102 bajtów

Podobna metoda do mojej odpowiedzi Mathematica (tj. isPrime(1+⌊¾n²⌋) else n++) Przy użyciu tego sprawdzania liczb pierwszych w golfa i zwracania anonimowego generatora nieskończonego

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)))

Wypróbuj online!

  • mypetlion -2, ponieważ prawdopodobnie anonimowe generatory są bardziej dozwolone niż te nazwane
  • -6 , zaczynając countod 2 +1, tak że and x>1pożyczony w warcaby pierwszej nie jest potrzebny -7
speedstyle
źródło
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
1
ponieważ anonimowe funkcje są dozwolone, a wyzwanie wyraźnie zezwala na nieskończony generator, usunąłem g=. Włączyłem go tylko w pierwszej kolejności, ponieważ pozwoliło to na szybki podgląd TIO z print(next(g) for i in range(52)).
speedstyle
1

Japt , 14 13 bytes

Na podstawie wzoru Arnaulda . 1-indeksowany.

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

Spróbuj

1 bajt zapisany dzięki EmbodimentOfIgnorance.

Kudłaty
źródło
13 bajtów? Nie zostały jednak dokładnie przetestowane.
Wcielenie nieznajomości
Dzięki, @EmbodimentofIgnorance. Próbowałem tego, ale to nie zadziałało; okazuje się, że zapomniałem (.
Kudłaty
1

Rakieta , 124 bajty

(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))))

Wypróbuj online!

Zwraca n-tą liczbę pierwszą kubańską, 0-indeksowaną.

Wykorzystuje formułę odpowiedzi JavaScript @ Arnauld

Galen Iwanow
źródło
1

Python 3 , 83 bajty

drukuje kubańskie liczby pierwsze na zawsze.

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)

Wypróbuj 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=(1+y)3y3(1+y)y=1+3y+3y2y=12±14+p13

p=(2+y)3y3(1+y)y=4+6y+3y2y=1±p13
As we only care whether y has an integer solution, we can ignore the ± and 1.

ovs
źródło
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
Jo King
źródło
1
1+0+| can be just 1+|
Grimmy
0

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
RosLuP
źródło