Co za dziwna funkcja

45

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.ff{1n}n

limn|{x:x{1n},odd(f(x))}|n

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


To jest 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{1n}n1/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.

Kreator pszenicy
źródło

Odpowiedzi:

22

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.
Dennis
źródło
Ta odpowiedź jest dość sprytna. Wydaje mi się, że rozumiem, dlaczego to działa, ale możesz chcieć dołączyć dowód, że to działa, ponieważ na początku uznałem to za nieintuicyjne.
Wheat Wizard
6
Dowód, że jest to permutacja: funkcja jest własną odwrotnością. Dowód stosunku: szansa, że ​​wynik jest nieparzysty, to szansa, że ​​oryginał nie miał czynników 3, czyli dokładnie wtedy, gdy nie można go podzielić przez trzy. Ta szansa to 2/3.
tomsmeding
15

Ł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
H.PWiz
źródło
1
Czy możesz wyjaśnić tę funkcję?
Wheat Wizard
8

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!

nimi
źródło
Zapisz paren:(!!)$do ...
xnor
8

Ł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
Lew
źródło
7

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.

Ramillies
źródło
2
To dodatkowe wyzwania. Aby była to prawidłowa odpowiedź, musisz podać rozwiązanie podstawowego wyzwania. Rozwiązanie wyzwania 1 jest również rozwiązaniem podstawowego wyzwania, ale rozwiązanie problemów 2 lub 3 nie.
Peter Taylor,
1
Dodatkowe wyzwania są dla mnie interesujące w tym pytaniu. Podstawowym wyzwaniem nie jest. Ale i tak dodałem jakieś rozwiązanie.
Ramillies
Poprosiłem o dowód, że twoja odpowiedź na wyzwanie 3 nie ma limitu w tym pytaniu Math.SE
Kevin - Przywróć Monikę
@Kevin, dzięki za pytanie. Myślę, że mogłem cię pomylić. Byłem całkiem pewien, że wszystko jest w porządku. Jedyną rzeczą jest to, że często udowadniam wszystko dość rygorystycznie dla siebie, tylko dla spokoju ducha (ponieważ twoje stopy mogą ślizgać się dość łatwo, szczególnie podczas obchodzenia się z takimi nieskończonymi obiektami) - i nie zrobiłem tego tutaj. To wszystko, co chciałem powiedzieć.
Ramillies,
1
@Kevin - w końcu przezwyciężyłem lenistwo (bohaterski czyn!) I zrobiłem dowód. Opublikowałem to jako odpowiedź na twoje pytanie Math.SE. Mam nadzieję, że jest OK (wykonywanie tego rodzaju pracy w nocy nie jest dobrym pomysłem :—)). Okazało się, że nie jest tak straszne, jak początkowo myślałem.
Ramillies,
5

Brain-Flak , 120 bajtów

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

Wypróbuj online!

Wykonuje następującą funkcję:

funkcjonować

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

0 '
źródło
4

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.

KSmarts
źródło
Czy możesz dodać link do TIO ?
H.PWiz
1
58 bajtów
Giuseppe,
56 bajtów
Giuseppe,
53 bajty
Giuseppe
3

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      
nwellnhof
źródło
3

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 .

Kreator pszenicy
źródło
2

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.
Dennis
źródło
1

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!

Steadybox
źródło
1

Partia, 36 bajtów

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

Realizuje sekwencję podaną w pytaniu.

Neil
źródło
1

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

tsh
źródło
n=>n%4?1.5*n|1:n/2jest o 5 bajtów krótszy.
nwellnhof
1

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
}
Peter Taylor
źródło
1

Perl 40 bajtów

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

źródło
1

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.

Kreator pszenicy
źródło
Jaka jest różnica między Flueue a Flak?
FantaC
@tfbninja Flueue używa kolejki zamiast stosu.
Wheat Wizard
ale ... używasz interpretera bflk ... jak to zrobić inaczej
FantaC
@tfbninja -lflueueArgument.
Wheat Wizard
0

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.

Jonathan Frech
źródło
Powinno to zwrócić liczbę, a nie zestaw / listę, o ile rozumiem
Pan Xcoder
Ponadto nie jest to poprawna permutacja, ponieważ zawiera 0.
Pan Xcoder,
@ Mr.Xcoder Dziękujemy za zauważenie.
Jonathan Frech,
0

Galaretka , 9 bajtów

Ḥ€’ĖUẎQ⁸ị

Wypróbuj online!

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

Erik the Outgolfer
źródło
0

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.
Pan Xcoder
źródło
0

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.

Kevin Cruijssen
źródło
0

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.

Katenkyo
źródło
Jeden bajt można łatwo zapisać, usuwając niepotrzebne miejsce ( ...and (n/...).
Jonathan Frech,
@JonathanFrech był w stanie uratować 2 w tym miejscu, całkowicie usuwając nawias, ponieważ and n/3*2ordziała równie dobrze
Katenkyo