Kann die Zahl 1 erreichen, indem sie wiederholt die größte Primzahl abzieht, die darunter liegt?

27

Herausforderung:

Wenn Sie eine Zahl haben, nehmen Sie die größte Primzahl strikt kleiner als diese, subtrahieren Sie sie von dieser Zahl, wiederholen Sie dies zu dieser neuen Zahl mit der größten Primzahl kleiner als diese und fahren Sie fort, bis sie kleiner als 3 ist. Wenn sie 1 erreicht, erhalten Sie Das Programm sollte einen Wahrheitswert ausgeben, ansonsten sollte das Programm einen Falsey-Wert ausgeben.

Beispiele:

All dies sollte einen wahrheitsgemäßen Wert haben:

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

All dies sollte falsche Werte ergeben:

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

Regeln:

  • Sie können entweder ein Programm oder eine Funktion schreiben.
  • Sie können davon ausgehen, dass die Eingabe größer als 2 ist.
  • Es gelten Standardlücken
  • Das ist also gewinnt die kürzeste Antwort!
Loovjo
quelle
related oeis.org/A175071
flawr
1
5-3 = 2, 2 - (- 2) = 4, 4-3 = 1. (/ wiseguy)
@Hurkyl -2 = -1 × 2, es ist also keine Primzahl ;-)
ETHproductions
1
@ETHProductions: Ah, aber -1 ist eine Einheit; Diese Faktorisierung widerspricht nicht der Primalität von -2 und nicht mehr als 2 = (- 1) × (-2) von 2. (oder sogar 2 = 1 × 2)
3
@ETHproductions: Die rationalen Zahlen sind interessant, weil es zwei sehr unterschiedliche Ansätze gibt, die in der Praxis nützlich sind! Die rationalen Zahlen haben keine Primzahlen (nicht einmal 2!), Weil alles eine Einheit ist. Sie können die Rationals jedoch auch als Konstruktion aus den ganzen Zahlen betrachten und sie mit den Primzahlen der ganzen Zahlen untersuchen. (zB wer nach der primären Faktorisierung von 9/10as fragt, 2^(-1) 3^2 5^(-1)denkt in Bezug auf das letztere)

Antworten:

8

Gelee , 9 8 Bytes

’ÆRṪạµ¡Ḃ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

’Æ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.
Dennis
quelle
11

Retina , 31 Bytes

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

Druck 0(falsy) oder 1(truthy).

Probieren Sie es online! (Die erste Zeile aktiviert eine durch Zeilenvorschub getrennte Testsuite.)

Erläuterung

.+
$*

Konvertieren Sie die Eingabe in Unary, indem Sie die Eingabe Nin NKopien von konvertieren 1.

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

Entfernen Sie wiederholt die größte Primzahl, die kleiner als die Eingabe ist. Dies basiert auf dem Standard-Primalitätstest mit Regex .

^1$

Prüfen Sie, ob das Ergebnis eine Single ist 1.

Martin Ender
quelle
Wie kommt es, dass Sie Retina ohne Unary verwenden können? Oo
Addison Crump
@Syxer die ersten beiden Zeilen konvertieren die Eingabe in unary.
Martin Ender
Bedeutet das nicht, dass Sie sie entfernen und unäre Eingaben anfordern können?
Addison Crump
2
@Syxer Ich könnte, aber ich habe damit aufgehört. Es scheint ein zwielichtiges E / A-Format zu sein, und jetzt, da die Konvertierung 6 Bytes beträgt (im Gegensatz zu den ~ 200, die es früher gab), zählt Retina meiner Meinung nach nicht mehr als "Eingaben in Dezimalzahlen können nicht vernünftigerweise akzeptiert werden".
Martin Ender
Ah ich sehe. Ich habe in der Netzhaut nur unäre Eingaben gesehen, daher meine Verwirrung.
Addison Crump
8

Pyth, 18 15 14 Bytes

Vielen Dank an @Maltysen für -1 Byte

#=-QefP_TUQ)q1

Ein Programm, das Eingaben in STDIN aufnimmt und druckt Trueoder Falseentsprechend.

Probieren Sie es online aus

Wie es funktioniert

#=-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

Alte Version mit Reduzierung, 18 Bytes

qu-G*<HGH_fP_TSQQ1

Probieren Sie es online aus

Wie es funktioniert

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
TheBikingViking
quelle
Stist U15 Zeichen
Maltysen
7

JavaScript (ES6), 64 - 63 Byte

1 Byte dank @Neil gespeichert

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))

Ich habe das in 2 Minuten geschrieben ... und es hat beim ersten Mal perfekt funktioniert.Erster Benutzer, der den unvermeidlichen Fehler findet, gewinnt ....

Versuch es

Wie es funktioniert

Zuerst definieren wir g (x) als die Funktion, die die erste Primzahl p <= x findet . Dies geschieht nach folgendem Verfahren:

  1. Beginnen Sie mit n = x-1 .
  2. Wenn n <2 ist , ist x eine Primzahl; Rückkehr x .
  3. Wenn x durch n teilbar ist , dekrementiere x und fahren Sie mit Schritt 1 fort.
  4. Andernfalls dekrementieren Sie n und fahren Sie mit Schritt 2 fort.

Die Lösung für diese Herausforderung, f (x) , ist jetzt ziemlich einfach:

  1. Wenn x <3 ist , wird x = 1 zurückgegeben .
  2. Andernfalls subtrahiere g (x-1) und versuche es erneut.
ETHproductions
quelle
4326, die true zurückgeben sollte, scheint nicht zurückzukehren, aber 4328 (true) und 4329 (false), ist dies eine JS-Einschränkung oder ein Fehler?
Jonathan Allan
@JonathanAllan 4326 wird too much recursionin Firefox 48 zur Browserkonsole geworfen , sodass die Rekursion vermutlich das Rekursionslimit von FF überschreitet.
ETHproductions
Ja, die nächste Primzahl ist 4297 (und die nächste 4327), weshalb 4328 funktioniert.
Jonathan Allan
4
x%2sollte Ihnen ein Byte sparen x==1.
Neil
@Neil Daran hätte ich nie gedacht :-)
ETHproductions
6

Pyke, 15 11 Bytes

WDU#_P)e-Dt

Probieren Sie es hier aus!

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

Gibt 1true zurück und löst eine Ausnahme aus, wenn false

Blau
quelle
5

Julia, 32 Bytes

Während es nicht die kürzeste Lösung unter den Sprachen sein wird, könnte dies die kürzeste von den für Menschen lesbaren sein ...

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

Oder, um es etwas klarer auszudrücken

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

Genannt mit zum Beispiel !37.

Glen O
quelle
3

Mathematica, 32 Bytes

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

Dies ist eine unbenannte Funktion, die eine Ganzzahl annimmt und einen Booleschen Wert zurückgibt.

Erläuterung

Es gibt hier eine Menge Syntax und lustige Lesereihenfolge, also ...

   #                               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.
Martin Ender
quelle
Eng geschlagen #+0~Min~NextPrime@-#&~FixedPoint~#==1&(36 Bytes). Gute Verwendung von //.!
Greg Martin
1
@ GregMartin 35, wenn Sie <2am Ende verwenden.
Martin Ender
3

Python3, 102 92 90 89 88 Bytes

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])

Golfvorschläge willkommen! Ich sehe, dass gmpyeine Funktion enthalten ist next_prime, aber ich kann sie noch nicht testen :(

-2 Bytes, danke an @JonathanAllan !

-1 Byte, danke an @Aaron !

Testfälle

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)))

Die Ausgabe umfasst 13 Wahrheitswerte und 13 Falsey-Werte. senthält die wahrheitsgemäßen Fälle und hdie falschen.

Yytsi
quelle
1
if all(x%y for...Arbeiten
Jonathan Allan
1
n<3 else-> n<3elseum die gleiche Länge wie ich zu bekommen;)
Aaron
2

Python mit Sympy, 60 Bytes

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

Meine frühere Methode war 83 Bytes ohne Sympy mit Rekursion, aber ich habe Wahrhaftigkeit / Falschheit als unterscheidbar und konsistent verstanden, aber mir wurde mitgeteilt, dass dies eine falsche Interpretation ist. Ich kann es anscheinend wegen des Schwanzes nicht retten, aber ich lasse es hier, falls jemand weiß, wie es geht:

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
Jonathan Allan
quelle
@ mbomb007 Ich dachte, Spezifikationen sind "wahr oder falsch", wenn dies erforderlich ist, während "wahr oder falsch" unterscheidbar und konsistent bedeutet?
Jonathan Allan
1
Nee. Sie sind so definiert, wie wir uns für die Meta-Site entschieden haben. Jede Frage, die eine "unterscheidbare und konsistente" Ausgabe ermöglicht, muss dies spezifizieren und nicht Wahrhaftigkeit / Falschheit.
mbomb007
OK, ich habe dies gelesen und werde es irgendwann aktualisieren ...
Jonathan Allan
1

Vitsy, 28 26 Bytes

Dies kann definitiv verkürzt werden.

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

Um die Umstellung zu erleichtern, müssen Sie

<                    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);

Probieren Sie es online!

Addison Crump
quelle
1

MATL , 13 Bytes

`tqZq0)-t2>}o

Probieren Sie es online! Oder überprüfen Sie alle Testfälle auf einmal .

Erläuterung

`        % 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
Luis Mendo
quelle
1

CJam , 21 16 Bytes

Vielen Dank an Dennis für das Speichern von 4 Bytes.

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

Probieren Sie es online!

Erläuterung

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
Martin Ender
quelle
ri_{_1|{mp},W=-}*sollte arbeiten.
Dennis
@Dennis Danke, das 1|ist echt schlau. :) (Und ich vergesse immer, dass {...},ein impliziter Bereich ...)
Martin Ender
1

Perl, 42 Bytes

Beinhaltet +1 für -p

Mit Eingabe auf STDIN ausführen

reach1.pl:

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

Verwendet den klassischen regulären Ausdruck "Primality"

Tonne Hospel
quelle
1

.NET Regex, 38 Byte

Nur um zu zeigen, dass es in einem einzigen regulären Ausdruck überprüft werden kann.

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

Die Eingabe wird als unär angenommen.

Erläuterung

Es implementiert einfach die Anforderung an das Wort, entfernt wiederholt die größte Primzahl und prüft, ob der Rest 1 ist.

  • (?>(?<=(.*))..+(?<!^\1\2+(.+.)|$))+: Eine Gruppe ohne Backtracking stellt sicher, dass die größte gefundene Primzahl nicht überschrieben wird, und +wiederholt einfach den Vorgang des Abgleichs der größten Primzahl.

    • (?<=(.*))..+(?<!^\1\2+(.+.)|$): Finde die größte Primzahl, die kleiner ist als die verbleibende Zahl

      • (?<=(.*)): Notieren Sie, wie viel wir abgezogen haben, um einen "Anker" -Punkt für die Behauptung zu erstellen.

      • ..+: Suche nach der größten Zahl ...

      • (?<!^\1\2+(.+.)|$): ... das ist eine Primzahl und kleiner als die verbleibende Zahl.
        • (?<!^\1\2+(.+.)): Die übliche Prime-Test-Routine, bei der im ^\1Vordergrund angeheftet wird, um sicherzustellen, dass die übereinstimmende Menge überprüft wird..+
        • (?!<$): Geben Sie weniger als die verbleibende Anzahl an
n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳
quelle
Der (?<=(.*))Teil ist ziemlich ungeschickt. Ich bin mir nicht sicher, ob es einen besseren Weg gibt. Außerdem bin ich gespannt, ob es in PCRE eine Lösung gibt.
n̴̖̋h̴̖̋a̷̭̿h̷̭̿d̷̰̀ĥ̷̳
0

Perl 6 ,  54 53 52  51 Bytes

{($_,{$_-($_-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}

Erläuterung:

# 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
}

Beispiel:

# 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)
Brad Gilbert b2gills
quelle
0

Unregelmäßig , 63 Bytes

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

Ich habe diese Sprache vor zwei Tagen erstellt, und die Grundvoraussetzung ist, dass es keine eingebauten Schleifen gibt. Die einzigen Merkmale sind Grundrechenarten und Entscheidungsfindung, und die Programmbewertung basiert auf regulären Ausdrücken.

Erläuterung

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

Dieser Teil wandelt die Eingabe in eine unäre um. Sie subtrahiert wiederholt 1 von der Eingabe, bis sie gleich 0 ist, und zwar 1_jedes Mal vor der Eingabe . Dann werden alle _s entfernt. Wenn ich ein breakin meinem Code nicht vergessen hätte, könnte es so geschrieben werden:

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

Der nächste Teil entfernt wiederholt die größte Primzahl von der Eingabe, bis sie gleich 1oder 11ist 11und durch ersetzt wird 0.

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

Ich habe den regulären Ausdruck von verwendet Martin Enders Antwort verwendet .

DanTheMan
quelle
0

Haskell, 79 Bytes

Nicht wirklich kurz, aber sinnvoll :)

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

PowerShell v2 +, 81 Byte

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

Übernimmt die Eingabe $n. Tritt in eine whileSchleife ein, solange sie $nnoch 3oder länger ist . Bei jeder Iteration wird eine Zahl von subtrahiert $n. Die Zahl ist das Ergebnis des Regex-Primalitätstests , der ($n-1)..2über den Operator Where-Object( ?) auf einen Bereich angewendet wurde , und dann das erste [0]der Ergebnisse (da der Bereich abnimmt, wird der größte ausgewählt). Nach Abschluss der Schleife $nwird entweder 1oder 2per Definition dekrementiert $n(in entweder 0oder umgewandelt 1) und das Boolesche-Nicht !davon genommen. Das bleibt in der Pipeline und die Ausgabe ist implizit.

Beispiele

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
AdmBorkBork
quelle
0

Matlab, 51 Bytes

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

Dies ist der JS6-Lösung von ETHProductions SEHR ähnlich, erfordert jedoch , dass sich die Variable im Arbeitsbereich befindet.

ptev
quelle
0

Python 2.7: 88 87 Bytes

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

Danke @TuukkaX für -1 weiteres Byte!

Aaron
quelle
1
Aktualisieren Sie Ihre Beschreibung;) Sie können auch ein Byte speichern, indem Sie n<2anstelle von sagen n==1.
Yytsi
0

Floroid , 45 30 29 Bytes

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

Clojure, 125 Bytes

#(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)))

Huch, das ist ein langer Code. Die wortreichste Sprache schlägt wieder zu!

Ungolfed:

(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))))
Clismique
quelle