Erreichbare Nummern

14

Definitionen

  • Euler-Phi-Funktion (AKA- Totientenfunktion ): Eine Funktion, die eine positive Zahl aufnimmt und die Anzahl positiver Zahlen zurückgibt, die kleiner sind als die angegebene Zahl, die mit der angegebenen Zahl gleichrangig sind. Es wird bezeichnet als φ(n).

  • Erreichbar Nummer : wenn es eine positive ganze Zahl vorhanden , xso dass φ(x) == n, dann nist erreichbar .

Aufgabe

Schreiben Sie eine Funktion / ein Programm, um festzustellen, ob eine bestimmte positive Ganzzahl erreichbar ist.

Eingang

Eine positive Zahl in jedem vernünftigen Format. Man kann davon ausgehen, dass die Anzahl innerhalb der Fähigkeiten der Sprache liegt. Unäre Eingabe wird akzeptiert.

Ausgabe

Zwei konsistente Werte, einer für erreichbare und der andere für nicht erreichbare Nummern. Die beiden Werte können beliebig sein, solange sie konsistent sind.

Testfälle

Die erreichbaren Nummern 100sind:

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96

( A002202 bei OEIS)

Regeln

Es gelten Standardlücken .

Gewinnkriterium

Das ist . Einreichung mit der niedrigsten Byteanzahl gewinnt.

Verweise

Undichte Nonne
quelle
auch relevant: oeis.org/A264739
Destructible Lemon
1
Ich biete eine Prämie für eine einzeilige Retina-Antwort an, wobei die eine Zeile eine einfache Regex ist (keine Backticks).
Undichte Nonne
@LeakyNun Ich bin etwas verwirrt, soweit ich das verstehe phi(n) = count { m : 1 <= m <= n AND (m,n) are coprime }.. ist das wahr?
Khaled.K
@ Khaled.K ja, das stimmt.
Undichte Nonne

Antworten:

6

Gelee , 7 6 Bytes

²RÆṪe@

Nicht gerade schnell. Gibt 1 oder 0 zurück .

Probieren Sie es online!

Wie es funktioniert

²RÆṪe@  Main link. Argument: n

²       Square; yield n².
 R      Range; yield [1, ..., n²].
  ÆṪ    Compute the totient of each integer in the range.
    e@  Exists swap; test if n occurs in the generated array.
Dennis
quelle
Wie funktioniert es?
Undichte Nonne
1
Rohe Gewalt. Es gibt eine Untergrenze für die Totientenfunktion, daher ist es ausreichend, einen ausreichend großen Bereich zu nehmen, den Totienten abzubilden und auf Vorkommen der Eingabe zu prüfen.
Dennis
Können Sie beweisen, dass die Quadratwurzel das Minimum ist?
Undichte Nonne
Die Quadratwurzel ist eigentlich keine Untergrenze, sondern die durch sqrt (2) geteilte Quadratwurzel. Ich bin mir sicher, dass eine Verdoppelung nicht erforderlich ist, aber ein Beweis muss warten, bis ich etwas geschlafen habe. Im Moment zu müde.
Dennis
4
@LeakyNun Tatsächlich beweist Lemma 3 dieser Arbeit, dass die Quadratwurzel eine Untergrenze ist, es sei denn, n = 2k mit ungeradem k . Da k und 2k den gleichen Totienten haben, ist keine Verdopplung erforderlich.
Dennis
6

Mathematica, 28 Bytes

EulerPhi@Range[#^2]~FreeQ~#&

Wie Dennis 'Jelly-Antwort berechnen wir die φ-Werte aller Zahlen bis zum Quadrat der Eingabe und prüfen, ob die Eingabe darin enthalten ist. Gibt zurück, Falseob die Eingabe erreichbar ist und Truenicht. Ja, das ist verwirrend. Aber FreeQist ein Byte kürzer als MatchQ, und hey, die Spezifikation sagte zwei konsistente Werte> :)

Greg Martin
quelle
2

JavaScript (ES6), 90 82 Bytes

Rückgabe 0oder true.

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

Dies basiert auf der Annahme, dass x ≤ 2n ist , wenn x existiert . Wenn falsch erwiesen, soll dies verwenden aktualisiert werden statt (gleicher Größe, viel langsamer).x=n*nx=n*2

Ein Kantenfall ist n = 128 , für den comp (255) berechnet werden muss .

Demo

Arnauld
quelle
Günstig sind die Fermat Primzahlen alle aufeinanderfolgenden, DIE EINEN sequentiellen Flanken Fällen n=2, n=8, n=128, n=32768und n=2147483648.
Neil
1

Axiom, 56 Bytes

f(x:PI):Boolean==member?(x,[eulerPhi(i)for i in 1..2*x])

Ich weiß nicht, ob es richtig ist ... Testcode und Ergebnisse

(35) -> [i  for i in 1..100|f(i)]
   (35)
   [1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46,
    48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100]

Der Bereich 1 .. (2 * x) wäre in Ordnung, bis Eingabe x = 500 ...

RosLuP
quelle
1

05AB1E , 5 Bytes

nLÕså

Erläuterung:

n       Square [implicit] input
 L      Range [1 .. a]
  Õ     Euler totient
   s    Put first input at the top of the stack
    å   Is it in the list?

Probieren Sie es online!

Okx
quelle
0

05AB1E , 13 12 Bytes

BEARBEITEN : Ein Byte wurde gespeichert, da die Eingabe wiederverwendet wird, wenn der Stapel nicht genügend Elemente enthält.

Gibt 1 aus, wenn erreichbar, 0, wenn nicht.

Setzt voraus, dass x ≤ 2n ist, falls vorhanden.

xGNÕQi1,q}}0

Probieren Sie es online!

Wie es funktioniert

              # implicit input    
x            # push input, 2 * input
 G           # for N in 1..2*input
             # implicit push input
  N          # push N
   Õ         # push totient of N
    Q        # check if both are equal
     i.      # if equal
      1,     # print 1
        q    # quit program
         }   # end if
          }  # end for
           0 # push 0 if condition never reached
             # implicit print
Neil A.
quelle
0

C, 123 Bytes

g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

Versuchen Sie es online

#include <stdio.h>

// gcd function
g(a,b){return!a?b:g(b%a,a);}

// Euler phi(x) function
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}

// check if m is reachable, phi(x) for x in (m , m^2]
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

main()
{
    // print all reachable number below 50
    for(int x=1; x<50; x++)
    {
        s(x);

        if(t)
        {
            printf(" %d ~ phi(%d) \n", x, k);
        }
    }
}
Khaled.K
quelle
102 Bytes
Ceilingcat