Bin ich eine 'Redivosite'-Nummer?

26

Redivosite ist ein Wort, das nur zum Zweck dieser Herausforderung erfunden wurde. Es ist eine Mischung aus Reduktion, Division und Composite.

Definition

Gegeben eine ganze Zahl N> 6 :

  • Wenn N eine Primzahl ist, ist N keine Redivosite-Zahl.
  • Wenn N zusammengesetzt ist:
    • Berechne wiederholt N '= N / d + d + 1, bis N' eine Primzahl ist, wobei d der kleinste Teiler von N größer als 1 ist
    • N ist genau dann eine Redivosite-Zahl, wenn der Endwert von N ' ein Teiler von N ist

Nachfolgend die 100 ersten Redivosite Numbers (kein OEIS-Eintrag zum Zeitpunkt der Veröffentlichung):

14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835

Beispiele

  • N = 13 : 13 ist Primzahl, daher ist 13 keine Redivosite-Zahl
  • N = 32 : 32/2 + 3 = 19; 19 ist kein Divisor oder 32, daher ist 32 keine Redivosite-Zahl
  • N = 260 : 260/2 + 3 = 133, 133/7 + 8 = 27, 27/3 + 4 = 13; 13 ist ein Divisor oder 260, also 260 ist eine Redivosite-Zahl

Deine Aufgabe

  • Wenn Sie eine Ganzzahl N angeben, geben Sie einen Wahrheitswert zurück, wenn es sich um eine Redivosite Number handelt, oder einen anderen falschen Wert. (Sie können auch zwei unterschiedliche Werte ausgeben, sofern diese konsistent sind.)
  • Die Eingabe ist garantiert größer als 6 .
  • Das ist , also gewinnt die kürzeste Antwort in Bytes!
Arnauld
quelle
13
Ich wünschte wirklich, all diese "Zahlenfolgen" -Herausforderungen, die nur Folgen von Zahlen mit einer bestimmten Eigenschaft sind, würden nur als Entscheidungsprobleme gestellt. Ich bezweifle sehr, dass es eine Möglichkeit gibt, diese direkt zu generieren. Die einzig mögliche Lösung besteht darin, das Entscheidungsproblem zu lösen und es dann in eine Schleife zu packen, die das N-te oder das erste N oder alle ganzen Zahlen findet, die diese Eigenschaft erfüllen.
Martin Ender
3
Ich mag Sequenzherausforderungen , die im Allgemeinen keine Entscheidungsprobleme sind , aber für diese denke ich, dass ein Entscheidungsproblem besser passt. Ich sehe keine Beziehung zwischen den Begriffen, so dass Sie das n- te oder das erste n auf clevere Weise drucken . Erlauben Sie also vielleicht, n als Eingabe zu nehmen und zu prüfen, ob es erneut geteilt wird ?
Mr. Xcoder
1
@MartinEnder & Mr.Xcoder Das war meine ursprüngliche Absicht (daher der Originaltitel, auf den ich gerade zurückgesetzt habe) und ich änderte meine Meinung. Ich denke, dies sollte keine WIP-Lösung ruinieren (aus den von Ihnen genannten Gründen), also habe ich sie bearbeitet.
Arnauld
5
@ Mr.Xcoder Ja, das habe ich gemeint. Es macht mir nichts aus, wenn Sequenzherausforderungen tatsächlich als Sequenz sinnvoll sind (entweder weil Sie a(n)direkt rechnen können oder weil Sie einen Term aus vorherigen berechnen können). Danke, Arnauld, dass du die Herausforderung geändert hast. :)
Martin Ender

Antworten:

9

Haskell, 91 85 83 80 75 74 Bytes

n#m=([n#(div m d+d+1)|d<-[2..m-1],mod m d<1]++[mod n m<1&&m<n])!!0
f x=x#x

Probieren Sie es online!

f x=x#x                           -- call # with x for both parameters
n#m               
         |d<-[2..m-1],mod m d<1   -- for all divisors d of m
    [n#(div m d+d+1)           ]  -- make a list of recursive calls to #,
                                  -- but with m set to m/d+d+1
   ++ [mod n m<1&&m<n]            -- append the Redivosite-ness of n (m divides n,
                                  -- but is not equal to n)
                           !!0    -- pick the last element of the list
                                  -- -> if there's no d, i.e. m is prime, the
                                  --    Redivosite value is picked, else the
                                  --    result of the call to # with the smallest d

Edit: -2 Bytes dank @BMO, -3 Bytes dank @ H.PWiz und -5 -6 Bytes dank @ Ørjan Johansen

nimi
quelle
2
75 Bytes
Ørjan Johansen
Eigentlich machen das 74
Ørjan Johansen
@ ØrjanJohansen: Nochmals vielen Dank.
Nimi
6

Schale , 14 Bytes

?¬Ṡ¦ΩṗoΓ~+→Πpṗ

Probieren Sie es online!

-3 danke an H.PWiz .

Erik der Outgolfer
quelle
14 Bytes mit einer saubereren Funktion im InnerenΩ
H.PWiz
@ H.PWiz kann einfach nicht verstehen Γ...
Erik der Outgolfer
Hier Γeine Liste gegeben [a, b, c ...] gelten ~+→Πzu aund [b,c...]. ~+→Πfügt a+1zu product[b,c...]. aist der kleinste Teiler, product[b,c...]istN/d
H.PWiz
@ H.PWiz Und ich habe darüber nachgedacht, Primfaktoren zu verwenden ...
Erik the Outgolfer
6

C (GCC) , 94 89 Bytes

m,n;o(k){for(m=1;m++<k;)if(k%m<1)return m;}
F(N){for(n=N;m=o(n),m-n;n=n/m-~m);N=m<N>N%n;}

Probieren Sie es online!

Erläuterung

m,n;                  // two global integers
o(k){                 // determine k's smallest divisor
 for(m=1;m++<k;)      // loop through integers 2 to n (inclusive)
  if(k%m<1)return m;} // return found divisor
F(N){                 // determine N's redivosity
 for(n=N;             // save N's initial value
  m=o(n),             // calculate n's smallest divisor (no name clash regarding m)
  m-n;                // loop while o(n)!=n, meaning n is not prime
                      //  (if N was prime, the loop will never be entered)
  n=n/m-~m);          // redivosite procedure, empty loop body
 N=m<N>N%n;}          // m<N evaluates to 0 or 1 depending on N being prime,
                      //  N%n==0 determines whether or not N is divisible by n,
                      //  meaning N could be redivosite => m<N&&N%n==0
                      //  <=> m<N&&N%n<1 <=> m<N&&1>N%n <=> (m<N)>N%n <=> m<N>N%n
Jonathan Frech
quelle
4

Jelly , 14 Bytes

ÆḌḊ
Ç.ịS‘µÇ¿eÇ

Probieren Sie es online!

Wie es funktioniert

ÆḌḊ         Helper link. Argument: k

ÆḌ          Yield k's proper (including 1, but not k) divisors.
  Ḋ         Dequeue; remove the first element (1).


Ç.ịS‘µÇ¿eÇ  Main link. Argument: n

     µ      Combine the links to the left into a chain.
      Ç¿    While the helper link, called with argument n, returns a truthy result,
            i.e., while n is composite, call the chain to the left and update n.
Ç             Call the helper link.
 .ị           At-index 0.5; return the elements at indices 0 (last) and 1 (first).
              This yields [n/d, d].
   S          Take the sum.
    ‘         Increment.
        Ç   Call the helper link on the original value of n.
       e    Test if the result of the while loop belongs to the proper divisors.
Dennis
quelle
4

Python 2 , 97 91 Bytes

r=0;e=d=i=input()
while r-e:e=i;r=[j for j in range(2,i+1)if i%j<1][0];i=i/r-~r
d%e<1<d/e<q

Probieren Sie es online!

Ausgänge über Exit-Code.

Ungolfed:

r = 0                             # r is the lowest divisor of the current number,
                                  # initialized to 0 for the while loop condition.
e = d = i = input()               # d remains unchanged, e is the current number
                                  # and i is the next number.
while r != e:                     # If the number is equal to its lowest divisor,
                                  # it is prime and we need to end the loop.
    e = i                         # current number := next number
    r = [j for j in range(2, i+1) # List all divisors of the number in the range [2; number + 1)
         if i%j < 1][0]           # and take the first (lowest) one.
    i = i/r+r+1                   # Calculate the next number.
                                  # We now arrived at a prime number.
print d%e == 0 and d != e         # Print True if our current number divides the input
                                  # and is distinct from the input.
                                  # If our current number is equal to the input,
                                  # the input is prime.

Probieren Sie es online!

ovs
quelle
3

05AB1E , 17 16 Bytes

[Dp#Òć©sP+>]Ö®p*

Probieren Sie es online!

Erläuterung

[                  # start loop
 Dp#               # break if current value is prime
    Ò              # get prime factors of current value
     ć©            # extract the smallest (d) and store a copy in register
       sP          # take the product of the rest of the factors
         +>        # add the smallest (d) and increment
           ]       # end loop
            Ö      # check if the input is divisible by the resulting prime
             ®p    # check if the last (d) is prime (true for all composite input)
               *   # multiply
Emigna
quelle
2

Pyth , 20 Bytes

<P_QiI.WtPHh+/ZKhPZK

Probieren Sie es hier aus!

Wie es funktioniert

iI.WtPHh + / ZKhPZK || Volles Programm.

  .W || Funktionell während. Es hat zwei Funktionen als Argumente, A und B.
                 || Während A (Wert) wahr ist, verwandeln Sie den Wert in B (Wert). Das
                 || Startwert ist die Eingabe.
    tPH || Erste Funktion, A. Nimmt ein einziges Argument, H.
     PH || .. Die Primfaktoren Faktoren von H.
    t || Schwanz (erstes Element entfernen). Während wahr (H ist zusammengesetzt):
       h + / ZKhPZK || Die zweite Funktion, B. Nimmt ein einziges Argument, Z:
         / Z || .. Teilen Sie Z durch:
           KhP || .. Sein niedrigster Primfaktor, und weisen Sie das K.   
       h || .. Zuwachs.
        + K || Und addiere K.
iI || Prüfen Sie, ob das Ergebnis (letzter Wert) die Eingabe teilt.

Und die ersten 4 Bytes ( <P_Q) prüfen nur, ob der Eingang nicht prim ist.

Mit Hilfe von Emigna konnte ich 3 Bytes einsparen.

Mr. Xcoder
quelle
Können Sie so etwas head(P)anstelle des fiITZ2Teils verwenden, da der kleinste Teiler, der größer als 1 ist, immer eine Primzahl ist?
Emigna
@Emigna Ninja'd, behoben und danke!
Mr. Xcoder
2

Python 3 , 149 Bytes

def f(N):
	n=N;s=[0]*-~N
	for p in range(2,N):
		if s[p]<1:
			for q in range(p*p,N+1,p):s[q]=s[q]or p
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Probieren Sie es online!

Mit einem Sieb Ansatz. Sollte O(N log log N)auch bei großen schnell sein ( = zeitliche Komplexität des Siebs des Eratosthenes) N(speichert aber O(N)ganze Zahlen im Speicher)

Hinweis:

  • Es kann nachgewiesen werden , dass alle Zwischenwerte von nnicht übersteigen N, und N > 7 pkann in range(2,N)dem statt range(2,N+1)zum Sieben.
  • /funktioniert nicht, //muss wegen Listenindex verwendet werden.
  • Das Speichern rangein eine andere Variable hilft leider nicht.

Erläuterung:

  • -~N== N+1.
  • Zuerst wird das Array smit N+1Nullen initialisiert (Python ist 0-indiziert, also sind die Indizes 0..N)
  • Nach der Initialisierung s[n]wird erwartet, dass 0if neine Primzahl ist, und pfür pdie minimale Primzahl, die nif teilt, nein Composite. s[0]und s[1]Werte sind nicht wichtig.
  • Für jeden pin Reichweite [2 .. N-1]:

    • Wenn s[p] < 1(das heißt s[p] == 0), dann pist es eine Primzahl, und für jede qist ein Vielfaches von pund s[q] == 0, zuzuweisen s[q] = p.
  • Die letzten beiden Zeilen sind unkompliziert, mit der Ausnahme, dass n//s[n]-~s[n]== (n // s[n]) + s[n] + 1.


Python 3 , 118 Bytes

def f(N):
	n=N;s=[0]*-~N
	for p in range(N,1,-1):s[2*p::p]=(N-p)//p*[p]
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Probieren Sie es online!

Auf Kosten einer etwas schlechteren Leistung. (Dieser läuft in O(N log N)zeitlicher Komplexität, unter der Annahme einer sinnvollen Implementierung von Python-Slices)


Das entsprechende vollständige Programm ist 117 Bytes .

user202729
quelle
Sie können n//s[n]-~s[n]statt n//s[n]+s[n]+1149 Bytes verwenden.
Mr. Xcoder
@ Mr.Xcoder Danke!
user202729
Auch ich denke or pkann sein|p
Mr. Xcoder
@ Mr.Xcoder Nein, or pführt logisch oder durch, während |pbitweise oder. Das heißt, a or bist b if a == 0 else a.
user202729
Sie können das äußere ändern for, um stattdessen ein anderes Slice zu verwendenfor . Das rangeist umgekehrt, so dass niedrigere Indizes die größeren überschreiben, und wenn 2*pSie das Slice bei starten , wird s[0]oder nicht ersetzt s[p].
Rod
1

Haskell , 110 Bytes

f n|mod(product[1..n-1]^2)n>0=1<0|1>0=n`mod`u n<1
u n|d<-[i|i<-[2..],n`mod`i<1]!!0=last$n:[u$n`div`d+d+1|d/=n]

Probieren Sie es online!

Nicht sehr glücklich ...

total menschlich
quelle
1

Oktave , 92 Bytes

function r=f(n)k=n;while~isprime(k)l=2:k;d=l(~mod(k,l))(1);k=k/d+d+1;end;r=~mod(n,k)&k<n;end

Probieren Sie es online!

Steadybox
quelle
1

Japt, 25 24 Bytes

Ich fürchte, ich bin vielleicht in die falsche Richtung gegangen, aber mir ist die Zeit ausgegangen, einen anderen Ansatz zu wählen.

Ausgaben 0für false oder 1für true.

j ?V©vU :ßU/(U=k g)+°UNg

Versuch es

Zottelig
quelle
0

Perl 5 , 291 + 1 (-a) = 292 Bytes

Darn Perl, weil er keinen nativen Prim Checker hat.

use POSIX;&r($_,$_);
sub p{$n=shift;if($n<=1){return;}if($n==2||$n==3){return 1;}if($n%2==0||$n%3==0){return;}for(5..ceil($n/2)){if($n%$_==0){return;}}return 1;}
sub r{$n=shift;$o=shift;if(&p($n)){print $o%$n==0&&$n!=$o?1:0;last;}for(2..ceil($n/2)){if($n%$_==0){&r(($n/$_)+$_+1, $o);last;}}}

Ungolfed version,

use POSIX;
&r($_,$_);
sub p{
    my $n=shift;
    if($n<=1){
        return;
    }
    if($n==2||$n==3){
        return 1;
    }
    if($n%2==0||$n%3==0){
        return;
    }
    for(5..ceil($n/2)){
        if($n%$_==0){
            return;
        }
    }
    return 1;
}
sub r{
    my $n=shift;
    my $o=shift;
    if(&p($n)){
        print $o%$n==0&&$n!=$o ? 1 : 0;
        last;
    }
    for(2..ceil($n/2)){
        if($n%$_==0){
            &r(($n/$_)+$_+1, $o);
            last;
        }
    }
}

Probieren Sie es online!

Geoffrey H.
quelle
0

Wolfram Language (Mathematica) , 64 Byte

Einfache Implementierung durch rekursives Ersetzen von Mustern

(Ersetzen von "\ [Divides]" durch das Symbol "∣" spart 7 Bytes)

(g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#&

Probieren Sie es online!

Kelly Lowder
quelle
0

Sauber , 128 117 114 Bytes

import StdEnv
@n#v=hd[p\\p<-[2..]|and[gcd p i<2\\i<-[2..p-1]]&&n rem p<1]
|v<n= @(n/v+v+1)=n
?n= @n<n&&n rem(@n)<1

Probieren Sie es online!

Οurous
quelle
0

J , 35 Bytes

(~:*0=|~)(1+d+]%d=.0{q:)^:(0&p:)^:_

Probieren Sie es online!

Der minimale Divisor, der der erste Hauptfaktor ist, wurde aus der @ Dennis's Jelly-Lösung gestohlen (zuvor habe ich verwendet) <./@q: ) .

Es sollte einen besseren Weg geben, um die Iteration durchzuführen, aber ich kann ihn scheinbar nicht finden. Ich habe überlegt, nicht den Primalitätstest ( ^:(0&p:)) zu machen und stattdessen den Negativtest zu verwenden, aber es scheint, als würde das etwas länger dauern, da Sie einen benötigen_2{ einige Änderungen die möglicherweise keine Nettoreduktion ergeben.

Ich habe wirklich das Gefühl, dass es einen Weg geben muss, um zu vermeiden, dass Parens auch um die Primalitätsprüfung herum stattfinden.

Erklärung (erweitert)

(~: * 0 = |~)(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Input: N
             (1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Find the final N'
                                       ^:        ^:_  Do while
                                           0&p:       N is not prime
                                   q:                 Get prime factors (in order)
                               0 {                    Take first (smallest divisor)
                          d =.                        Assign this value to d
             1 + d + ] %  d                           Compute (N/d) + 1 + d
(~: * 0 = |~)                                        Is it redivosite?
      0 = |~                                          N = 0 (mod N'), i.e. N'|N
    *                                                 And
 ~:                                                   N =/= N', i.e. N is not prime
cole
quelle
0

APL NARS, 43 Zeichen, 85 Byte

{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}

(in der Hoffnung, dass es für alle Zahlen> 6 konvergiert) Test:

h←{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}
v←⍳100     
v,¨h¨v
   1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0  10 0  11 0
   12 0  13 0  14 1  15 0  16 0  17 0  18 0  19 0  20 0  
   21 0  22 0  23 0  24 0  25 0  26 0  27 0  28 0  29 0  
   30 0  31 0  32 0  33 0  34 0  35 0  36 0  37 0  38 0  
   39 0  40 0  41 0  42 1  43 0  44 1  45 0  46 0  47 0  
   48 0  49 1  50 0  51 0  52 0  53 0  54 0  55 0  56 0  
   57 0  58 0  59 0  60 0  61 0  62 0  63 0  64 0  65 0  
   66 1  67 0  68 0  69 0  70 1  71 0  72 0  73 0  74 0  
   75 0  76 0  77 0  78 0  79 0  80 0  81 0  82 0  83 0  
   84 0  85 0  86 0  87 0  88 0  89 0  90 0  91 0  92 0  
   93 0  94 0  95 0  96 0  97 0  98 0  99 0  100 0  

Die Idee mit 2 anonymen Funktionen komme ich zu einer anderen Apl-Lösung.

 {(⍵≤60)∨π⍵:0⋄ -- if arg ⍵ is prime or <=6 return 0
  ⍵{1=⍴t←π⍵:0=⍵|⍺⋄ -- if list of factors ⍵ has length 1 (it is prime)
                    -- then return ⍺mod⍵==0
  ⍺∇1+↑t+⍵÷↑t}⍵}   -- else recall this function with args ⍺ and 1+↑t+⍵÷↑t
RosLuP
quelle
0

Pyt , 44 Bytes

←⁻0`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹ṗ⇹3Ș⊽

Eine Erklärung finden Sie im folgenden Code. Die einzigen Unterschiede sind (1), dass N vor dem Inkrementieren der Schleife dekrementiert wird, und (2) dass NOR anstelle von OR verwendet wird.

Probieren Sie es online!



Ich habe das gemacht, bevor ich die Frage erneut gelesen habe und festgestellt habe, dass es nur ein Richtig / Falsch sein soll.

Pyt, 52 Bytes

60`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹Đṗ⇹3Ș∨ł⇹Đƥ⇹ŕ1ł

Gibt eine unendliche Liste von Redivosite-Zahlen aus.

Erläuterung:

6                                                            Push 6
 0                                                           Push unused character
  `                   ł                     ł      ł         Return point for all three loops
   ŕ                                                         Remove top of stack
    ⁺                                                        Increment top of stack (n)
     ĐĐ                                                      Triplicate top of stack (n)
       ϼ↓                                                    Get smallest prime factor of n (returns 1 if n is prime) 
         Đ                                                   Duplicate top of stack
          3Ș⇹                                                Manipulate stack so that the top is (in descending order): [d,(N,N'),d]
             ÷+⁺                                             Calculates N'=(N,N')/d+d+1
                Đṗ¬                                          Is N' not prime?
                   ⇹⁻⇹                                       Decrement N' (so the increment at the beginning doesn't change the value), and keep the boolean on top - end of innermost loop (it loops if top of stack is true)
                       ŕ                                     Remove top of stack
                        á                                    Convert stack to array
                         Đ                                   Duplicate array
                          0⦋Đ                                Get the first element (N)
                             ↔ĐŁ⁻⦋                           Get the last element ((final N')-1)
                                  ⁺                          Increment to get (final N')
                                   |¬                        Does N' not divide N?
                                     ⇹Đṗ                     Is N prime?
                                        ⇹3Ș∨                 Is N prime or does N' not divide N? - end of second loop (loops if top of stack is true)
                                             ⇹Đƥ⇹ŕ           Print N, and reduce stack to [N]
                                                  1          Push garbage (pushes 1 so that the outermost loop does not terminate)


Probieren Sie es online!

mudkip201
quelle