Najmniejsza dodatnia liczba całkowita, która jest koprime dwóch ostatnich poprzedników i jeszcze się nie pojawiła; a (1) = 1, a (2) = 2

10

Definicja

  • Dwie liczby całkowite są chronione prawem autorskim, jeśli nie dzielą żadnych dodatnich wspólnych dzielników innych niż 1.
  • a(1) = 1
  • a(2) = 2
  • a(n)jest najmniejszą liczbą całkowitą dodatnią, która jest względnie pierwsze do a(n-1)a a(n-2)i jeszcze nie pojawił się na całkowitą n >= 3.

Zadanie

  • Podana dodatnia liczba całkowita n, wyjście / wydruk a(n).

Przykład

  • a(11) = 6ponieważ 6jest chroniony prawem autorskim wobec dwóch ostatnich poprzedników (mianowicie 11i 13) i 6nie pojawił się wcześniej.

Notatki

  • Zauważ, że sekwencja nie rośnie, co oznacza, że ​​element może być mniejszy niż jego poprzednik.

Okular

  • Państwo musi użyć 1-indeksowane.

Przypadki testowe

n      a(n)
1      1
2      2
3      3
4      5
5      4
6      7
7      9
8      8
9      11
10     13
11     6
12     17
13     19
14     10
15     21
16     23
17     16
18     15
19     29
20     14
100    139
1000   1355
10000  13387
100000 133361

Punktacja

  • Ponieważ coprime oznacza, że ​​dwie liczby dzielą tylko jeden dzielnik ( 1) i 1jest małą liczbą, twój kod powinien być tak mały, jak to możliwe pod względem liczby bajtów.

Bibliografia

Leaky Nun
źródło
4
Te „powody” dla krótkiego kodu ...
Luis Mendo
1
Zastanawiam się, dlaczego zostało to odrzucone. Z pewnością nie z powodu okropnego uzasadnienia?
Conor O'Brien,
@ Conor Nie ja. Właściwie to głosowałem. Mam nadzieję, że ludzie zobaczą zarówno uzasadnienie, jak i mój komentarz jako żarty
Luis Mendo,
3
Problem z tymi „śmiesznymi” uzasadnieniami dla kodu golfa polega na tym, że muszę przeczytać zły dowcip obejmujący cztery linie, aby dowiedzieć się, że jest to standardowy kod golfowy. Po prostu zasłania zasady wyzwania bez uzasadnionego powodu.
Martin Ender
1
@ ConorO'Brien Nie wszystkie przeglądarki zawsze wyświetlają tytuł (a potem jest aplikacja mobilna), a my generalnie opisujemy ocenę w poście oprócz używania tagu, ponieważ sam tag nie znaczy nic dla osób, które są nowe na stronie. Mimo, że jestem zaznajomiony z naszych tagów typu wyzwanie, nigdy nie czytałem je, aby dowiedzieć się, jak to wyzwanie jest punktowane, ale starają się okazać, że w organizmie wyzwanie. Tag służy do kategoryzacji, wyszukiwania i informacji specyficznych dla typu wyzwania w wiki tagu.
Martin Ender

Odpowiedzi:

5

Python 3.5, 160 141 126 124 121 109 bajtów

Jest to prosta implementacja definicji sekwencji. Sugestie dotyczące gry w golfa mile widziane.

Edycja: -17 bajtów dzięki Dziurawej Zakonnicy. -9 bajtów dzięki Peterowi Taylorowi. -6 bajtów dzięki Sp3000 i przejściu na Python 3.5.

import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)

Ungolfing:

import math
def f(n, r=[2,1], c=3):
    if n<2:
        return r[1]
    elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
        return f(n-1, [c]+r)
    else:
        return f(n, r, c+1)
Sherlock9
źródło
Dla Pythona 3.5, import mathwtedy g=math.gcdpowinien być krótszy niż definiowanie własnych g. Dla zanim 3,5, można to zrobić from fractions import*za gcd.
Sp3000,
Jeśli inicjujesz c=3wewnątrz pętli, musisz to zrobić tylko raz. Według moich obliczeń oszczędzasz 3 znaki.
Peter Taylor,
Istnieje również 2-znakowa oszczędność od budowania tablicy na odwrót: musisz użyć r=[c]+rzamiast +=, ale trzy ujemne wskaźniki stają się dodatnie. I jeszcze jedna oszczędność 2 znaków od przepisywania jako lambda, chociaż jest to dość drastyczna zmiana: from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)i nie ma potrzeby, printponieważ nie jest to już pełny program.
Peter Taylor,
2

MATL , 28 27 bajtów

2:i:"`@ym1MTF_)Zdqa+}@h]]G)

Kod jest wolny, ale daje poprawny wynik.

Wypróbuj online! Lub sprawdź pierwsze dziesięć przypadków .

Mała modyfikacja kodu tworzy wykres sekwencji:

2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG

Zobacz go jako grafikę ASCII lub z graficznym wyjściem w kompilatorze offline:

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

Wyjaśnienie

2:         % Push [1 2] to initiallize the sequence
i:         % Input n. Push [1 2 ... n]
"          % For loop: repeat n times
  `        %   Do while loop
    @      %     Push iteration index, starting at 1. This is the candidate number
           %     to extend the sequence
    y      %     Duplicate vector containing the sequence so far
    m      %     Is member? Gives true if the candidate is in the sequence
    1M     %     Push candidate and vector again
    TF_)   %     Get last two elements of the vector
    Zd     %     GCD between the candidate and those two elements. Produces a
           %     two-element vector
    qa     %     True if any of the two results exceeds 1, meaning
           %     the candidate is not coprime with the latest two sequence values
    +      %     Add. This corresponds to logical "or" of the two conditions, namely
           %     whether the candidate is member of the sequence so far, and
           %     whether it is not coprime with the latest two. In either case
           %     the do...while must continue with a next iteration, to try a new
           %     candidate. Else the loop is exited, and the current candidate
           %     is the new value of the sequence
  }        %   Finally (execute when the loop is exited)
    @h     %     Push current candidate and concatenate to the sequence vector
  ]        %   End do...while
]          % End for
G)         % Get n-th value of the sequence. Implicitly display
Luis Mendo
źródło
1

C, 185 bajtów

G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
orlp
źródło
1

Faktycznie , 38 37 35 33 31 30 bajtów

Jest to prosta implementacja definicji funkcji. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

Edycja: -3 bajty dzięki Dziurawej Zakonnicy.

2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E

Ungolfing:

2R#╗    Push [1,2] and store it in register 0
,;      Take input and duplicate
`1      Start function, push 1
  "       Start string
  ;       Duplicate i
  2±╜t    Push (list in register 0)[-2:]
  πg      gcd(i, product of list[-2:])
  @╜í     Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
  +Y      Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
  "£      End string, turn into a function
╓       Push first (1) values where f(x) is truthy, starting with f(0)
╖`      Append result to the list in register 0, end function
n       Run function (input) times
D╜E     Return (final list)[n-1]
Sherlock9
źródło
1
Dużo manipulacji na stosie
Leaky Nun
0

Haskell, 81 73 bajtów

c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)

Przykład użycia: ((0:1:c[2,1])!!) 12-> 17.

Zbuduj listę wszystkich a(n), zaczynając od, 0aby naprawić indeks oparty na 1, 1a następnie c[2,1]. cbierze na czele listę argumentów, lpo której następuje rekurencyjne wywołanie, a następnie dodany jest następny numer, który pasuje (co-prime, nie widziałem wcześniej) l. Wybierz nelement th z tej listy.

nimi
źródło
0

R, 141 bajtów

 f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))

bez golfa

f=Vectorize( function(n)     #build a recursive function. Vectorize allows
    if(n>3) {                #the function to be called on vectors.
        c=3                  #Tests size. Builds some frequent variables.
        a=f(n-1)
        b=f(n-2)
        d=f(4:n-3)           #Should really golf this out, but its horribly slow.
        while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
              c=c+1          #If we are coprime and not already seen. add.
        c
     } else n)               #First three are 1,2,3.
użytkownik5957401
źródło
0

Mathematica, 97 90 bajtów

a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]

Na podstawie moich przypuszczeń, że a(n) < 2n dla wszystkich n.

Aby uzyskać szybszy przebieg, dodaj a@n=po oryginale, :=aby funkcja nie musiała ponownie obliczać poprzednich wartości .

Zaoszczędź 7 bajtów dzięki Sherlock9 (jeśli gcd(a,b)=1to gcd(ab,m) = gcd(a,m)*gcd(b,m))


źródło
To nie jest przypuszczenie, ponieważ na stronie OEIS jest napisane, że „ ABS(a(n)-n) < n
Leaky Nun
@LeakyNun Thanks. Strona OEIS była niedostępna jeszcze kilka chwil temu i martwiłem się o możliwą kontrprzykład dla dużych n.
0

Pyth, 23 bajty

eu+Gf&-TGq1iT*F>2G1tQ]1

Zestaw testowy

Dość prosta implementacja, ale z kilkoma fajnymi sztuczkami golfowymi.

eu+Gf&-TGq1iT*F>2G1tQ]1
 u                 tQ]1    Apply the following function input - 1 times,
                           where G is the current state (List of values so far)
  +G                       Add to G
    f             1        The first number, counting up from 1
      -TG                  That has not been seen so far
     &                     And where
               >2G         The most recent two numbers
             *F            Multiplied together
           iT              Gcd with the current number being checked
         q1                Equals 1
e                          Output the final element of the list.
isaacg
źródło