Twoim zadaniem tutaj będzie zaimplementowanie funkcji ^1, która tworzy permutację na dodatnich liczbach całkowitych (bijection z dodatnich liczb całkowitych na siebie). Oznacza to, że każda dodatnia liczba całkowita powinna pojawić się dokładnie raz w permutacji. Złap to twoja funkcja powinna mieć większe prawdopodobieństwo wyprowadzenia liczby nieparzystej niż liczba parzysta.

Teraz może się to wydawać dziwne lub niemożliwe. Z pewnością jest tyle samo liczb nieparzystych, co liczb parzystych? I chociaż ta intuicja jest poprawna dla zbiorów skończonych, tak naprawdę nie obowiązuje dla zbiorów nieskończonych. Na przykład weź następującą permutację:

1 3 2 5 7 4 9 11 6 13 15 8 17 19 10 21 23 12 25 27 14 29 31 16 33 35 18 37 39 20 41 43 22 45 47 24 49 51 26 53 55 ...

Jeśli weźmiesz podsekcję sekwencji o rozmiarze większym niż $1$ , będziesz mieć co najmniej tyle nieparzystych liczb, co liczb parzystych, więc wydaje się, że prawdopodobieństwo dowolnego nieparzystego wyrażenia jest większe niż bycie parzystym. Zauważysz również, że każda liczba nieparzysta lub parzysta ostatecznie pojawi się w sekwencji i może pojawić się tylko raz. Zatem sekwencja jest prawdziwą permutacją.

Definicja prawdopodobieństwa

Aby uniknąć zamieszania lub dwuznaczności, zamierzam jasno wyjaśnić, co oznacza prawdopodobieństwo w tym pytaniu.

Powiedzmy, że mamy funkcję . Prawdopodobieństwo, że liczba będzie nieparzysta, zostanie zdefiniowane jako granica stosunku nieparzystych elementów zbioru do wielkości zbioru gdy zmierza w kierunku nieskończoności.$f$$f\{1\dots n\}$$n$

Na przykład wyżej wspomniana funkcja miałaby prawdopodobieństwo nieparzystości $2/3$ .

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Dodatkowe wyzwania

Oto kilka zabawnych pomysłów do zabawy i być może próby wdrożenia. Są one dla zabawy i nie wpływają w żaden sposób na zdobywanie punktów. Niektóre z nich nie są nawet prawidłowymi rozwiązaniami tego wyzwania, a odpowiedź, która obejmuje tylko rozwiązania problemów 2 lub 3, nie jest prawidłową odpowiedzią i może zostać usunięta .

• Napisz permutację z dziwnym prawdopodobieństwem $1$ . (to jest możliwe)

• Napisz permutację, która ma więcej nieparzystych liczb niż parzystych w dla dowolnego ale ma nieparzyste prawdopodobieństwo .$f\{1\dots n\}$$n$$1/2$

• Napisz permutację, która nie ma zdefiniowanego prawdopodobieństwa (czyli nie ma limitu).

^{1: Tutaj funkcja oznacza program lub funkcję. To tylko fragment kodu, który pobiera dane wejściowe i generuje dane wyjściowe.}

Galaretka , 7 bajtów

Æf^<¥4P

Zamienia 2 s i 3 s w pierwotnym rozkładzie na czynniki pierwsze. Prawdopodobieństwo szans wynosi 2/3 .

Wypróbuj online!

Jak to działa

Æf^<¥4P  Main link. Argument: n

Æf       Compute all prime factors of n, with duplicates.
    ¥4   Combine the two links to the left into a dyadic chain and call it with
         right argument 4.
   <       Compare each prime factor with 4. Yields 1 for 2 and 3, 0 otherwise.
  ^        Bitwise XOR the results with the corresponding prime factors.
         This maps 2 to 3, 3 to 2, and all other primes to themselves.
      P  Take the product of the resulting primes.

Łuska , 11 10 bajtów

-1 bajt dzięki Leo i nieco innej funkcji

Ma to dziwne prawdopodobieństwo 1

!uΣz:NCNİ1

Wypróbuj online!

Indeksuje sekwencję:

[1,2,3,5,7,9,11,4,13,15,17,19,21,23,25,27,29,6,31,33]
1 odd, 1 even, 5 odd, 1 even, 9 odd, 1 even, 13 odd...

Wyjaśnienie

!               Index the following sequence (1-indexed)
 u              remove duplicates                     [1,2,3,5,7,9,11,4,13,15...]
  Σ              Concatenate                          [1,1,2,3,5,3,7,9,11,4,13..]
   z:            Zipwith append                       [[1,1],[2,3,5],[3,7,9,11]..
     N          Natural numbers
      CNİ1      Odd numbers cut into lists of lengths [[1],[3,5],[7,9,11]...]
                corresponding to the Natural numbers

Haskell, 35 34 32 bajtów

f n=n:2*n+1:2*n+3:f(n+2)
(f 0!!)

Implementuje przykładową sekwencję [1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,...].

Wypróbuj online!

Dla odniesienia: stara wersja, 34 bajty (-1 bajt dzięki @xnor):

(!!)$do e<-[0,2..];[e,2*e+1,2*e+3]

Wypróbuj online!

Łuska , 8 bajtów

!uΣzeİ1N

Wypróbuj online!

To implementuje przykładową sekwencję ( 1,3,2,5,7,4...).

Wyjaśnienie

!uΣzeİ1N
   ze       zip together
     İ1       the odd numbers
       N      with the natural (positive) numbers
  Σ         flatten the resulting list
 u          remove duplicates
!           index into the obtained sequence with the input

Wszyscy wykonują Wyzwanie 1, więc zróbmy pozostałe dwa.

Perl 6 , 26 bajtów - wyzwanie 2

{($_==1)+$_-(-1)**($_%%2)}

Wypróbuj online!

Po prostu 1 3 2 5 4 7 6...w parzystej liczbie przypadków zawsze są 2 liczby nieparzyste niż parzyste. W liczbie nieparzystej 1 więcej. Ma to jednak wyraźnie limit (n+2)/(2n+2) -> ½.

Perl 6 , 70 bajtów - Wyzwanie 3

{((1,),(2,4),->@a,@ {@(map(@a[*-1]+2*(*+1),^(4*@a)))}...*).flat[$_-1]}

Wypróbuj online!

Trzeba przyznać, że gra w golfa jest straszna. Indeksuje sekwencję, która zawiera 2⁰ liczb nieparzystych, następnie 2¹ parzystych, następnie 2² nieparzystych, następnie 2³ parzystych i tak dalej.

Prawdopodobieństwo po n takich „blokach”, jeśli n jest nieparzyste, wynosi (2⁰ + 2² + 2⁴ + ... + 2ⁿ⁻¹) / (2ⁿ-1). Suma w liczniku jest równa ⅓ (4 ^{½ (n + 1)} - 1) = ⅓ (2 ^{n + 1} - 1). Prawdopodobieństwo po nieparzystej liczbie bloków wynosi ⅔ (w limicie).

Jeśli dodamy jeszcze jeden blok (i uzyskamy parzystą liczbę n + 1), nie dodamy jednak żadnych liczb nieparzystych (licznik pozostaje taki sam), ale teraz jest (2 ^{n + 1} - 1) liczb w sumie . Nawiasy są anulowane i otrzymujemy prawdopodobieństwo ⅓ (w limicie).

Najwyraźniej ma to mieć 2 różne punkty skupienia ⅓ i ⅔, aby upewnić się, że limit nie istnieje, ale tak naprawdę to nie dowodzi. Moja próba zrobienia solidnego, rygorystycznego dowodu znajduje się w tej odpowiedzi Math.SE: https://math.stackexchange.com/a/2416990/174637 . Mile widziane błędy.

Perl 6 , 39 bajtów - podstawowe wyzwanie.

{my$l=$_ div 3;$_%3??2*($_-$l)-1!!2*$l}

Wypróbuj online!

Chociaż zamieściłem tę odpowiedź z powodu wyzwań 2 i 3, które stanowiły przyjemną małą łamigłówkę mathy, istnieje ścisły wymóg, aby wszystkie odpowiedzi zawierały rozwiązanie podstawowego wyzwania. Oto jest.

To jest przykładowa sekwencja.

Brain-Flak , 120 bajtów

(({})<{{({}[()]<({}(()[{}]))>)}{}({}[({})]<({}<>{}<({}())>)><>)}>)<>({}[()]){{}((<>{}<>[{}]){}[()])<>}{}{(({}){})<>{}}<>

Wypróbuj online!

Wykonuje następującą funkcję:

Ta funkcja generuje sekwencję

2 4 1 6 3 5 7 8 9 11 13 15 17 19 21 10 23 25 27 29...

Funkcja ma dziwne prawdopodobieństwo 1

R, 82 bajty (dodatkowe wyzwanie 1)

f<-function(n){if(sqrt(n)==floor(sqrt(n))){2*sqrt(n)}else{2*(n-floor(sqrt(n)))-1}}

Wypróbuj online!

Jeśli wejście jest idealnym kwadratem, podaje liczbę parzystą. W przeciwnym razie podaje liczbę nieparzystą. Idealne kwadraty mają naturalną gęstość 0, co oznacza, że ​​ta sekwencja daje liczby nieparzyste z prawdopodobieństwem 1.

C (gcc) , 29 bajtów

f(n){return n&3?n+n/2|1:n/2;}

Wypróbuj online!

Co czwarta liczba to nawet:

1 3 5   7 9 11   13 15 17   19 21 23   25 27 29
      2        4          6          8          10

Dodatkowe wyzwanie 1, 52 bajty

f(n,i){for(i=0;n>>i/2;i+=2);return n&n-1?2*n-i-1:i;}

Wypróbuj online!

Zwraca 2 * (x + 1), jeśli n jest równe 2 ^x, a kolejne liczby nieparzyste w przeciwnym razie:

    1   3 5 7   9 11 13 15 17 19 21    23 25
2 4   6       8                     10      

Brain-Flak , 140 138 136 bajtów

({}<(((()())()()))((<>[()])[()()])>){({}[()]<(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)>)}{}({}<{}{}>)

Wypróbuj online!

Wyjaśnienie

Pełni tę funkcję podobną do tej sugerowanej w pytaniu.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Działa głównie w oparciu o fragment, który zrobiłem, aby rzucić stos dla stosów rozmiaru 3.

(({}(({}({}))[({}[{}])]))[({}[{}])])

Ustawiliśmy dwa stosy, jeden z wartościami akumulatorów (dwa parzyste nieparzyste) i jeden z liczbami 4 4 2. W każdej iteracji rzucamy obydwoma stosami i dodajemy górę lewego stosu do góry prawego stosu.

(({}(({}({}))[({}[{}])]))[({}[{}])]<>(({}(({}({}))[({}[{}])]))[({}[{}])])<>)

To zwiększy każdą nieparzystą liczbę o 4, a jedną parzystą liczbę o 2. Gdy przechodzimy przez pętlę, otrzymujemy wzór 2 nieparzystych 1 parzystych, z każdą trafioną dodatnią liczbą całkowitą. Tak więc po prostu zapętlamy nczasy, nbędąc wejściowymi. Ma to asymptotyczne prawdopodobieństwo 2/3 .

Galaretka , 10 bajtów

ÆE;0ṭ2/FÆẸ

Prawdopodobieństwo szans wynosi 2/3 .

Wypróbuj online!

Jak to działa

ÆE;0ṭ2/FÆẸ  Main link. Argument: n

ÆE          Compute the exponents of n's prime factorization.
  ;0        Append a 0.
     2/     Reduce all pairs by...
    ṭ         tack, appending the left argument to the right one.
            This inverts all non-overlapping pairs of exponents.
       F    Flatten the result.
        ÆẸ  Consider the result a prime factorization and compute the corresponding
            integer.

C, 80 bajtów

#define R if(k++==n)return
i,j,k;f(n){for(i=k=1,j=2;;i+=4,j+=2){R i;R i+2;R j;}}

Implementacja przykładowej permutacji z pytania.

Wypróbuj online!

Partia, 36 bajtów

@cmd/cset/an=%1*2,(-~n*!!(n%%3)+n)/3

Realizuje sekwencję podaną w pytaniu.

JavaScript, 23 bajty

n=>n/2+n/2%2+(n%4&&n-1)

Wyjście: 1, 3, 5, 2, 7, 9, 11, 4, 13, 15, 17, 6, 19, 21, 23, 8 ...

• Dla wszystkich n = 4k:
  • f (n) = n / 2 = 2k
• Dla wszystkich n = 4k + b
  • f (n) = n / 2 + b / 2 + n - 1 = 3/2 * (4k + b) + 1/2 * b - 1 = 6k + 2b - 1

Wyzwanie 2:

n=>n^(n>1)

Wyjście: 1, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14

CJam (21 bajtów)

{2b_(&!\_,2*\1$~+2b?}

Demo online pokazujące pierwsze 32 wyniki. To anonimowy blok (funkcja).

Jest to również rozwiązanie dla wyzwania 1: liczby odwzorowane na liczby parzyste są potęgami 2, więc gęstość liczb parzystych na pierwszych n wyjściach wynosi lg (n) / n, który dąży do zera.

Sekcja

{         e# Declare a block; let's call the input x
  2b      e#   Convert to base 2
  _(&     e#   Copy, pull out first digit (1) and set intersection with rest
  !       e#   Boolean not, so empty set (i.e. power of 2) maps to 1 and non-empty
          e#   to 0
  \_,2*   e#   Take another copy, find its length, and double it
  \1$~+   e#   Take the original base 2 array and append ~(2L) = -2L-1
  2b      e#   Convert from base 2, to get 2x-2L-1
  ?       e#   Take the 2L if it was a power of 2, and the 2x-2L-1 otherwise
}

Perl 40 bajtów

$,=$";$i=4;{say$i-3,$i/2,($i+=4)-5;redo}

Brain-Flueue , 88 bajtów

({}<(((<>)[()])[()()])>)<>(((()())()()))<>{({})({})({})({}[()]<({}<>({})<>)>)}{}{}({}){}

Wypróbuj online!

Wyjaśnienie

To implementuje tę samą funkcję, co moja ostatnia odpowiedź, ale używa modelu FIFO firmy Brain-Flueue, aby skrócić niektóre rogi. Oto kilka pierwszych warunków, które generuje.

2 3 1 4 7 5 6 11 9 8 15 13 10 17 15 ...

Pierwsza część kodu to tylko trochę instalacji, kładziemy 0,-1,-3na pierwszym stosie i 2,4,4na drugim stosie. 2,4,4Zostaną wykorzystane do przechodzenia parzystych i nieparzystych numerów tak jak ja w moim Brain-Flak odpowiedź.

Następnie zapętlamy n razy, za każdym razem dodając górę lewego stosu do prawego stosu. Ponieważ Brain-Flueue używa kolejek zamiast stosów, wartości naturalnie rzutują się, gdy ich dotykamy, zapobiegając potrzebie dodatkowego kodu.

Python 2 , 46 104 55 bajtów

lambda n:2*((n-int(n**.5))+.5,n**.5-1)[n!=1>0==n**.5%1]

Wypróbuj online!

Źle odczytałem pytanie, teraz poprawnie zaimplementowałem funkcję, której można użyć do wygenerowania sekwencji zamiast takiej, która generuje sekwencję. Wyłączone również 0z zestawu możliwych wyników.

Prawdopodobieństwo znalezienia nieparzystej dodatniej liczby całkowitej jest teraz zbieżne z 1.

Galaretka , 9 bajtów

Ḥ€’ĖUẎQ⁸ị

Wypróbuj online!

Implementuje 1, 3, 2, 5, 7, 4, 9, 11, 6, ...(prawdopodobieństwo 2/3).

05AB1E , 11 bajtów

·ÅÉā‚ø˜Ù¹<è

Wypróbuj online!

Pyth , 9 bajtów

*Fmxd<d4P

Wypróbuj tutaj! lub Przetestuj więcej za jednym razem!

Możesz użyć tego kodu, aby sprawdzić stosunek liczb nieparzystych do pewnego punktu. Zastąp 10000żądany limit (nie ustawiaj go znacznie wyżej, ponieważ to błędy pamięci).

Km*Fmxk<k4PdS10000clf%T2KlK

Wypróbuj tutaj .

Powyższe daje z grubsza 0,667 . Rzeczywiste prawdopodobieństwo wystąpienia nieparzystych zdarzeń wynosi 2/3 . To podejście stanowi równoważne wdrożenie odpowiedzi Dennisa .

Wyjaśnienie

*Fmxd<d4P   Full program.

        P   Prime factors.
  m         Map over ^.
   x        Bitwise XOR between:
    d          The current prime factor.
     <d4       The integer corresponding to the boolean value of current factor < 4.
*F          Product of the list.

Java 8, 20 bajtów

n->n%4>0?n+n/2|1:n/2

Odpowiedź C na port @nwellnhof .
Niektóre rzeczy, które sam próbowałem, skończyły się bajtami dłuższymi lub nieco niepoprawnymi.

Implementuje: 1,3,5,2,7,9,11,4,13,15,17,6,19,21,23,8,25,27,29,10,31,33,35,12,37,...
z prawdopodobieństwem 3/4.

Wypróbuj tutaj.

Lua, 67 53 bajtów

Wyjaśnienie nadchodzi, kiedy skończę grać w golfa :)

Ten program pobiera jako dane wejściowe liczbę całkowitą za pomocą argumentów wiersza poleceń i wypisuje n-ty element przykładowej sekwencji na STDOUT

n=...print(n%3<1 and n/3*2or n+math.floor(n/3)+n%3-1)

Objaśnienia

n=...                              -- shorthand for the argument
print(                             -- prints out the result of the following ternary
     n%3<1                         -- if n is divisible by 3
       and n/3*2                   -- prints out the corresponding even number
       or n+math.floor(n/3)+n%3-1) -- else prints out the odd number

Liczby parzyste w tej sekwencji są zarówno nliczbą parzystą, jak i nwielokrotnością liczby 3, dlatego wzór n%3*2jest wystarczający do ich wygenerowania.

W przypadku liczb nieparzystych jest to trochę trudniejsze. W oparciu o fakt, że możemy je znaleźć w zależności od prądu n, mamy następującą tabelę:

n       |  1   2   4   5   7   8   10   11  
target  |  1   3   5   7   9   11  13   15
target-n|  +0  +1  +1  +2  +2  +3  +3   +4

Nazwijmy wartość target-n i, którą widzimy za każdym razem n%3==2, ijest zwiększana. Oto nasza formuła:

n+math.floor(n/3)+n%3-1

Liczby nieparzyste są oparte nna których dodajemy i.

Wartość iprzyrostów w tym samym tempie, co podział euklidesowy o 3, z przesunięciem. math.floor(n/3)daje nam tempo przyrostu i n%3-1daje nam przesunięcie, dzięki czemu dzieje się tak n%3==2zamiast n%3==0.