Twoim zadaniem jest zaimplementowanie sekwencji liczb całkowitych A130826 :

_n jest najmniejszą dodatnią liczbą całkowitą, tak że _n - n jest cały wielokrotnością 3 i dwa razy liczbę dzielników (A _n - n) / 3 daje n ^th określenie w pierwszych różnice sekwencji wytwarzanych przez Flawiusza Sito Józefa Flawiusza.

Zgubiłeś już? Cóż, w rzeczywistości jest to dość łatwe.

Józef Flawiusz sita określa sekwencję całkowitą w następujący sposób.

1. Zacznij od sekwencji dodatnich liczb całkowitych i ustaw k = 2 .

2. Usuń każdą k- ^tą liczbę całkowitą sekwencji, zaczynając od k- ^tej .

3. Zwiększ wartość k i wróć do kroku 2.

f _n jest n- ^tą liczbą całkowitą (indeksowaną 1), która nigdy nie zostanie usunięta.

Jeżeli - jak zwykle - σ ₀ (k) oznacza liczbę dodatnich dzielników liczby całkowitej K , można określić z _n jak najmniejszej liczby całkowitej w taki sposób, 2σ ₀ ((a _n - n) / 3) = f _{n + 1} - f _n .

Wyzwanie

Napisać program lub funkcji, które ma dodatnią liczbę całkowitą N wejściu i nadrukami lub powraca do _n .

Obowiązują standardowe zasady gry w golfa . Niech wygra najkrótszy kod!

Sprawdzone przykłady

Jeśli usuniemy co drugi element dodatnich liczb całkowitych, pozostaje nam

 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...

Po usunięciu co trzeciego elementu pozostałej części otrzymujemy

 1  3  7  9 13 15 19 21 25 27 31 33 37 39 ...

Teraz usuwamy co czwarty, potem piąty, a następnie szósty element

 1  3  7 13 15 19 25 27 31 37 39 ...
 1  3  7 13 19 25 27 31 39 ...
 1  3  7 13 19 27 31 39 ...
 1  3  7 13 19 27 39 ...

Ostatni wiersz pokazuje warunki od f ₁ do f ₇ .

Różnice między kolejnymi elementami tych warunków są

 2  4  6  6  8 12

Dzieląc te różnice w przód przez 2 , otrzymujemy

 1  2  3  3  4  6 

Są to liczby dzielników docelowych.

• 4 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 1) / 3) = 1 . W rzeczywistości σ ₀ (1) = 1 .
• 8 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 2) / 3) = 2 . W rzeczywistości σ ₀ (2) = 2 .
• 15 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 3) / 3) = 3 . W rzeczywistości σ ₀ (4) = 3 .
• 16 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 4) / 3) = 3 . W rzeczywistości σ ₀ (4) = 3 .
• 23 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 5) / 3) = 4 . W rzeczywistości σ ₀ (6) = 4 .
• 42 jest pierwszą liczbą całkowitą k taką, że σ ₀ ((k - 6) / 3) = 6 . W rzeczywistości σ ₀ (12) = 6 .

Przypadki testowe

   n     a(n)

   1        4
   2        8
   3       15
   4       16
   5       23
   6       42
   7       55
   8      200
   9       81
  10       46
  11      119
  12      192
  13      205
  14   196622
  15    12303
  16       88
  17      449
  18      558
  19      127
  20     1748
  21   786453
  22       58
  23     2183
  24     3096
  25     1105
  26   786458
  27 12582939
  28      568
  29     2189
  30     2730

Galaretka, 30 29 27 25 bajtów

Zaoszczędziłem 2 bajty dzięki powiadomieniu @Dennis Ædi kolejnym 2 bajtom na połączenie dwóch łańcuchów.

RUð÷‘Ċ×µ/
‘Ç_ÇH0Æd=¥1#×3+

Wypróbuj online!

To była prawdopodobnie najlepsza zabawa, jaką kiedykolwiek miałem z Jelly. Zacząłem od drugiej linii, która oblicza f _n od n za pomocą wzoru na OEIS i jest dość piękna.

Wyjaśnienie

RUð ÷ '× × µ / Łącznik pomocniczy do obliczenia F n . Argument: n
R Uzyskaj liczby [1..n]
 U Reverse
        / Zmniejsz o „zaokrąglić w górę do następnych 2 wielokrotności”:
   ÷ Podziel przez następny numer
    „Przyrost pomija wielokrotność
     Ce Ceil (zaokrąglenie w górę)
      × Pomnóż przez następny numer

„Ç_ÇH0Æd = ¥ 1 # × 3 + Główny link. Argument: n
„Przyrost n
 Ç Oblicz F n + 1 
   Ç Oblicz F n
  _ Odejmować
    H Podziel przez 2
     0 1 # Począwszy od 0, znajdź pierwszego kandydata na (a n-n ) / 3
                   który spełnia ...
      Æd σ 0 ((a n-n ) / 3)
        = = (F n + 1- F n ) / 2
            × 3 Pomnóż przez 3, aby zmienić (a n-n ) / 3 w n- n
              + Dodaj n, aby zmienić n-n w n

Python 2 , 121 119 118 bajtów

n=input();r=range(1,4**n);d=s,=r*1,
for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,
print d.index(s[n]-s[n-1])*3+n

Czas działania powinien wynosić mniej więcej O (16 ⁿ ) przy zużyciu pamięci O (4 ⁿ ) . Zastąpienie 4**nprzez 5<<n- co moim zdaniem jest wystarczające - poprawiłoby to radykalnie, ale nie jestem przekonany, że działa on na dowolnie duże wartości n .

Wypróbuj online!

Zachowanie asymptotyczne i górne granice _n

Zdefiniuj b _n jako (a _n - n) / 3 , tj. Najmniejszą dodatnią liczbę całkowitą k taką, że σ ₀ (k) = ½ (f _{n + 1} - f _n ) .

Jak zauważono na stronie OEIS, f _n ~ ¼πn ² , więc f _{n + 1} - f _n ~ ¼π (n + 1) ² - ¼πn ² = ¼π (2n + 1) ~ ½πn .

W ten sposób ½ (f _{n + 1} - f _n ) ~ ¼πn . Jeżeli rzeczywista liczba jest pierwsza s , najmniejszą liczbą dodatnią z p dzielników jest 2 ^{p 1} , dlatego b _n może być przybliżony przez 2 ^{c _n} , gdzie c _n ~ ¼πn .

Dlatego b _n <4 ⁿ będzie utrzymywać wystarczająco duże n , a biorąc pod uwagę, że 2 ^¼πn <2 ⁿ << (2 ⁿ ) ² = 4 ⁿ , jestem pewien, że nie ma żadnych kontrprzykładów.

Jak to działa

n=input();r=range(1,4**n);d=s,=r*1,

To ustanawia kilka referencji dla naszego iteracyjnego procesu.

• n to dane wejściowe użytkownika: dodatnia liczba całkowita.

• r jest listą [1, ..., 4 ⁿ - 1] .

• s jest kopią r .

  Jednokrotne powtórzenie listy r*1tworzy płytką kopię, więc modyfikacja s nie zmieni r .

• d jest inicjalizowane jako krotki ( krotki ) .

  Ta pierwsza wartość nie jest ważna. Wszystkie pozostałe będą zawierać liczby dzielników dodatnich liczb całkowitych.

for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,

Dla każdej liczby całkowitej k od 1 do 4 ⁿ - 1 wykonujemy następujące czynności.

• del s[k::k+1]każdy zajmuje (k + 1) ^th całkowitą w s - wychodząc z (k + 1) ^XX - i usuwa ten plaster z s .

  Jest to prosty sposób przechowywania początkowego odstępu sita Flavius ​​Josephus w s . Będzie obliczał znacznie więcej niż wymagane warunki początkowe n + 1 , ale użycie pojedynczej forpętli do zaktualizowania zarówno s, jak i d pozwala zaoszczędzić niektóre bajty.

• d+=sum(k%j<1for j in r)*2,zlicza, ile elementów r dzieli k równomiernie i dodaje 2σ ₀ (k) do d .

  Ponieważ d zostało zainicjowane jako krotka singleton, 2σ ₀ (k) jest przechowywany pod indeksem k .

print d.index(s[n]-s[n-1])*3+n

Znajduje to pierwszy wskaźnik f _{n + 1} - f _n w D , który jest najmniejszym , k , tak że 2σ ₀ (k) = f _{n + 1} - f _n , a następnie oblicza się _N jako 3k + 1 i drukuje wyniki.

Java 8, 336 , 305 , 303 , 287 , 283 279 bajtów

57 bajtów usuniętych dzięki Kritixi Lithos

Grał w golfa

class f{static int g(int s,int N){return s<1?N+1:g(s-1,N+N/s);}static int h(int k){int u=0,t=1,i;for(;u!=(g(k,k)-g(k,k-1))/2;t++)for(i=1,u=0;i<=t;)if(t%i++<1)u++;return 3*t-3+k;}public static void main(String[]a){System.out.print(h(new java.util.Scanner(System.in).nextInt()));}}

Bez golfa

class f {
    static int g(int s,int N){return s < 1 ? N + 1 : g(s - 1, N + N / s);}

    static int h(int k) {
        int u = 0, t = 1, i;
        // get the first number with v divisors
        while(u != (g(k, k) - g(k, k - 1))/2){
            u = 0;
            for (i = 1; i <= t; i++)
                if (t % i < 1) u++;
            t++;
        }
        // 3*(t-1)+k = 3*t+k-3
        return 3 * t + k - 3;
    }

    public static void main(String[] a) {
        System.out.print(h(new java.util.Scanner(System.in).nextInt()));
    }
}

Mathematica, 130 116 106 103 bajtów

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[Tr[2+0Divisors@k]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

lub

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[2DivisorSum[k,1&]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

Skończyło się prawie identycznym kodem Jelly @ Pietu1998 ...

Wyjaśnienie

Catch@

Catchcokolwiek jest Throw-ed (wyrzucone).

Do[ ... ,{k,∞}]

Nieskończona pętla; kzaczyna się 1i zwiększa każdą iterację.

f= ...

Przypisz f:

Reverse@Range@#

Znajdź {1, 2, ... , n}. Odwróć to.

#2⌈#/#2+1⌉&

Funkcja wysyłająca pułap (n1 / n2 + 1) * n2

f= ... ~Fold~ ... &

Przypisz ffunkcję, która rekurencyjnie stosuje powyższą funkcję do listy z dwóch powyższych kroków, używając każdego wyjścia jako pierwszego wejścia i każdego elementu listy jako drugiego wejścia. Początkowe „wyjście” (pierwsze wejście) jest pierwszym elementem listy.

Tr[2+0Divisors@k]==f[#+1]-f@#

Sprawdź, czy dwukrotna liczba dzielników kjest równa f (n + 1) - f (n).

If[ ... ,Throw@k]

Jeśli warunek jest spełniony True, Throwwartość k. Jeśli nie, kontynuuj zapętlanie.

3 ... +#&

Pomnóż wynik przez 3 i dodaj n.

Wersja 130 bajtów

Catch@Do[s=#+1;a=k-#;If[3∣a&&2DivisorSigma[0,a/3]==Differences[Nest[i=1;Drop[#,++i;;;;i]&,Range[s^2],s]][[#]],Throw@k],{k,∞}]&

Perl 6 , 154 149 136 107 bajtów

->\n{n+3*first ->\o{([-] ->\m{m??&?BLOCK(m-1).rotor(m+0=>1).flat!!1..*}(n)[n,n-1])/2==grep o%%*,1..o},^Inf}

Nie golfowany:

-> \n {                    # Anonymous sub taking argument n
  n + 3 * first -> \o {    # n plus thrice the first integer satisfying:
    (                      #
      [-]                  #
      -> \m {              # Compute nth sieve iteration:
        m                  # If m is nonzero,
          ?? &?BLOCK(m-1).rotor(m+0=>1).flat # then recurse and remove every (m+1)-th element;
          !! 1..*          # the base case is all of the positive integers
      }                    #
      (n)                  # Get the nth sieve
      [n,n-1]              # Get the difference between the nth and (n-1)th elements (via the [-] reduction operator above)
    ) / 2                  # and divide by 2;
    ==                     # We want the number that equals
    grep o %% *, 1..o      # the number of divisors of o.
  }
  ,^Inf
}

05AB1E ,35 34 39 bajtów

1Qi4ë[N3*¹+NÑg·¹D>‚vyy<LRvy/>îy*}}‚Æ(Q#

Wygląda okropnie, podobnie jak wydajność środowiska uruchomieniowego. Dane wejściowe, które dają małe wartości, wymagają kilku sekund. Nie próbuj liczb takich jak 14; ostatecznie znajdzie wynik, ale zajęłoby wieki.

Wyjaśnienie

Działa jako 2 kolejno nazywane programy. Pierwszy oblicza F _{n + 1} - F _N i druga określa się _n w oparciu o jego definicji, z wykorzystaniem podejścia Bruteforce.

F _{n + 1} - F _n jest obliczane dla każdej iteracji, nawet jeśli jest niezmienna w pętli. To sprawia, że ​​czas kodu jest nieefektywny, ale sprawia, że ​​kod jest krótszy.

Wypróbuj online!