„Główna żaba” to dziwne zwierzę, które przeskakuje między liczbami całkowitymi, aż dotrze 3 lub 19 ...

Twój program powinien przyjmować liczbę całkowitą njako dane wejściowe i wyjściowe wyniku poniższego algorytmu ( 3lub 19).

Dla danej liczby całkowitej n >= 2:

1. Niech fbędzie pozycja żaby. Początkowo jest ustawiony nan
2. if f = 3lub f = 19: żaba przestaje skakać - zatrzymać program i wyjście f.
3. if fjest liczbą pierwszą: żaba skacze na pozycję 2×f-1. Wróć do kroku 2.
4. jeśli fjest mieszany: niech dbędzie f„s największym prime dzielnik. Żaba skacze na pozycję f-d. Wróć do kroku 2.

Przykłady:

Przykład z n = 5:

5 > 9 > 6 > 3 stop

Program powinien wyjść 3.

Kolejny przykład z n = 23:

23 > 45 > 40 > 35 > 28 > 21 > 14 > 7 > 13 > 25 > 20 > 15 > 10 > 5 > 9 > 6 > 3 stop

Ponownie program powinien wypisać dane 3.

Przypadki testowe:

10 => 3
74 => 19
94 => 3
417 => 3
991 => 19
9983 => 19

Możesz założyć 1 < n < 1000000(sprawdziłem końce programu pod kątem tych wartości).

Python 2 , 101 93 92 90 88 87 85 bajtów

import sympy
n=input()
while~16&n-3:m=max(sympy.factorint(n));n-=[1-n,m][m<n]
print n

Wypróbuj online!

C (gcc),  87  65 bajtów

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);n=~16&n-3?f(n-k?:n+n-1):n;}

Wypróbuj online!

Wyjaśnienie:

i,k;
f(n)
{
    for (i=n; i>1;)              // Loop until `k` is prime (the largest positive
                                 // `i` inequal to `k` that divides `k` is 1).
        for (k=i; k%--i;);       // Find the largest factor `k`

    n =                          // Returning like this is undefined behaviour,
                                 // but happens to work with gcc. This can be
                                 // replaced with `return` at the cost of 4 bytes.

        ~16&n-3                  // If `n` is 3 or 19, this expression equals 0 and
                                 // the algorithm halts. Otherwise the function
                                 // calls itself to perform the next iteration.

        ? f(n-k ?: n+n-1)        // If `n-k` is non-zero, n is not prime.
                                 // In this case call `f` with the value of `n-k`.
                                 // (Omitting the second `n-k` between `?` and `:`
                                 // is a gcc extension)
                                 // Otherwise call `f` with `2*n-1`.

        : n;                     // All done, `n` is returned.
}

Wersja przenośna (72 bajty):

i,k;f(n){for(i=n;i>1;)for(k=i;k%--i;);return~16&n-3?f(n-k?n-k:n+n-1):n;}

Wypróbuj online!

Z bardziej odpowiednimi nazwami zmiennych:

f,r;o(g){for(f=g;f>1;)for(r=f;r%--f;);g=~16&g-3?o(g-r?:g+g-1):g;}

Wypróbuj online!

Siatkówka , 63 62 bajty

Podziękowania dla Neila za zaoszczędzenie 1 bajtu.

{`^(11+)(?<!^\2+(11+))(?=\1+$)

^(?!(11+)\1+$|111$|1{19}$)1
$_

Wypróbuj online!

Wejścia i wyjścia w jednostkowej (zestaw testów używa dziesiętnego dla wygody). To rozwiązanie staje się niezwykle wolne w przypadku większych nakładów. W 9983przypadku testowego razy na na TIO.

Wyjaśnienie

Z tego powodu {oba etapy programu są po prostu uruchamiane w pętli, aż nie będą już miały wpływu na ciąg. Przeplatamy kompozyty przetwarzania etapowego i liczby pierwsze przetwarzania etapowego. To pozwala nam uniknąć rzeczywistego warunku (który tak naprawdę nie istnieje w Retina). Jeśli bieżąca wartość jest nieodpowiednia dla sceny, scena po prostu nic nie robi.

^(11+)(?<!^\2+(11+))(?=\1+$)

Przetwarza to kompozyty. Dopasowujemy potencjalny dzielnik (11+), ale sprawdzamy, czy nie jest on złożony (?<!^\2+(11+)), więc bierzemy pod uwagę tylko czynniki pierwsze. Ze względu na chciwość +priorytetem jest największy czynnik. Następnie sprawdzamy, czy potencjał ten dzielnik jest rzeczywisty dzielnik próbując dopasować resztę napisu z powtórzeniami nim (?=\1+$). Dzielnik ten jest po prostu usuwany z łańcucha, w ten sposób odejmujesz coś unarowo.

^(?!(11+)\1+$|111$|1{19}$)1
$_

Przetwarza liczby pierwsze, z wyjątkiem 3 i 19 . Negatywne spojrzenie wstecz zapewnia, że ​​dane wejściowe nie są złożone, a nie 3, a nie 19 . Następnie dopasowujemy pojedynczy 1i zastępujemy go całym ciągiem. Jest to jedna forma obliczania n - 1 + n , która oczywiście wynosi 2n-1 .

Gdy trafimy 3 lub 19 , żaden etap nie może dopasować struny i nie będzie już zmieniany.

Łuska , 15 bajtów

Ω€p57§|o←DṠ-o→p

Wypróbuj online!

Wyjaśnienie

Ω€p57§|o←DṠ-o→p  Implicit input n.
Ω                Do this to n until
 €p57            you get a prime factor of 57 (which are 3 and 19):
            o→p   Take last element of the prime factors of n
          Ṡ-      and subtract it from n,
     §|           or if this gives 0 (so n is prime),
       o←D        double and decrement n.

Galaretka , 12 bajtów

_ÆfṂoḤ’$µÐḶṂ

Wypróbuj online!

Jak to działa

_ÆfṂoḤ’$µÐḶṂ  Maink link. Argument: n

        µ     Combine the links to the left into a chain.
         ÐḶ   Repeatedly call the chain monadically until the results are no longer
              unique. Yield the loop, i.e., the first occurrence of the first
              repeated integer, up to and excluding the repetition.
              Let's call the argument of the chain k.
_Æf             Subtract all prime factors of k from k.
   Ṃ            Take the minimum of the differences. This yields 0 iff k is prime.
     Ḥ’$        Compute 2k-1.
    o           Take the logical OR of the results.
              The result is now a rotation of either [3, 5, 9, 6] or
              [19, 37, 73, 145, 116, 87, 58, 29, 57, 38].
          Ṃ   Take the minimum, yielding either 3 or 19.

Wolfram Language (Mathematica) , 6566 68 bajty

#//.i:Except[3|19]:>If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i]&

• -1 bajty, dzięki Misze Ławrow!
• -2 bajty, dzięki Martin!

Wypróbuj online!

Inspirowany wskazówką . Zasadniczo po prostu odtwarza algorytm.

//.jest RepeatedReplacei /;jest Condition. Tak więc kod zastąpi i_(pojedynczą ilość) znakiem If[PrimeQ@i,2i-1,i-#&@@Last@FactorInteger@i], aż do i!=3&&!=19oceny True.

Reper:

05AB1E , 19 18 17 bajtów

[ÐƵηfså#pi·<ëDfθ-

Wypróbuj online!

Wyjaśnienie

[      #            # loop until
 Ð   så             # a copy of the current value is contained in
  Ƶηf               # the unique prime factors of 171
        pi          # if the current value is prime
          ·<        # double and decrement
            ë   -   # else subtract
             Dfθ    # the largest prime factor of a copy of the current value

JavaScript (ES6), 73 71 69 bajtów

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38

Przypadki testowe

f=n=>57%n?f(n-(g=(k,d=1)=>++d<k?k%d?g(k,d):g(k/d):d<n?d:1-n)(n)):n%38

console.log('10   -> ' + f(10))   // 3
console.log('74   -> ' + f(74))   // 19
console.log('94   -> ' + f(94))   // 3
console.log('417  -> ' + f(417))  // 3
console.log('991  -> ' + f(991))  // 19
console.log('9983 -> ' + f(9983)) // 19

Sformatowane i skomentowane

f = n =>                 // given n
  57 % n ?               // if n is neither 3, 19 or 57 (and assuming that n is > 1):
    f(                   //   do a recursive call to f() with:
      n -                //     n minus
      (g = (k, d = 1) => //     the result of the recursive function g():
        ++d < k ?        //       increment d; if d is less than k:
          k % d ?        //         if d is not a divisor of k:
            g(k, d)      //           recursive call to g() with k and d unchanged
          :              //         else:
            g(k / d)     //           recursive call to g() with k = k / d, d = 1
        :                //       else, d is now the highest prime divisor of n:
          d < n ?        //         if d is less than n:
            d            //           n is composite: return d, which results in f(n - d)
          :              //         else:
            1 - n        //           n is prime: return 1 - n, which results in f(2n - 1)
      )(n)               //     initial call to g()
    )                    //   end of recursive call to f()
  :                      // else:
    n % 38               //   return n % 38 (gives 19 as expected if n = 57)

Galaretka , 23 19 bajtów

-4 bajty z mil . Nadal jednak dłużej niż 05AB1E.

Ḥ’$_Æf$ÆP?Ṫµḟ3,19$¿

Wypróbuj online!

Python 2 , 110 105 103 101 bajtów

-2 bajty dzięki @Lynn

f=lambda n,i=2,k=0:i/n and(n*(n&~16==3)or f((2*i-1,k-i)[k>0]))or n%i and f(n,i+1,k)or f(n/i,2,k or n)

Wypróbuj online!

Python 2 , 116 112 105 bajtów

f=lambda n,i=2:i/n*i or n%i and f(n,i+1)or f(n/i)
n=input()
while~16&n-3:n=[2*n-1,n-f(n)][f(n)<n]
print n

Wypróbuj online!

MATL , 22 21 bajtów

Dzięki @Giuseppe za usunięcie 1 bajtu!

`tZp?Eq}tYfX>-]tI19h-

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

`           % Do...while
  t         %   Duplicate. Takes (implicit) input the first time
  Zp        %   Is it prime? 
  ?         %   If so
    Eq      %     Times 2, minus 1
  }         %   Else
    t       %     Duplicate
    YfX>-   %     Prime divisors, maximum, subtract
  ]         %   End
  t         %   Duplicate
  I19h      %   Push array [3 19]
  -         %   Subtract, element-wise. The result is truthy if and only if
            %   it doesn't contain any zero
            % End (implicit). Next iteraton if top of the stack is truthy
            % Display (implicit)

Haskell - 154 bajty

f 3=3
f 19=19
f n
 |(c==[1])=f$2*n-1
 |True=f$n-head c
 where c=z n;v b=reverse[x|x<-[1..(b-1)],b`rem`x==0];z j=case v j of[1]->[1];s->filter((==[1]).v)$s

Prawdopodobnie brakuje tutaj kilku sztuczek golfowych, to moja pierwsza próba golfa haskell.

Neim , 17 16 bajtów

ͻY𝐏𝕚÷D𝐌Ξᚫ<#D𝐏𝐠𝕊

Wyjaśnienie:

ͻ                   Start infinite loop
 D                  Duplicate
  Y                 Push 57
   𝐏                Prime factors: [3 19]
     𝕚              If the second-to-top of stack is in the list
      ÷             Break the loop
       D            Duplicate
        𝐌Ξᚫ<       If prime, double and decrement
            #D𝐏𝐠𝕊   Otherwise, subtract the largest prime factor

Wypróbuj online!

Liczby R + , 102 99 bajtów

function(n){while(!n%in%c(3,19))n="if"(isPrime(n),2*n-1,n-max(primeFactors(n)))
n}
library(numbers)

Wypróbuj online!

R nie jest znany z krótkich wbudowań, a nawet pakiety podążają za nimi!

Java 8, 140 135 134 94 bajtów

n->{for(int f,t,m=0;57%n>0;n=f>n?2*n-1:n-m)for(t=n,f=1;f++<t;)for(;t%f<1;t/=m=f);return n%38;}

-5 bajtów konwertujących rekurencyjną metodę Java 7 na Java 8 lambda z pętlą.
-1 bajt niejawny dzięki odpowiedzi JavaScript @Arnauld poprzez zmianę n!=3&n!=19oraz return n;na 57%n>0i return n%38;.
Myślę, że powinno być możliwe połączenie w jakiś sposób dwóch pętli i sprawdzenie, czy njest liczbą pierwszą, i uzyskanie jej największej liczby w tym samym czasie, ale nie mogę tego rozgryźć (jeszcze). Na razie będzie to początkowa wersja.
-40 dużych bajtów dzięki @Nevay, robiąc to, czego nie mogłem zrobić: łącząc pętle, aby sprawdzić liczby pierwsze i największy czynnik pierwszy na raz.

Wyjaśnienie:

Wypróbuj tutaj (działa nawet 999999w mniej niż 1 sekundę).

n->{                  // Method with integer as both parameter and return-type
  for(int f,          //  Flag-integer
          t,          //  Temp-integer
          m=1;        //  Max prime factor integer, starting at 0
      57%n>0;         //  Loop (1) as long as `n` is not 3, not 19 and not 57:
      n=f>n?          //    After every iteration: if `f` is larger than `n`:
         2*n-1        //     Change `n` to `2*n-1`
        :             //    Else:
         n-m)         //     Change `n` to `n-m`
    for(t=n,          //   Reset `t` to `n`
        f=1;          //   Reset `f` to 1
        f++<t;)       //   Inner loop (2) from 2 to `t` (inclusive)
      for(;t%f<1;     //    Inner loop (3) as long as `t` is divisible by `f`
        t/=m=f;       //     Set `m` to `f`, and set `t` to `t/f`
      );              //    End of inner loop (3)
                      //   End of inner loop (2) (implicit / single-line body)
                      //  End of loop (1) (implicit / single-line body)
  return n%38;        //  Return `n%38`, which is now either 3 or 19
}                     // End of method

Bash, 73 bajty

((57%$1))&&$0 $[(x=$1-`factor $1|sed 's/.* //'`)?x:2*$1-1]||echo $[$1%38]

Wypróbuj online! Zmodyfikowano nieznacznie, aby działał na TIO.

Rekurencyjnie wywołuje własny plik skryptu $0, który nie działa w TIO, ponieważ musi być uruchomiony jako./filename.sh . Akceptuje dane wejściowe jako argument wiersza polecenia.

Używa tej samej sztuczki modułowej, co odpowiedź JS @ Arnauld .

Przypadki testowe

$ for t in 5 23 10 74 94 417 991 9983;{ echo -n "$t -> "; ./prime-frog.sh $t; }
5 -> 3
23 -> 3
10 -> 3
74 -> 19
94 -> 3
417 -> 3
991 -> 19
9983 -> 19

Python 3 , 97 bajtów

f=lambda n:n*(n&-17==3)or f(n-max(k*all(n%k<k%j for j in range(2,k))for k in range(n+1))or 2*n-1)

Wypróbuj online!

Pyth , 19 bajtów

.W!/P57H?P_ZtyZ-ZeP

Sprawdź wszystkie przypadki testowe!

Odpowiedź Łuski zainspirowała mnie do zapisania 2 bajtów ( ,3 19do P57).

Jak to działa

.W! / P57H? P_ZtyZ-ZeP - Pełny program.

.W - funkcjonalne podczas. Podczas gdy A (wartość) jest prawdziwa, wartość = B (wartość). Zwraca ostatnią wartość.
    P57 - Czynniki pierwsze 57 ([3, 19]).
   / H - Policz wystąpienia bieżącej wartości.
  ! - Logiczne NIE. 0 -> Prawda, wszystko inne -> Falsy.
        ? P_Z - Jeśli bieżąca wartość jest liczbą pierwszą, to:
            tyZ - Podwoj bieżącą wartość, zmniejszenie.
               -ZeP - W przeciwnym razie odejmij od siebie maksymalny współczynnik liczby bieżącej wartości bieżącej.
                     - Drukuj niejawnie.

PowerShell , 150 126 bajtów

for($n="$args";57%$n){$a=$n;$d=for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}};if($n-in$d){$n+=$n-1}else{$n-=$d[-1]}}$n%38

Wypróbuj online! (ostrzeżenie: wolne dla większych liczb)

Metoda iteracyjna. Program PowerShell nie ma żadnych wbudowanych głównych faktoryzacji, więc pożycza kod z mojej odpowiedzi na temat znajomych Prime Factors .

Pierwsza jest nasza forpętla. Setup ustawia $nsię na wartość wejściową, a warunkowe utrzymuje pętlę tak długo, jak długo 57%$njest niezerowa (dzięki Arnauldowi za tę sztuczkę). Wewnątrz pętli najpierw otrzymujemy listę głównych czynników $a(ustawionych na $n). To jest kod pożyczony od kumpli Prime Factors. Jeśli dane wejściowe $asą już pierwotne, funkcja zwróci tylko $a(ważne później). To (potencjalnie po prostu $a) zostaje zapisane $d.

Dalej jest if/ elsewarunkowy. W przypadku ifczęści sprawdzamy, czy $njest -in $d. Jeśli tak, to znaczy, że $njest liczbą pierwszą, więc bierzemy $n=2*$n-1lub $n+=$n-1. W przeciwnym razie jest złożony, więc musimy znaleźć największy czynnik pierwszy. Oznacza to, że musimy podjąć ostatnią [-1]z $di odejmować, że od $nz $n-=. Działa to, ponieważ zapętlamy się od 2i dlatego ostatni element $dbędzie już największy.

Po zakończeniu zapętlania po prostu umieszczamy $n%38(ponownie, dzięki Arnauld) w potoku, a dane wyjściowe są niejawne.

APL (Dyalog Unicode) , 113 90 59 bajtów

⎕CY 'dfns'
g←{1pco ⍵:f(2×⍵)-1⋄f⍵-⊃⌽3pco ⍵}
f←{⍵∊3 19:⍵⋄g ⍵}

Wypróbuj online!

TIO działa z wartościami do ~ 3200. Przetestowano na moim komputerze dla ostatniego przypadku testowego. Aby przetestować na TIO, po prostu dodaj f valuena dole kodu. Nie ma już zastosowania, dzięki @ Adám za zwrócenie uwagi, że mój algorytm sprawdzania pierwotności był naprawdę zły i dostarczenie mi zamiennika; także dla 23-bajtowego zapisu.

Edytowane, aby naprawić liczbę bajtów.

Jak to działa

⎕CY 'dfns'                      # Imports every Defined Function, which is shorter than importing just the function I used (pco).

g←{1pco ⍵:f(2×⍵)-1⋄f⍵-⊃⌽3pco ⍵} 
g←                              # define g as
   1pco ⍵:                      # if the argument ⍵ is prime
          f(2×⍵)-1              # Call f over 2×⍵-1
                  ⋄f            # else, call f over
                    ⊃           # the first element of the
                      3pco ⍵    # list of prime factors of ⍵
                     ⌽          # reversed

f←{⍵∊3 19:⍵⋄g ⍵}
f←                              # Define f as
   ⍵     :                      # if the argument ⍵
    ∊                           # is in
     3 19                       # the list [3, 19]
          ⍵                     # return the argument ⍵
           ⋄                    # else
            g ⍵                 # call g over the argument ⍵

Aksjomat, 93 bajty

h(n)==(repeat(n=3 or n=19 or n<2=>break;prime? n=>(n:=2*n-1);n:=n-last(factors(n)).factor);n)

test:

(4) -> [[i,h(i)] for i in [10,74,94,417,991,9983]]
   (4)  [[10,3],[74,19],[94,3],[417,3],[991,19],[9983,19]]
                                                  Type: List List Integer

Byłaby funkcja 68 bajtów

q x==(n<4=>3;n=19=>n;prime? n=>q(2*n-1);q(n-last(factors n).factor))

ale dla n = 57991 (o ile dobrze pamiętam), to przestaje być zarezerwowane miejsce na stosie.

Python 2 , 93 bajty

Port z odpowiedzią TFeld jest bez bibliotekami zewnętrznymi.

n=input()
while~16&n-3:
 f=n;i=2
 while i<f:
	if f%i:i+=1
	else:f/=i
 n-=[1-n,f][f<n]
print n

Wypróbuj online!