Umkehren und Entartung hinzufügen

22

Intro

Das Umkehren und Hinzufügen ist so einfach wie es sich anhört. Nehmen Sie es nund fügen Sie es in umgekehrter Reihenfolge zu den Ziffern hinzu. (zB 234 + 432 = 666).

Wenn Sie diesen Vorgang wiederholt anwenden, treffen einige Zahlen irgendwann auf eine Primzahl und andere erreichen nie eine Primzahl.

Beispiel

Ich habe derzeit

11431 rep.

11431 is not prime
11431 + 13411 = 24842 which is not prime
24842 + 24842 = 49684 which is not prime
49684 + 48694 = 98378 which is not prime
98378 + 87389 = 185767 which is prime!

Diese Zahl trifft eine Primzahl

Im Gegensatz dazu wird ein Vielfaches von 3 niemals eine Primzahl treffen, da alle Vielfachen von 3 eine Ziffernsumme haben, die ein Vielfaches von 3 ist und umgekehrt. Wenn Sie also umkehren und ein Vielfaches von 3 addieren, erhalten Sie immer ein neues Vielfaches von 3 und somit niemals eine Primzahl.

Aufgabe

Nehmen Sie eine positive ganze Zahl nund bestimmen Sie, ob das wiederholte Umkehren und Addieren jemals zu einer Primzahl führen wird. Gib einen wahrheitsgemäßen oder falschen Wert aus. Entweder erreicht Truthy for einen Primwert, und Truthy is not oder umgekehrt sind beide akzeptabel.

Es wird davon ausgegangen, dass Primzahlen in Iterationen von Null eine Primzahl erreichen.

Dies ist also versuchen Sie, Ihren Code so kurz wie möglich zu halten.

Testfälle

Wahr für erreicht eine Primzahl Falsch für erreicht nie eine Primzahl

11 -> True
11431 -> True
13201 -> True
13360 -> True
13450 -> True
1019410 -> True
1019510 -> True
22 -> False
1431 -> False
15621 -> False
14641 -> False

Hinweis

Während ich diese Herausforderung schrieb, entdeckte ich einen coolen Trick, der dieses Problem viel einfacher macht. Es ist nicht unmöglich ohne diesen Trick und es ist auch nicht trivial damit, aber es hilft. Es hat mir sehr viel Spaß gemacht, dies zu entdecken und ich werde es unten in einem Spoiler belassen.

Durch wiederholtes Umkehren und Hinzufügen wird immer ein Vielfaches von 11 in 6 Iterationen oder weniger erreicht. Wenn es keine Primzahl erreicht, bevor es ein Vielfaches von 11 erreicht, wird es niemals eine Primzahl erreichen.

Weizen-Assistent
quelle
Ich finde es eher ein mathematisches Problem als ein Codierungsproblem. Ich denke, bei Code-Problemen sind spezielle Regeln festgelegt, die vom Antwortenden im Code implementiert werden. Ich glaube nicht, dass dies bei dieser Herausforderung der Fall ist.
Arjun
@ DobbyTheFree-Elf Ich denke, der Unterschied zwischen diesem Problem und typischen "Codierungs" -Problemen besteht darin, dass der zu implementierende Algorithmus für letztere häufig offensichtlich ist und nur mit möglichst wenig Code ausgeführt werden muss. Diese Herausforderung zwingt Sie dazu, einen Algorithmus von Grund auf neu zu entwickeln. Beide werfen ihre eigenen einzigartigen Rätsel auf, aber beide sind letztendlich immer noch Probleme beim Programmieren.
Weizen-Assistent
Ich stimme Ihrem Kommentar zu, aber meiner Meinung nach ist es eher eine Aufgabe eines Mathematikers als eines Programmierers, einen solchen Algorithmus für diese Herausforderung zu entwickeln. Ich weiß nicht, was andere denken, aber das denke ich zumindest. Das hat meine Ablehnung.
Arjun
1
@ DobbyTheFree-Elf Ich hasse es, es Ihnen zu brechen, aber effiziente Algorithmen zu finden, um ein Problem in einem entscheidenden Teil eines guten Programmierers zu lösen.
Weizen-Assistent
Dem stimme ich auch zu. Der Algorithmus für diese Herausforderung hat jedoch einen höheren mathematischen Wert. Man muss bewährte mathematische Theoreme finden oder erstellen, um mit jeder möglichen Eingabe eine korrekte Ausgabe zu gewährleisten, was meiner Meinung nach die Mathematiker tun. Gängige Ansätze wie Brute Force usw. funktionieren in diesem Fall nicht.
Arjun

Antworten:

7

Ruby , 84 79 77 74 Bytes

->x{y=1;x+="#{x}".reverse.to_i while(2...x).any?{|z|0==y=x%z}&&x%11>0;y>0}

Probieren Sie es online!

Wenn ich es richtig verstanden habe, können wir aufhören, wenn wir ein Vielfaches von 11 erreichen (danach erhalten wir nur noch ein Vielfaches von 11).

GB
quelle
Es gibt etwas Stärkeres, das wir mit den Informationen im Spoiler beweisen können.
Weizen-Assistent
3

Haskell , 65 Bytes

fnimmt ein Integerund gibt ein zurück Bool. Truebedeutet, es erreicht eine Blütezeit.

f n=gcd(product[2..n-1])n<2||gcd 33n<2&&f(n+read(reverse$show n))

Probieren Sie es online!

Leider bedeutet der kurze, aber ineffiziente Primetest, dass die Testfälle des OP Truenicht 11zu groß werden, um abgeschlossen zu werden. Aber zum Beispiel ist 11432 ein TrueFall, der zu Ende geht.

Sie können auch dieses 3 Bytes längere versuchen, für das TIO alle TrueTestfälle beenden kann :

f n=and[mod n i>0|i<-[2..n-1]]||gcd 33n<2&&f(n+read(reverse$show n))

Probieren Sie es online!

Die Primetests beider Versionen brechen mit 1 ab, aber es kommt trotzdem vor, dass es zu einer Primzahl (2) kommt.

Ansonsten ist mir etwa dasselbe aufgefallen wie GB im Spoiler der Ruby-Einreichung:

Sobald eine Zahl eine gerade Länge erreicht, ist die nächste Iteration durch 11 teilbar. Sobald eine Zahl durch 11 teilbar ist, sind auch alle folgenden Iterationen teilbar.

Ørjan Johansen
quelle
@ WheatWizard Nun, es bedeutet, dass die Anzahl der Iterationen begrenzt ist, mit (sorry, keine Spoiler-Tags in Kommentaren) maximal 6 Schritten zu überprüfen, denke ich (zB 100 ist maximal). Wenn ich es kurz versuche, scheint mir dies jedoch keine kürzere Lösung zu bieten. Meinst du etwas Mächtigeres als das?
Ørjan Johansen
Nein, das war es 6 ist das Maximum
Wheat Wizard
3

Python 2, 123 110 Bytes

13 Bytes gespart dank Ørjan Johansen und Wheat Wizard !

n=input()
while 1:
 if all(n%m for m in range(2,n)):print 1;break
 if n%11==0:print 0;break
 n+=int(`n`[::-1])

Gibt 1 zurück, wenn eine Primzahl erreicht wird, und 0, wenn dies nicht der Fall ist. Probieren Sie es online!

numbermaniac
quelle
2

Python 2 , 78 70 69 Bytes

f=lambda x:all(x%a for a in range(2,x))or x%11and f(x+int(`x`[::-1]))

Probieren Sie es online!

Erläuterung

Dieses Programm beruht auf der Tatsache, dass

Jede Zahl, die für immer verloren hat, erreicht in weniger als 6 Zügen ein Vielfaches von 11

Dieses Programm ist ein rekursives Lambda mit logischen Vergleichsschaltungen. Zuerst wird geprüft, ob n eine Primzahl ist.

all(x%a for a in range(2,x))

Wenn dies wahr ist, geben wir wahr zurück.

Wenn es falsch ist, prüfen wir, ob es ein Vielfaches von 11 ist.

x%11

Wenn false, geben wir false zurück, andernfalls geben wir das Ergebnis fder nächsten Iteration zurück

f(x+int(`x`[::-1]))
Weizen-Assistent
quelle
2

Jelly , 11 Bytes

ṚḌ$+$6СÆPS

Probieren Sie es online!

Erik der Outgolfer
quelle
Für das Interesse eines jeden, der diese Antwort liest, könnte die letzte Sauch eine sein T. RD$+$kann auch sein +RD$$oder RD+<newline>Ç(alle trivialen Änderungen)
HyperNeutrino
@HyperNeutrino Ich habe gewählt, Sweil es weniger Chancen hat, etwas> 1 zu zeigen. Es gibt kein RDgerechtes ṚḌund ich entschied ṚḌ$+$mich dafür, es besser zu organisieren.
Erik der Outgolfer
Ich war zu faul, um die Punkte einzufügen; Ich weiß, warum Sie setzen S; Ich hätte das überdenken sollen T, aber das ist hauptsächlich für das Interesse aller anderen.
HyperNeutrino
1

05AB1E , 14 13 Bytes

BEARBEITEN : 1 Byte gespeichert, da die Eingabe wiederverwendet wird, wenn nicht genügend Elemente auf dem Stapel vorhanden sind

[Dp#D11Ö#R+]p

Probieren Sie es online!

Verwendet den Hinweis in der Frage

Wie es funktioniert

[              # begin infinite loop
               # implicit input
 D             # duplicate input
  p            # push primality of input
   #           # if prime, break
    D          # duplicate input
     11        # push 11
       Ö       # push input % 11 == 0
        #      # if multiple of 11, break
               # implicit push input
          R    # reverse input
           +   # add both numbers
            ]  # end infinite loop
             p # push primality of result; 1 if prime, 0 if multiple of 11
               # implicit print
Neil A.
quelle
0

MATLAB, 88 81 Bytes

function r=f(n);r=0;for i=1:7 r=r+isprime(n);n=n+str2num(fliplr(num2str(n)));end;
Steadybox
quelle
0

JavaScript (ES6), 73 Byte

Rückgabe 0oder true.

f=n=>{for(d=n;n%--d;);return d<2||n%11&&f(+[...n+''].reverse().join``+n)}

Kommentiert

Dies basiert auf der von Wheat Wizard beschriebenen Magic-Spoiler-Formel.

f = n => {              // given n:
  for(d = n; n % --d;); // find the highest divisor d of n
  return                //
    d < 2 ||            // if this divisor is 1, return true (n is prime)
    n % 11 &&           // else: if 11 is a divisor of n, return 0
    f(                  // else: do a recursive call with
      +[...n + '']      // the digits of n
      .reverse().join`` // reversed, joined,
      + n               // coerced to a number and added to n
    )                   //
}                       //

Testfälle

Ich habe die beiden größten Eingaben aus dem Snippet entfernt, da sie einige Sekunden dauern. (Aber sie funktionieren auch.)

Arnauld
quelle
0

Mathematica, 45 Bytes

Or@@PrimeQ@NestList[#+IntegerReverse@#&,#,6]&
Alephalpha
quelle
0

Microsoft SQL Server, 826 786 * Bytes

* Ich habe über die IIF-Funktion erinnert, die in Microsoft SQL Server 2012 eingeführt wurde

set nocount on
use rextester
go
if object_id('dbo.n','IF')is not null drop function dbo.n
go
create function dbo.n(@ bigint,@f bigint)returns table as return
with a as(select 0 c union all select 0),b as(select 0 c from a,a t),c as(select 0 c from b,b t),
d as(select 0 c from c,c t),e as(select 0 c from d,d t),f as(select 0 c from e,e t),
v as(select top(@f-@+1)0 c from f)select row_number()over(order by(select 0))+@-1 n from v
go
with u as(select cast(a as bigint)a from(values(11),(11431),(13201),(13360),(13450),(1019410),(1019510),(22),(1431),
(15621),(14641))u(a)),v as(select a,a c from u union all select a,c+reverse(str(c,38))from v
where 0=any(select c%n from dbo.n(2,c/2))and c%11>0)select a,iif(0=any(select max(c)%n from dbo.n(2,max(c)/2)),0,1)
from v group by a option(maxrecursion 0)

Überprüfen Sie es online

Je übersichtlicher die Formatierung

SET NOCOUNT ON;
USE rextester;
GO
IF OBJECT_ID('dbo.n', 'IF') IS NOT NULL DROP FUNCTION dbo.n;
GO
CREATE FUNCTION dbo.n(@ BIGINT,@f BIGINT)RETURNS TABLE AS RETURN
  WITH
    a AS(SELECT 0 c UNION ALL SELECT 0),
    b AS(SELECT 0 c FROM a,a t),
    c AS(SELECT 0 c FROM b,b t),
    d AS(SELECT 0 c FROM c,c t),
    e AS(SELECT 0 c FROM d,d t),
    f AS(SELECT 0 c FROM e,e t),
    v AS(SELECT TOP(@f-@+1)0 c FROM f)
    SELECT ROW_NUMBER()OVER(ORDER BY(SELECT 0))+@-1 n FROM v;
GO
WITH u AS(
  SELECT CAST(a AS BIGINT) a
  FROM(VALUES (11), (11431), (13201), (13360), (13450), (1019410), (1019510),
              (22), (1431), (15621), (14641)) u(a)
),
v AS(
  SELECT a, a c FROM u
    UNION ALL
  SELECT a, c + reverse(str(c, 38))
  FROM v
  WHERE 0 = ANY(SELECT c % n FROM dbo.n(2, c / 2)) AND c % 11 > 0
)
SELECT a, IIF(0 = ANY(SELECT MAX(c) % n FROM dbo.n(2, MAX(c) / 2)), 0, 1)
FROM v
GROUP BY a
OPTION (MAXRECURSION 0);
Andrei Odegov
quelle
Benötigen Sie die /*true*/und /*false*/Kommentare?
Esolanging Fruit
Nein. Es sind die Kommentare, die verwendet wurden, um die Eingabedaten nach den erwarteten Ergebnissen zu trennen.
Andrei Odegov
Kannst du sie löschen?
Esolanging Fruit
Ja, die Kommentare können natürlich gelöscht werden.
Andrei Odegov
Sie scheinen die Eingaben fest codiert zu haben. Ich bin mir nicht sicher, aber ich denke, ein akzeptables Eingabeformat ist, sie stattdessen aus einer Tabelle auszuwählen
Jo King,
0

Gelee , 9 Bytes

ṚḌ+Ɗ6СẒẸ

Probieren Sie es online!

Wie es funktioniert

ṚḌ+Ɗ6СẒẸ    Monadic main link.
ṚḌ+Ɗ         Monad: Reverse and add to original.
    6С      Repeatedly apply the above 6 times, collecting all iterations
       ẒẸ    Is any of them a prime?
Bubbler
quelle
0

PHP 114 Bytes

<?php function f($n){$n1=strrev((string)$n);$r=$n+(int)$n1;for($i=2;$i<$r;$i++){if($r%$i==0){die('0');}}die('1');}

Mehr lesbare Version:

<?php function f($n)
{
    $n1 = strrev((string)$n);
    $r = $n + (int)$n1;
    for ($i = 2; $i < $r; $i++) {
        if ($r % $i == 0) {
            die('0');
        }
    }
    die('1');
}

f(11431 );

Probieren Sie es online!

Ich habe dieses Ding zum Zählen von Bytes benutzt.

Andrew
quelle
Ah okay, es sollte enden. Ich habe die Frage damals falsch verstanden. Die Frage wurde bearbeitet, um sie für falsche Fälle zu beenden.
Andrew
Jetzt wird immer false zurückgegeben, es sei denn, die erste Umkehrung ist eine Primzahl. Sie überprüfen auch nicht den ersten Fall, in demnist eine Primzahl. Und TIO hat einen Byte-Zähler für Sie ... es hat sogar einen Auto-Formatierer für die Vorlage, die Sie verwenden können
Jo King