Wyzwanie:

Biorąc pod uwagę liczbę, weź największą liczbę pierwszą dokładnie od niej, odejmij ją od tej liczby, zrób to ponownie z tym nowym numerem z największą liczbą pierwszą mniejszą i kontynuuj robienie tego, aż będzie mniejsza niż 3. Jeśli osiągnie 1, twoja program powinien wypisać prawdziwą wartość, w przeciwnym razie program powinien wypisać wartość falsey.

Przykłady:

Wszystko to powinno dać prawdziwą wartość:

3
4
6
8
10
11
12
14
16
17
18
20
22
23
24
26
27
29
30
32
34
35
37
38
40
41
42
44
46
47
48
50

Wszystkie powinny dać wartości falsey:

5
7
9
13
15
19
21
25
28
31
33
36
39
43
45
49

Zasady:

• Możesz napisać program lub funkcję.
• Możesz założyć, że dane wejściowe są większe niż 2.
• Obowiązują standardowe luki
• To jest golf golfowy, więc wygrywa najkrótsza odpowiedź!

Galaretka , 9 8 bajtów

’ÆRṪạµ¡Ḃ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

’ÆRṪạµ¡Ḃ  Main link. Argument: n

     µ    Combine all atoms to the left into a chain.
’           Decrement; yield n - 1.
 ÆR         Prime range; yield all primes in [2, ..., n -1].
   Ṫ        Tail; yield p, the last prime in the range.
            If the range is empty, this yields p = 0.
    ạ       Compute the absolute difference of p and n.
      ¡   Call the chain to the left n times.
          This suffices since each iteration decreases n, until one of the fixed
          points (1 or 2) is reached.
       Ḃ  Bit; return the parity of the fixed point.

Retina , 31 bajtów

.+
$*
+`1(?!(11+)\1+$)11+
1
^1$

Odbitki 0(fałsz) lub 1(prawda).

Wypróbuj online! (Pierwszy wiersz włącza pakiet testowy oddzielony od linii).

Wyjaśnienie

.+
$*

Konwertuj dane wejściowe na jednostkowe, przekształcając dane wejściowe Nw Nkopie pliku 1.

+`1(?!(11+)\1+$)11+
1

Wielokrotnie usuwaj największą liczbę pierwszą mniejszą niż wartość wejściowa. Jest to oparte na standardowym teście pierwotności z wyrażeniem regularnym .

^1$

Sprawdź, czy wynik jest pojedynczy 1.

Pyth, 18 15 14 bajtów

Dzięki @Maltysen za -1 bajtów

#=-QefP_TUQ)q1

Program, który pobiera dane ze STDIN i drukuje Truelub Falseodpowiednio.

Wypróbuj online

Jak to działa

#=-QefP_TUQ)q1  Program. Input: Q
#          )    Loop until error statement (which occurs when Q<3):
         UQ      Yield [0, 1, 2, 3, ..., Q-1]
     fP_T        Filter that by primality
    e            Yield the last element of that
 =-Q             Q = Q - that
            q1  Q is 1 (implicit variable fill)
                Implicitly print

Stara wersja z redukcją, 18 bajtów

qu-G*<HGH_fP_TSQQ1

Wypróbuj online

Jak to działa

qu-G*<HGH_fP_TSQQ1  Program. Input: Q
              SQ    Yield [1, 2, 3, ..., Q]
          fP_T      Filter that by primality
         _          Reverse it
 u                  Reduce it:
                Q    with base case Q and
                     function G, H -> 
     <HG              H<G
    *   H             *H (yields H if H<G, else 0)
  -G                  Subtract that from G
q                1  The result of that is 1
                    Implicitly print

JavaScript (ES6), 64 63 bajtów

Zapisano 1 bajt dzięki @Neil

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

Napisałem to w 2 minuty ... i zadziałało idealnie za pierwszym razem. Pierwszy użytkownik, który znajdzie nieunikniony błąd, wygrywa ....

Wypróbuj to

g=(x,n=x-1)=>n<2?x:x%n?g(x,n-1):g(x-1)
f=x=>x<3?x%2:f(x-g(x-1))

<input type="number" value=3 min=3 onchange="A.innerHTML=f(this.value)"><br>
<p id=A>1</p>

Jak to działa

Najpierw definiujemy g (x) jako funkcję, która znajduje pierwszą liczbę pierwszą p <= x . Odbywa się to przy użyciu następującego procesu:

1. Zacznij od n = x-1 .
2. Jeśli n <2 , x jest liczbą pierwszą; zwróć x .
3. Jeśli x jest podzielne przez n , zmniejsz x i przejdź do kroku 1.
4. W przeciwnym razie zmniejsz wartość n i przejdź do kroku 2.

Rozwiązanie tego wyzwania, f (x) , jest teraz dość proste:

1. Jeśli x <3 , zwróć x = 1 .
2. W przeciwnym razie odejmij g (x-1) i spróbuj ponownie.

Pyke, 15 11 bajtów

WDU#_P)e-Dt

Wypróbuj tutaj!

            - stack = input
W           - while continue:
  U#_P)     -     filter(is_prime, range(stack))
       e    -    ^[-1]
 D      -   -   stack-^
         Dt -  continue = ^ != 1

Zwraca wartość 1true, a jeśli wartość false - wyjątek

Julia, 32 bajty

Chociaż nie będzie to najkrótsze rozwiązanie wśród języków, może to być najkrótsze z języków czytelnych dla człowieka ...

!n=n>2?!(n-primes(n-1)[end]):n<2

Lub, mówiąc nieco inaczej

function !(n)
  if n>2
    m=primes(n-1)[end]   # Gets largest prime less than n
    return !(n-m)        # Recurses
  else
    return n<2           # Gives true if n is 1 and false if n is 2
  end
end

Nazywany na przykład przez !37.

Mathematica, 32 bajty

2>(#//.x_/;x>2:>x+NextPrime@-x)&

Jest to nienazwana funkcja, która przyjmuje liczbę całkowitą i zwraca wartość logiczną.

Wyjaśnienie

Tutaj jest dużo składni i zabawnej kolejności czytania, więc ...

   #                               This is simply the argument of the function.
    //.                            This is the 'ReplaceRepeated' operator, which applies
                                   a substitution until the its left-hand argument stops
                                   changing.
       x_/;x>2                     The substitution pattern. Matches any expression x as
                                   long as that expression is greater than 2.
              :>                   Replace that with...
                  NextPrime@-x     Mathematica has a NextPrime built-in but no
                                   PreviousPrime built-in. Conveniently, NextPrime
                                   works with negative inputs and then gives you the 
                                   next "negative prime" which is basically a
                                   PreviousPrime function (just with an added minus sign).
                x+                 This gets added to x, which subtracts the previous
                                   prime from it.
2>(                           )    Finally, we check whether the result is less than 2.

Python3, 102 92 90 89 88 bajtów

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

Zapraszamy do gry w golfa! Widzę, że gmpyzawiera funkcję next_prime, ale nie mogę jej jeszcze przetestować :(

-2 bajty, dzięki @JonathanAllan !

-1 bajt, dzięki @Aaron !

Przypadki testowe

f=lambda n:n<2if n<3else f(n-[x for x in range(2,n)if all(x%y for y in range(2,x))][-1])

s="3 4 6 8 10 11 12 14 16 17 18 20 22"
h="5 7 9 13 15 19 21 25 28 31 33 36 39"

for j in s.split(" "):print(f(int(j)))
for j in h.split(" "):print(f(int(j)))

Dane wyjściowe to 13 wartości prawdziwych i 13 wartości falsey. szawiera prawdziwe przypadki i hfalseys.

Python, z sympią, 60 bajtów

import sympy
f=lambda n:n>2and f(n-sympy.prevprime(n))or n<2

Moja poprzednia metoda miała 83 bajty bez sympy przy użyciu rekurencji, ale wziąłem prawdę / falsey, aby oznaczać dającą się odróżnić i spójną, ale zostałem poinformowany, że to niepoprawna interpretacja. Nie mogę go uratować z powodu ogona, ale zostawię go tutaj, na wypadek, gdyby ktoś wiedział, jak to zrobić:

f=lambda n,p=0:n>2and(any(p%x==0for x in range(2,p))and f(n,p-1)or f(n-p,n+~p))or n

Vitsy, 28 26 bajtów

Można to zdecydowanie skrócić.

<]xN0)l1)-1[)/3D-];(pD-1[D

W pobliżu

<                    Traverse the code in this direction, rotating on the line.
                     For the sake of reading the code easier, I'm reversing the
                     code on this line. This will be the order executed.

 D[1-Dp(;]-D3/)[1-)1l)0Nx]
 D                         Duplicate the top member of the stack.
  [      ]                 Do the stuff in brackets until break is called.
   1-                      Subtract 1 from the top item of the stack.
     D                     Duplicate the top member of the stack.
      p(                   If the top member is a prime...
        ;                  break;
          -                Pop a, b, push a - b.
           D3/)[         ] If this value is less than 3, do the bracketed code.
                1-         Subtract the top item of the stack by 1.
                  )        If the top item is zero...
                   1       Push 1.
                    l)     If the length of the stack is zero...
                      0    Push 0.
                       N   Output the top member of the stack.
                        x  System.exit(0);

Wypróbuj online!

MATL , 13 bajtów

`tqZq0)-t2>}o

Wypróbuj online! Lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Wyjaśnienie

`        % Do...while
  t      %   Duplicate. Takes input implicitly in the first iteration
  qZq    %   All primes less than that
  0)     %   Get last one
  -      %   Subtract (this result will be used in the next iteration, if any)
  t      %   Duplicate
  2>     %   Does it exceed 2? If so: next iteration. Else: execute the "finally" 
         %   block and exit do...while loop
}        % Finally
  o      %   Parity. Transforms 2 into 0 and 1 into 1
         % End do...while implicitly
         % Display implicitly

CJam , 21 16 bajtów

Dzięki Dennis za oszczędność 4 bajtów.

ri{_1|{mp},W=-}h

Wypróbuj online!

Wyjaśnienie

ri       e# Read input and convert to integer N.
{        e# Run this block as long as N is positive (or until the program aborts
         e# with an error)...
  _1|    e#   Duplicate and OR 1. This rounds up to an odd number. For N > 2, this
         e#   will never affect the greatest prime less than N.
  {mp},  e#   Get all primes from 0 to (N|1)-1.
         e#   For N > 2, this will contain all primes less than N.
         e#   For N = 2, this will contain only 2.
         e#   For N = 1, this will be empty.
  W=     e#   Select the last element (largest prime up to (N|1)-1).
         e#   For N = 1, this will result in an error and terminate the program, which
         e#   still prints the stack contents though (which are 1, the desired output).
  -      e#   Subtract from N. Note that this gives us 0 for N = 2, which terminates the 
         e#   loop.
}h

Perl, 42 bajty

Obejmuje +1 dla -p

Uruchom z wejściem na STDIN

reach1.pl:

#!/usr/bin/perl -p
$_=1x$_;$_=$`while/\B(?!(11+)\1+$|$)|11$/

Używa klasycznego wyrażenia regularnego

.NET Regex, 38 bajtów

Aby pokazać, że można to sprawdzić w jednym wyrażeniu regularnym.

^(?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+.$

Zakłada się, że dane wejściowe są jednostkowe.

Wyjaśnienie

Po prostu implementuje wymaganie do tego słowa, kilkakrotnie usuwając największą liczbę pierwszą i sprawdzając, czy reszta to 1.

• (?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: Grupa bez śledzenia wstecznego upewnia się, że znaleziona największa liczba pierwsza nie jest nadpisywana, i +po prostu powtarza proces dopasowywania największej liczby pierwszej.

  • (?<=(.*))..+(?<!^\1\2+(.+.)|$): Dopasuj największą liczbę pierwszą mniejszą niż pozostała liczba

    • (?<=(.*)): Zapisz, ile odjęliśmy, aby ustalić „punkt kontrolny” dla potwierdzenia.

    • ..+: Poszukaj największej liczby ...

    • (?<!^\1\2+(.+.)|$): ... która jest liczbą pierwszą i jest mniejsza niż pozostała liczba.
      • (?<!^\1\2+(.+.)): Zwykła rutyna testu wstępnego, z ^\1tackingiem z przodu, aby upewnić się, że sprawdzamy dopasowaną ilość..+
      • (?!<$): Podaj mniej niż pozostała liczba

Perl 6 ,  54 53 52  51 bajtów

{($_,{$_-($_-1...2).first: *.is-prime}...3>*)[*-1]==1}
{($_,{$_-($_-1...2).first: *.is-prime}...3>*).any==1}
{any($_,{$_-($_-1...2).first: *.is-prime}...3>*)==1}

{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}

Wyjaśnienie:

# bare block lambda with implicit parameter ｢$_｣
# used to generate all of the rest of the elements of the sequence
{
  # create an any Junction of the following list
  any(
    $_, # initialize sequence with the inner block's argument

    # bare block lambda with implicit parameter ｢$_｣
    {
      # take this inner block's argument and subtract
      $_ -

      ( ^$_ )            # Range up-to and excluding ｢$_｣
      .grep(*.is-prime)\ # find the primes
      [ * - 1 ]          # return the last value
    }

    ...   # keep doing that until

    3 > * # the result is less than 3

  # test that Junction against ｢1｣
  # ( returns an ｢any｣ Junction like ｢any(False, False, True)｣ )
  ) == 1
}

Przykład:

# show what is returned and if it is truthy
sub show ($_) {
  # ｢.&{…}｣ uses the block as a method and implicitly against ｢$_｣
  my $value = .&{any($_,{$_-(^$_).grep(*.is-prime)[*-1]}...3>*)==1}
  say join "\t", $_, ?$value, $value.gist;
}

show 3;  # 3    True    any(False, True)
show 4;  # 4    True    any(False, True)
show 5;  # 5    False   any(False, False)
show 10; # 10   True    any(False, False, True)
show 28; # 28   False   any(False, False, False)
show 49; # 49   False   any(False, False)
show 50; # 50   True    any(False, False, True)

Nieregularny , 63 bajty

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n
1(?!(11+)\1+$)11+~1
^11$~0
N

Stworzyłem ten język dwa dni temu, a podstawowe założenia są takie, że nie ma wbudowanych pętli, jedynymi funkcjami są podstawowa arytmetyka i podejmowanie decyzji, a ocena programu oparta jest na wyrażeniach regularnych.

Wyjaśnienie

p~?1_$-1p:;
n=i(0)?1_$-1p:;
_~
N=n

Ta część przekształca dane wejściowe w jednoargumentowy. Wielokrotnie odejmuje 1 od wartości wejściowej, aż będzie równa 0, dodając za 1_każdym razem. Następnie usuwa wszystkie _s. Gdybym nie zapomniał breakkodu w swoim kodzie, można go zapisać w następujący sposób:

p~?1_$-1p:;
_~
n=i(0)?1_$-1p:;

Następna część wielokrotnie usuwa największą liczbę pierwszą z wejścia, aż będzie równa 1lub 11, z 11zastąpieniem przez 0.

1(?!(11+)\1+$)11+~1
^11$~0
N

Użyłem wyrażenia regularnego z odpowiedzi Martina Endera .

Haskell, 79 bajtów

Niezbyt krótkie, ale bezsensowne :)

(<2).until(<3)(until(flip(`until`(+1))2.(.)(<1).mod>>=(==))pred.pred>>=flip(-))

PowerShell v2 +, 81 bajtów

param($n)while($n-gt2){$n-=(($n-1)..2|?{'1'*$_-match'^(?!(..+)\1+$)..'})[0]}!--$n

Pobiera dane wejściowe $n. Wchodzi w whilepętlę, dopóki $njest jeszcze 3większa lub większa. Każda iteracja odejmuje liczbę od $n. Liczba to wyniki testu pierwotności wyrażenia regularnego zastosowanego względem zakresu ($n-1)..2za pośrednictwem operatora Where-Object( ?), a następnie pierwszy [0]z wyników (ponieważ zakres zmniejsza się, w wyniku czego wybierany jest największy). Po zakończeniu pętli $nalbo będzie, 1albo 2z definicji, więc wstępnie dekrementujemy $n(zamieniając ją na jedną z nich 0lub 1) i bierzemy wartość logiczną, a nie !jej. Pozostaje to w potoku, a dane wyjściowe są niejawne.

Przykłady

PS C:\Tools\Scripts\golfing> 3..20|%{"$_ --> "+(.\can-the-number-reach-one.ps1 $_)}
3 --> True
4 --> True
5 --> False
6 --> True
7 --> False
8 --> True
9 --> False
10 --> True
11 --> True
12 --> True
13 --> False
14 --> True
15 --> False
16 --> True
17 --> True
18 --> True
19 --> False
20 --> True

Matlab, 51 bajtów

v=@(x)x-max(primes(x-1));while(x>=3)x=v(x);end;x==1

Jest to BARDZO podobne do rozwiązania JS6 firmy ETHProductions , ale wymaga, aby zmienna znajdowała się w obszarze roboczym.

Python 2.7: 88 87 bajtów

r=lambda n:n>2and r(n-[a for a in range(2,n)if all(a%b for b in range(2,a))][-1])or n<2

Dzięki @TuukkaX za -1 więcej bajtów!

Floroid , 45 30 29 bajtów

f=Bb:b<2Fb<3Gf(b-en(b-1)[-1])

Clojure, 125 bajtów

#(loop[x %](if(> x 2)(recur(- x(loop[y(dec x)](if(some zero?(vec(for[z(range 2 y)](mod y z))))(recur(dec y))y))))(quot 1 x)))

Tak, to jeden długi fragment kodu. Najbardziej pełny język uderza ponownie!

Nie golfowany:

(defn subprime [n]
  (loop [x n]
    (if (> x 2)
      (recur
        (- x
          (loop [y (dec x)]
            (if (some zero? (vec (for [z (range 2 y)] (mod y z))))
              (recur (dec y)) y))))
      (quot 1 x))))