Naturalnie występujący generator główny

42

Istnieje dość duża liczba funkcji generujących liczby pierwsze. Prawie wszystkie z nich są zbudowane i opierają się na sicie Eratostenesa, funkcji Möbiusa lub twierdzeniu Wilsona i są generalnie niemożliwe do obliczenia w praktyce. Ale są też generatory, które mają bardzo łatwą strukturę i zostały znalezione przypadkowo.

W 2003 roku Stephen Wolfram zbadał klasę zagnieżdżonych równań rekurencyjnych w eksperymencie komputerowym na żywo w NKS Summer School. Grupa ludzi wokół Matthew Franka przeprowadziła dodatkowe eksperymenty i odkryła interesującą właściwość tego prostego nawrotu

a(n) = a(n-1) + gcd(n,a(n-1))

z wartością początkową a(1) = 7. Różnica a(n) - a(n-1) = gcd(n,a(n-1))zawsze wydawała się 1 lub liczbą pierwszą. Pierwsze kilka różnic to ( OEIS A132199 ):

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, ...

Jeśli pominiemy tylko jedynki, otrzymamy następującą sekwencję ( OEIS A137613 ):

5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 
941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, ...

Kilka lat później Eric S. Rowland udowodnił prymat każdego elementu z tej listy. Jak widać, liczby pierwsze są mieszane, a niektóre z nich pojawiają się wiele razy. Udowodniono również, że sekwencja zawiera nieskończenie wiele różnych liczb pierwszych. Ponadto przypuszcza się, że pojawiają się wszystkie nieparzyste liczby pierwsze.

Ponieważ ten główny generator nie został skonstruowany, ale po prostu został znaleziony przypadkowo, główny generator nazywany jest „naturalnie występującym”. Zauważ jednak, że w praktyce generator ten jest również bardzo trudny do obliczenia. Jak się okazuje, pierwsze p pojawia się dopiero po (p–3)/2kolejnych 1s. Niemniej jednak wdrożenie tego generatora będzie Twoim zadaniem.

Wyzwanie:

Napisz funkcję lub program, który drukuje pierwsze nelementy sekwencji A137613(sekwencja bez 1s). Numer wejściowy można odczytać za n >= 0pomocą STDIN, argumentu wiersza poleceń, monitu lub argumentu funkcji. Wypisz pierwsze nelementy w dowolnym czytelnym formacie do STDOUT lub zwróć tablicę lub listę z tymi wartościami.

To jest golf golfowy. Dlatego wygrywa najkrótszy kod.

Tabela liderów:

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka. Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie N jest rozmiarem twojego zgłoszenia. Jeśli poprawisz swój wynik, możesz zachować stare wyniki w nagłówku, przekreślając je. Na przykład:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Jakube
źródło
1
Chociaż generator główny nie jest zbudowany, efektywnie wdrażasz podział próbny za pomocą rekurencji.
orlp
Jeśli a (1) = 7, dlaczego sekwencja nie zaczyna się od 7?
feersum
3
@feersum, ponieważ sekwencja, którą się zajmujemy, toa(n)-a(n-1)
Maltysen
Czy może nbyć zero?
Sp3000,
1
@jrenk Nie jestem pewien. Może policz to jako 2 bajty (ponieważ usuwasz 2 znaki //) i wyjaśnij to w swoim zgłoszeniu. Jeśli ktoś się z tobą nie zgadza, zawsze możesz edytować swój post.
Jakube,

Odpowiedzi:

19

Pyth, 14 13 bajtów

meaYhP+sY-5dQ

Używa a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))gdzie Lpfoznacza najmniejszy czynnik główny.

Wypróbuj tutaj online.

orlp
źródło
7

Python 3.5.0b1 +, 95 93 bajtów

Link do wydania Python 3.5.0b1 +

import math
def f(k,n=2,a=7,L=[]):x=math.gcd(n,a);return k and f(k-1%x,n+1,a+x,L+1%x*[x])or L

Bezpośrednia realizacja cyklu, obejmująca:

  • Nasz dobry przyjaciel 1%xi
  • math.gcd, w przeciwieństwie do fractions.gcd.
Sp3000
źródło
Co ma 1%xzrobić? Pytanie poboczne: gdzie znajdę dokumentację historii wersji Pythona, która zawiera bety? Edycja: Nevermind, znalazłem go na dole historii zmian .
mbomb007
@ mbomb007 Ponieważ x >= 1, 1%xzwraca 0 jeśli x == 1, 1 inaczej (używany do zdecydować, czy dodać xdo listy)
SP3000
5

Julia, 110 bajtów

n->(a(n)=(n1&&(n==1?7:a(n-1)+gcd(n,a(n-1))));i=2;j=0;while j<n x=a(i)-a(i-1);x>1&&(j+=1;println(x));i+=1end)

Nie golfowany:

function a(n::Int)
    n  1 && (n == 1 ? 7 : a(n-1) + gcd(n, a(n-1)))
end

function f(n::Int)
    i = 2;
    j = 0;
    while j < n
        x = a(i) - a(i-1)
        if x > 1
            j += 1
            println(x)
        end
        i += 1
    end
end
Alex A.
źródło
Wow, perfekcyjne 8k, fajnie: D
Beta Decay
1
Użyj n<2zamiast n==1. Ponadto, jeśli spojrzeć do przodu zamiast do tyłu, można użyć i=1i x=a(i)-a(i+=1), a następnie println(-x)i -x>1na prawidłowe dla negativeness, unikając w ten sposób konieczności stosowania oddzielnego przyrostu i. I ma trzy bajty, podczas gdy >=dwa ... ale wtedy możesz użyć n<1||()zamiast n>=1&&()... a mimo to nie jest to nawet konieczne (porzuć warunek, n ​​nigdy nie będzie mniejszy niż 1). Nie potrzebujesz również najbardziej zewnętrznych nawiasów podczas definiowania (n). Dzięki tym zmianom powinieneś uzyskać przynajmniej 97 bajtów.
Glen O,
5

PHP, 101 96 99 98 77 72 bajtów

<?for(;2>$t=gmp_strval(gmp_gcd(~++$i,7+$e+=$t))or$argv[1]-=print"$t ";);


Użycie:
Wywołaj skrypt z argumentem: php -d error_reporting=0 script.php 30
jeśli chcesz go przetestować, musisz cofnąć komentarz ;extension=php_gmp.dllw php.ini
-> extension=php_gmp.dll
Czy powinienem dodać rozszerzenie do mojej liczby bajtów? jakieś pomysły?


Dziennik:
Zapisano 3 bajty dzięki Ismael Miguel.
Zaoszczędź 26 bajtów dzięki primo.

Jrenk
źródło
1
Możesz skrócić otwierający tag <?i usunąć definicję $j.
Ismael Miguel,
1
Tak, to się liczy. Ale możesz usunąć tę nową linię. Co pozwoli zaoszczędzić 1-2 bajty, w zależności od tego, jak policzyłeś rozmiar kodu.
Ismael Miguel,
1
Niewielkie ulepszenia: Użyj <w $j<=$argv[1](drukuje o jeden za dużo) (-1). Pozostaw $eniezainicjowane, użyj $e+7zamiast tego (-3). Użyj for(;;)zamiast while(), używając wyrażeń wstępnych i końcowych (-2). Wymienić echo$t.' ';$j++z $j+=print"$t ", spadek wsporniki (-3). Wymienić if($t>1)z 2>$t||(-2). Połącz przypisanie $tz warunkowym, przełącz ||na or, upuść nawiasy (-5). Przejdź $argv[1]do $jprzyrostu, przenieś całe wyrażenie do forwarunkowej (-2). Zmień >=$j+=printna -=print(-3). Krok po kroku: codepad.org/s6LNSPSM
primo
1
@primo dzięki za miłe wyjaśnienie! Nie wiedziałem, że mogę to wszystko zrobić.
jrenk
1
Kilka innych: Połącz $e+7z $e+=$t(-2). Pozostaw $iniezainicjowane, użyj ~++$izamiast tego (-3). codepad.org/fDIImajp
primo
4

Haskell, 51 bajtów

d=zipWith gcd[2..]$scanl(+)7d
f=($filter(>1)d).take

Zauważ, że fjest to funkcja, która zwróci pierwsze n elementów.

Zamiast obliczać, a(n)a następnie opracowywać różnice, obliczamy różnice d(n)i sumujemy je razem a(n). (Osoby niezaznajomione z Haskellem mogą protestować, że a(n)najpierw musimy to zrobić d(n), ale oczywiście leniwa ocena omija ten problem!)

Nie golfowany:

a = scanl (+) 7 d        -- yielding a(n) = 7 + d(1) + d(2) + ... + d(n-1)
d = zipWith gcd [2..] a  -- yielding d(n) = gcd(n+1, a(n))

f n = take n $ filter (> 1) d -- get rid of 1s and take the first n
Artelius
źródło
4

Pyth, 30 bajtów

Bardzo źle golfa, można znacznie zmniejszyć. Definiuje funkcję rekurencyjną z przodu, filtruje .first-n, a następnie odwzorowuje różnicę.

L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

Wypróbuj tutaj online .

Maltysen
źródło
Daje to zły wynik dlan = 0
Sp3000,
2
@ Sp3000, który jest błędem w Pyth. Złożę prośbę.
Maltysen,
Znaleziono błąd i naprawiono - łatka zostanie zaimplementowana, gdy github przestanie być DDoS.
isaacg,
1
Oto on: meta.codegolf.stackexchange.com/questions/5318/… . Osobiście rozważę poprawki błędów w językach programowania jako odpowiedź
Thomas Weller,
2
@ThomasWeller W pewnym sensie osiągnięto cały język ...
isaacg
4

Julia, 69 67 bajtów

n->(i=1;a=7;while n>0 x=gcd(i+=1,a);a+=x;x>1&&(n-=1;println(x))end)

Jest to proste iteracyjne rozwiązanie problemu. xjest różnica (która jest gcd), a następnie aktualizuję a, dodając x.

Glen O
źródło
Myślę, że drukuje A231900 .
alephalpha
@alephalpha - Myślę, że widzę błąd. Łatwo naprawiony. Ogolił nawet dwa bajty.
Glen O
3

JavaScript (ES6), 91

Rekurencyjny gcd, iteracyjna główna funkcja. Nie tak szybko.

Zwykła uwaga: przetestuj fragment kodu w dowolnej przeglądarce zgodnej z EcmaScript 6 (w szczególności nie Chrome, a nie MSIE. Testowałem na Firefoxie, Safari 9 mogłaby działać)

F=m=>{
  for(G=(a,b)=>b?G(b,a%b):a,o=[],p=7,n=1;m;d>1&&(o.push(d),--m))
    p+=d=G(++n,p);
  return o
}

O.innerHTML=F(+I.value)
<input id=I value=10><button onclick='O.innerHTML=F(+I.value)'>-></button>
<pre id=O></pre>

edc65
źródło
3

Haskell, 74 71 66 bajtów

f=($filter(>1)$tail>>=zipWith(-)$scanl(\x->(x+).gcd x)7[2..]).take

Zastosowałem lewę tutaj: https://codegolf.stackexchange.com/a/39730/43318 i uczyniono bez punktów.

(Poprzedni: 71 bajtów)

a=scanl(\x->(x+).gcd x)7[2..]
f m=take m$filter(>1)$zipWith(-)(tail a)a

Najpierw utwórz sekwencję a, a następnie weź różnice.

(Poprzedni: 74 bajty)

f m=take m$filter(>1)$map snd$scanl(\(x,d)->(\y->(x+y,y)).gcd x)(7,1)[2..]

Standardowe funkcje listy oraz sprytne wykorzystanie funkcji lambda. Zauważ, że jest to 1 bajt krótszy niż bardziej oczywisty

g m=take m$filter(>1)$map snd$scanl(\(x,d)n->(x+gcd x n,gcd x n))(7,1)[2..]

Jeśli nie liczymy importów, mogę to zmniejszyć do 66.

import Data.List
h m=take m$filter(>1)$snd$mapAccumL(\x->(\y->(x+y,y)).gcd x)7[2..]
Holden Lee
źródło
3

PARI / GP, 60 bajtów

a(n)=a=7;i=1;while(n,if(1<d=gcd(i+=1,a),n-=1;print(d));a+=d)

Wzięte mniej więcej prosto z definicji a (n) - a (n-1) = gcd (n, a (n-1))

Dane wyjściowe dla a(20):

5
3
11
3
23
3
47
3
5
3
101
3
7
11
3
13
233
3
467
3
primo
źródło
2

C ++, 193 182 180 172 bajtów

Dzięki @Jakube - zapisano 8 bajtów na wyjściu.

int g(int a,int b){return a==b?a:a>b?g(b,a-b):g(a,b-a);}void f(int *r,int n){int m=1,i=0,a=7,b;while(i<n){b=g(a,++m);if(b>1){r[i]=b;++i;}a+=b;}}int main(){int r[6];f(r,6);}
EvgeniyZh
źródło
Prawdopodobnie można zapisać kilka bajtów, definiując funkcję f, która zwraca tablicę z wynikami. W ten sposób możesz usunąć dołączenie, skan i wydruk.
Jakube
2

Mathematica, 59 bajtów

For[i=j=1;a=7,i<=#,,d=GCD[++j,a];If[d>1,Print@d;i++];a+=d]&
alephalpha
źródło