Podano dodatnią liczbę całkowitą n > 2. Konwertujemy go na tablicę w następujący sposób:

1. Jeśli jest równy, 2zwróć pustą tablicę
2. W przeciwnym razie utwórz tablicę wszystkich nczynników pierwszych posortowanych rosnąco, następnie każdy element zamień jego indeksem w sekwencji liczb pierwszych i na koniec przekonwertuj każdy element na tablicę

Na przykład pozwala przekonwertować liczbę 46na tablicę. Po pierwsze, przekonwertuj go na tablicę jego głównych czynników:

[2, 23]

Numer 23jest 9th prime, więc zastąpić 2z pustej tablicy i 23z [9]. Tablica staje się teraz:

[[], [9]]

Najważniejsze czynniki 9to, 3a 3więc:

[[], [3, 3]]

Zrób to samo dla obu 3:

[[], [[2], [2]]]

I w końcu:

[[], [[[]], [[]]]]

Teraz, aby go zakodować, po prostu zamieniamy każdy otwarty nawias na 1i każdy zamykający na 0, następnie usuwamy wszystkie zera końcowe i upuszczamy jeden 1z końca. To jest nasz numer binarny. Korzystając z powyższego przykładu:

[ ] [ [ [ ] ] [ [ ] ] ]

| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V

1 0 1 1 1 0 0 1 1 0 0 0

Teraz po prostu upuść trzy ostatnie zera i ostatnie 1. Liczba staje 10111001się 185dziesiętna. To jest oczekiwany wynik. Zauważ, że w tablicy do konwersji binarnej nawiasy główne tablicy nie są uwzględnione.

Wkład

Dodatnia liczba całkowita nwiększa niż 2.

Wydajność

Zakodowana liczba całkowita n.

Zasady i format IO

• Obowiązują standardowe zasady.
• Dane wejściowe mogą być ciągiem lub liczbą (ale w przypadku ciągu musi być w bazie 10).
• Dane wyjściowe mogą być ciągiem lub liczbą (ale w przypadku ciągu musi być w bazie 10).
• To jest golf golfowy , wygrywa najkrótsza odpowiedź w bajtach!

Przypadki testowe

Więcej przypadków testowych na żądanie.

3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478

Piaskownica

Łuska , 35 31 30 29 26 25 24 22 20 19 15 bajtów

-7 bajtów dzięki @Zgarb!

Zaoszczędź dodatkowe 4 bajty, pośrednio, dzięki Zgarb

ḋhΣhgφṁȯ`Jḋ2⁰ṗp

Wypróbuj online!

Wyjaśnienie

     φ             -- Define a recursive function which calls itself ⁰ and is applied to an Integer
      ṁ       p    -- map then concatenate over its prime factors
             ṗ     --   return their indices into the primes
            ⁰      --   and then recur, applying ⁰ to that number
       ȯ`Jḋ2       --   then surround it between the list [1,0] (binary 2)
    g              -- group adjacent equal elements
   h               -- drop last element (trailing 0s)
  Σ                -- concatenate
 h                 -- drop the last element
ḋ                  -- interpret as base 2

Galaretka ,  22 20  19 bajtów

-1 dzięki Erikowi Outgolfer (zera ogona z obu stron t, a nie z prawej œr)

ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ

Łącze monadyczne przyjmujące liczbę całkowitą większą niż 2 i zwracającą liczbę całkowitą większą niż 0 (2 zwróciłoby 0 zgodnie z oryginalną specyfikacją).

Wypróbuj online!

W jaki sposób?

To prawie dokładnie odwzorowuje podany opis, tylko z pewną porządkową manipulacją w celu utworzenia tablicy binarnej ...

ÆfÆC$ÐLŒṘO%3ḟ2Ḋt0ṖḄ - Link: number n (>=2)
     ÐL             - loop until no more changes occur:
    $               -   last two links as a monad:
Æf                  -     prime factorisation (includes duplicates & vectorises)
  ÆC                -     count primes less than or equal (vectorises)
                    -   ...note for entries of 2 this yields [1]
                    -      then for entries of 1 it yields [], as required
       ŒṘ           - get a Python representation - just like in the OP,
                    -    something like: "[[], [[[]], [[]]]]" (for an input of 46)
         O          - convert to ordinals e.g. [91,91,93,44,32,91,91,91,93,93,44,32,91,91,93,93,93,93]
          %3        - modulo by 3         e.g. [ 1, 1, 0, 2, 2, 1, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0]
            ḟ2      - filter discard twos e.g. [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
              Ḋ     - dequeue             e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0]
               t0   - strip zeros         e.g. [ 1, 0, 1, 1, 1, 0, 0, 1, 1]
                 Ṗ  - pop                 e.g. [ 1, 0, 1, 1, 1, 0, 0, 1]
                  Ḅ - binary to decimal   e.g. 185

Python 2 , 212 177 bajtów

lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
 while n>1:
  j+=1;P=q=1;exec"P*=q*q;q+=1;"*~-j;i+=P%q
  while n%j<1:yield i;n/=j

Wypróbuj online!

Brak wbudowanych liczb pierwszych naprawdę boli liczbę bajtów, i przekracza limit czasu dla TIO z większymi liczbami pierwszymi. Zastosowania XNOR „s czek pierwszości.

Python 2 + gmpy2 , 175 bajtów

lambda n:int(g(n).rstrip("0")[1:-1],2)
g=lambda n:"1%s0"%"".join(map(g,p(n)))
def p(n,i=0,j=1):
 while n>1:
  j+=1;i+=is_prime(j)
  while n%j<1:yield i;n/=j
from gmpy2 import*

Wypróbuj online!

Ta wersja nie przekracza limitów czasu dla większych przypadków testowych (tj. 10000 - 10008).

Mathematica, 125 119 bajtów

Flatten[#//.{{1}->{1,0},a_/;a>1:>{1,List/@PrimePi[Join@@Table@@@FactorInteger@a],0}}]/.{1,d__,1,0..}:>{d}~FromDigits~2&

Stosuje nieco inne podejście; konwertuje indeksy pierwsze na {1, index, 0}i 2 na {1, 0}.

Wypróbuj na Wolfram Sandbox

Stosowanie:

f = Flatten[ ...

f[10008]

1402478

Galaretka , 35 bajtów

ÆfẎW€ÆC2,“”y¹ß€Ṇ?
ÇŒṘḊ⁾][iЀḟ0t1Ṗ’Ḅ

Wypróbuj online!

J, 74 73 66 bajtów

3 :'#.(}.~ >:@i.&1)&.|.2+}.;<@(_2,~_1,[:>:[:_1&p:q:) ::<"0@;^:_ y'

Wypróbuj online!

To prawdziwy bałagan, który z pewnością wymaga dalszej gry w golfa (np. Usunięcia wyraźnej definicji funkcji). Myślę, że boks, który robiłem, jest szczególnie tym, co przywołuje liczbę bajtów, ponieważ tak naprawdę nie wiem, co tam robię (było wiele prób i błędów). Ponadto jestem całkiem pewien, że są pewne wbudowane elementy, o których zapominam (np. Czuję, że _2,~_1,prawdopodobnie mają wbudowane).

Wyjaśnienie (bez golfa)

Preambuła

Usiądźcie wygodnie, bo to nie będzie krótkie wyjaśnienie. Jak na ironię, zwięzły język został sparowany z osobą pełną.

Podzielę to na kilka funkcji

encode  =. 3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::<"0@;^:_ y'
convert =. 3 : '2 + }. ; y'
drop    =. (}.~ >:@i.&1)&.|.
decode  =. #.

• encode koduje liczbę całkowitą za pomocą _1 i _2 zamiast [i]
• convert konwertuje listę _1 i _2 na listę 1 i 0
• drop upuszcza ostatni 1 i końcowe zera
• decode konwertuje z listy binarnej na liczbę

Przejdę przez przykładowe wezwanie na 46, które jest wyrażone w formacie bez golfa

   decode drop convert encode 46
185

Kodować

Tutaj jest wiele do wyjaśnienia.

3 : '<@(_2,~_1, [: >: [: _1&p: q:) ::< "0@;^:_ y'
                                           ^:_      Do until result converges
                                          ;          Raze (remove all boxing)
                                       "0            For each
                               q:                     Factorize
                         _1&p:                        Get index of prime
                   >:                                 Add 1 (J zero-indexes)
            _1,                                       Prepend -1
        _2,~                                          Append -2
     <                                                Box resulting array
                                   ::                If there is an error
                                     <                Box the element

Zauważ, że wyraźna definicja funkcji 3 : '[function]'ocenia funkcję tak, jakby znajdowała się na REPL, z odpowiednim argumentem zastępującym każde wystąpienie y(oznacza to, że mogę uniknąć konieczności używania caps ( [:), atops ( @) i ats ( @:) kosztem kilka bajtów).

Oto, jak to wygląda dla każdej kolejnej iteracji na wejściu 46

┌─────────┐    ┌──┬─────┬─────────┬──┐    ┌──┬──┬──┬──┬───────┬───────┬──┬──┐
│_1 1 9 _2│ => │_1│_1 _2│_1 2 2 _2│_2│ => │_1│_1│_2│_1│_1 1 _2│_1 1 _2│_2│_2│ =>
└─────────┘    └──┴─────┴─────────┴──┘    └──┴──┴──┴──┴───────┴───────┴──┴──┘

┌──┬──┬──┬──┬──┬─────┬──┬──┬─────┬──┬──┬──┐    
│_1│_1│_2│_1│_1│_1 _2│_2│_1│_1 _2│_2│_2│_2│ => the final iteration is just every
└──┴──┴──┴──┴──┴─────┴──┴──┴─────┴──┴──┴──┘    value in its own box

Ta funkcja korzysta z funkcji negative ( ::) w celu zagnieżdżenia wartości w „nawiasach” (stosowane tutaj nawiasy to -1 i -2). Zasadniczo, za każdym razem, gdy rozkładamy na czynniki pierwsze i przekształcamy w indeksy liczb pierwszych, _1 jest dodawane, a _2 jest dołączane, które działają jak nawiasy. Gdy funkcja jest wywoływana na tych elementach, po prostu zwraca je takimi, jakimi są, ponieważ q:wystąpi błąd przy próbie faktoryzacji liczby ujemnej. Jest to także szczęście, że q:ma nie błąd na próby na czynniki 1 i zamiast zwraca pustą tablicę (w razie potrzeby).

Konwertować

3 : '2 + }. ; y'
            ;     Raze (remove boxing)
         }.       Behead (remove head)
     2 +          Add 2

Konwersja jest znacznie prostsza. Po prostu usuwa wszystkie boks, a także pierwszy element, a następnie konwertuje wszystko na 1 i 0 (po prostu dodając 2)

Upuszczać

(}.~ >:@i.&1)&.|.
             &.|.  Reverse, apply the left function, and then undo
 }.~ >:@i.&1        Drop the leading zeroes and first 1
        i.&1         Index of first one
     >:              Add 1
 }.~                 Drop

Spowoduje to odwrócenie listy, znalezienie pierwszej, a następnie upuszczenie wszystkich wartości do tej, a następnie ponowne odwrócenie listy.

Rozszyfrować

Dekodowanie to wbudowana funkcja, #.która pobiera listę 1 i 0 i konwertuje ją na liczbę binarną.

Retina , 244 227 225 bajtów

+%(G`
\d+
$*0¶$&$*
+`^00(0+)
0$1¶$0
A`^(00+?)\1+$
^0+
$0;1
+`(1+)¶0+(?=¶)
$0;1$1
+`¶(11+?)(\1)*$
¶$1¶1$#2$*1
1$

m`^11$
[]
m`^1+
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶
$1;$2$3$2¶
0+;1+¶

)`1+
$.0
T`[]¶`10_
10+$

1
01
+`10
011
^0+

1

Wypróbuj online!

Jest to proste podejście oparte na algorytmie przedstawionym w pytaniu. Generowanie indeksu podstawowego ma złożoność wykładniczą, więc przekroczy limit czasu dla większych danych wejściowych

Wyjaśnienie:

+%(G`                Repeatedly apply on each line:
\d+                      If the line is a number, convert it to unary 0s and 1s
$*0¶$&$*
+`^00(0+)                Generate all prefixes of the zeros greater than 1
0$1¶$0
A`^(00+?)\1+$            Remove non-prime strings of zeros
^0+                      Index the first zero set (00) as 1
$0;1
+`(1+)¶0+(?=¶)           Index the rest of the zeroes as their prime index
$0;1$1
+`¶(11+?)(\1)*$          Compute prime factors of input value
¶$1¶1$#2$*1
1$                       Remove the 1 factor (not really prime)

m`^11$                   Turn all 2 prime factors to []
[]
m`^1+                    Surround all non-2 prime factors in brackets
[¶$.0$*0¶]
+s`(0+);(1+)(.+¶)\1¶     Convert non-2 prime factors to their index
$1;$2$3$2¶
0+;1+¶                   Remove the list of primes

)`1+                     Return all primes back to decimal ready to be repeated
$.0
T`[]¶`10_            Then convert all [ to 1 and ] to 0, and remove linefeeds
10+$                 Remove the final 1 and trailing zeroes

1                    Convert from binary to unary
01
+`10
011
^0+

1                    Convert from unary to decimal

Haskell , 162 160 155 bajtów

sum.zipWith((*).(2^))[0..].tail.snd.span(<1).(r%)
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
_%1=[]
((i,q):p)%n|mod n q<1=r%div n q++0:r%i++[1]|1<3=p%n

Wypróbuj online!

Wyjaśnienie:

r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]definiuje nieskończoną listę krotek liczb pierwszych i ich indeksów: [(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...].

Funkcja (%)pobiera tę listę ri liczbę ni konwertuje liczbę na odwróconą reprezentację tablicy czynników. Odbywa się to krok po kroku, rdopóki nie znajdziemy liczby pierwszej, która dzieli n. My wtedy rekurencyjnie określić reprezentację wskaźnik ten główny i ująć ją w 0i 1a poprzedzić reprezentacji npodzielony przez to prime.

W przypadku n=46, to otrzymuje się liście [0,0,0,1,1,0,0,1,1,1,0,1], z których następnie wiodącymi zerami ( snd.span(<1)) i następne 1( tail) są odrzucane. Następnie lista jest przekształcany na liczbę dziesiętną od elementu mnożenie listę potęgi dwójki i sumowanie otrzymanej listy: sum.zipWith((*).(2^))[0..].

JavaScript, 289 bajtów

Bajty to suma kodu JavaScript bez podziałów wierszy po przecinkach (które są wstawiane tylko w celu lepszego formatowania i czytelności) (256 bajtów) oraz dodatkowe znaki dla przełącznika wiersza poleceń, które są wymagane przy korzystaniu z Chrome (33 bajty).

'use strict'
var f=(n,i=2,r=[])=>n>1?n%i?f(n,i+1,r):f(n/i,i,r.concat(i)):r,
c=(p,r=1,i=2)=>i<p?f(i)[1]?c(p,r,i+1):c(p,r+1,i+1):r-1?f(r).map(h):[],
h=a=>c(a),
s=a=>a.reduce((r,e)=>r+s(e),'1')+' ',
o=i=>+('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1))

I dłuższa, lepiej czytelna wersja:

'use strict';
const f = (n,i=2,r=[]) => n>1 ? n%i ? f(n,i+1,r) : f(n/i,i,r.concat(i)) : r;
const c = (p,r=1,i=2) => i<p ? f(i)[1] ? c(p,r,i+1) : c(p,r+1,i+1) : r-1 ? f(r).map(h) : [];
const h = i => c(i);
const s = a => a.reduce((r,e) => r+s(e),'1')+' ';
const o = i => +('0b'+s(f(i).map(h)).trim().replace(/ /g,'0').slice(1,-1));

Kilka krótkich wyjaśnień:

f jest czysto funkcjonalnym algorytmem faktoryzacji typu tail-recursive.

czlicza, w którym miejscu występuje rliczba pierwsza pw sekwencji liczb pierwszych i zwraca albo [](jeśli p=2i r=1) albo rozkłada na czynniki pierwsze i procesy rza pomocą rekurencji.

hjest małą funkcją pomocniczą, która niestety jest niezbędna, ponieważ mapwywołuje dostarczoną funkcję z numberOfCurrentElementdrugim i wholeArraytrzecim argumentem, zastępując w ten sposób wartości domyślne podane, cjeśli przekażemy tę funkcję bezpośrednio (zajęło mi to trochę czasu, aby dostać się po tej pułapce; zastąpienie hjej definicją byłoby kilka bajtów dłuższe).

sprzekształca wygenerowaną tablicę w ciąg. Używamy blankzamiast 0, abyśmy mogli używać trim()w o.

oto funkcja, która ma zostać wywołana z wartością wejściową izwracającą dane wyjściowe. Generuje reprezentację ciągu binarnego wymaganą przez specyfikację i konwertuje ją na (dziesiętną) liczbę.

Edycja: Chrome należy uruchomić za pomocą, chrome --js-flags="--harmony-tailcalls"aby umożliwić optymalizację rekurencji ogona (patrz https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Wymaga to również użycia trybu ścisłego.

Poniższy test pokazuje, że obliczenia są nieco wolne dla niektórych wartości (najdłuższy to ponad sześć sekund 10007na moim komputerze). Co ciekawe, bez optymalizacji rekurencji obliczeń obliczenia są znacznie szybsze (około 5), gdy nie ma przepełnienia stosu.

for (let i=3; i<=10008; i==10 ? i=10000 : ++i) {
    let time = new Date().getTime();
    let val = o(i);
    time = new Date().getTime() - time;
    document.write(i + ': ' + o(i) + ' (computed in ' + time + ' ms)<br>');
}

tinylisp , 209 bajtów

(load library
(d [(q((N)(map(q((P)([(length(filter prime?(1to P))))))(reverse(prime-factors N
(d B(q((L)(c 1(insert-end 0(foldl concat(map B L
(d T(q((N)(if(mod N 2)(/ N 2)(T(/ N 2
(q((N)(T(from-base 2(t(B([ N

Ostatni wiersz to nienazwana funkcja, która oblicza określone kodowanie. Wypróbuj online!

Wersja do gry w golfa

Oto kod, który miałem przed rozpoczęciem gry w golfa:

(load library)

(def prime-index
 (lambda (P)
  (length (filter prime? (1to P)))))

(def to-list
 (lambda (N)
  (map to-list
   (map prime-index
    (reverse (prime-factors N))))))

(def to-bits
 (lambda (L)
  (cons 1
   (insert-end 0
    (foldl concat
     (map to-bits L))))))

(def trim
 (lambda (N)
  (if (mod N 2)
   (div2 N 2)
   (trim (div2 N 2)))))

(def encode
 (lambda (N)
  (trim
   (from-base 2
    (tail (to-bits (to-list N)))))))

05AB1E , 18 bajtów

ΔÒ.Ø>}¸»Ç3%2K0ܨ2β

Wypróbuj online!

Wyjaśnienie:

Δ    }       # loop until a fixed point
 Ò           # replace each number with its prime factorization
  .Ø>        # replace each prime with its 1-based index
¸»           # after the loop: join to a string
  Ç          # get ASCII value of each character
   3%        # modulo 3 (maps '[' to 1, ']' to 0, ' ' to 2, ',' to 2)
     2K      # remove 2s
       0Ü    # trim trailing 0s
         ¨   # remove the last 1
          2β # parse as base 2