Unterschiede von MaxMin Divisor Pairs (DMDP)

18

Reden wir über Teiler ...

Ohne perfekte Quadrate (für einen Moment) können alle positiven ganzen Zahlen als das Produkt von 2 ihrer Teiler ausgedrückt werden . Kurzes Beispiel für 126: Hier sind alle Teiler von126
Bildbeschreibung hier eingeben

Wie Sie sehen, können alle Teiler gekoppelt werden. Wir werden die Divisor-Paare wie folgt bezeichnen :
[1, 126], [2, 63], [3, 42], [6, 21], [7, 18], [9, 14]

Für diese Herausforderung benötigen wir nur das letzte Paar dieser Liste (das mittlere Paar des Bildes):
[9,14]Wir nennen dieses Paar das MaxMin-Divisor-Paar .
Der Unterschied des MaxMin-Divisor-Paares (DMDP) ist der Unterschied der beiden Elemente des Paares, wofür [9,14]=5
Ein weiteres Beispiel ist 544. Die Teiler sind:

[1, 2, 4, 8, 16, 17, 32 , 34, 68, 136, 272, 544]

und DMDP (544) = 15 weil32-17=15

Was ist mit den perfekten Quadraten ? Alle perfekten Quadrate haben DMDP = 0
Nehmen wir zum Beispiel 64Divisoren

{1, 2, 4, 8 , 16, 32, 64}

Wie Sie in diesem Fall sehen können, ist das MaxMin-Divisor-Paar, mit [8,8]dem DMDP=0
wir fast fertig sind.

Die Herausforderung

Gegeben eine ganze Zahl n>0, Ausgabe wie viele ganze Zahlen kleiner als oder gleich 10000 , haben DMDP weniger als n

Testfälle

Eingabe -> Ausgabe

1->100 (those are all the perfect squares)
5->492  
13->1201
369->6175  
777->7264  
2000->8478  
5000->9440  
9000->9888  
10000->10000   
20000->10000

Dies ist kürzeste Antwort in Bytes gewinnt .


quelle
Wäre es nicht sinnvoller, den 10000als zweiten, variablen Eingang zu haben?
Jonathan Allan
1
Ja, ich habe darüber nachgedacht, aber es würde der Herausforderung nichts hinzufügen. Auf diese Weise fällt es meiner Meinung nach jedem leichter, die Herausforderung zu verstehen.
1
Related
Peter Taylor

Antworten:

5

JavaScript (ES7), 60 Byte

f=(n,i=1e4,j=i**.5|0)=>i?i%j?f(n,i,j-1):(i/j-j<n)+f(n,i-1):0

Überschreitet wahrscheinlich Ihr Rekursionslimit, sodass Sie möglicherweise die iterative Version für 70 Bytes bevorzugen:

n=>[...Array(1e4)].map(g=(j=++i**.5|0)=>i%j?g(j-1):k+=i/j-j<n,i=k=0)|k
Neil
quelle
4

Gelee , 13 Bytes

1 Byte danke an Jonathan Allan.

ȷ4RÆDạU$Ṃ€<⁸S

Probieren Sie es online!

Undichte Nonne
quelle
ÆDạ"Ṛ$Ṃspart dir ein byte mehr als ÆDạ:@¥⁸Ṃ(ich hatte ạ"ṚṂ... ȷ4RÆDÇ€<⁸Sfür 15 - zu ähnlich - BEARBEITEN: hmm oder war es, nicht :beteiligt ... was denkst du?)
Jonathan Allan
@JonathanAllan Ich denke , Sie sollten schreiben Sie diese 13-byter
Leaky Nonne
Oh wow. nein du machst es, ich habe dir ein Byte gespart, das weitere 2 speichert!
Jonathan Allan
Könnten Sie eine Erklärung hinzufügen?
Kevin Cruijssen
4

Java 8, 151 111 110 101 Bytes

n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1;)if(x>=i*i&x%i<1){i=x/i-i;break;}return r;}

-10 Bytes dank @Nevay .

Erläuterung:

Probieren Sie es hier aus.

n->{               // Method with integer as parameter and return-type
  int r=0,         //  Result-integer
      x=10000,     //  Index-integer starting at 10,000
      i;           //  Another index-integer for the inner loop
  for(;x-->0;      //  Loop (1) from 10,000 down to 0
      r-=i-n>>-1)  //   If the MaxMin-Divisor Pair's difference is lower than the input,
                   //    add 1 to the result (after every iteration)
    for(i=x,       //   Set `i` to `x`
        i-->1;)    //   Inner loop (2) from `i` downwards to 1
      if(x>=i*i    //    If the current square-root of `x` is smaller than or equal to `i`,
         &x%i<1){  //    and if the current `x` is divisible by `i`:
        i=x/i-i;   //     Calculate the MaxMin-Division difference
        break;}    //     And leave the inner loop (2)
                   //   End of inner loop (2) (implicit / single-line body)
                   //  End of loop (1) (implicit / single-line body)
  return r;        //  Return the result
}                  // End of method
Kevin Cruijssen
quelle
1
Mit können Sie for(i=1,i+=Math.sqrt(x);--i>0;)if(...1 Byte speichern.
Nevay
Sie haben keine Zeit, es selbst zu versuchen. Wäre es jedoch kürzer, wenn die innere Schleife von x ausgeht und eine zusätzliche Variable für das aktuelle Minimum vorhanden wäre?
JollyJoker
1
101 Bytes:n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1;)if(x>=i*i&x%i<1){i=x/i-i;break;}return r;}
Nevay
@Nevay Nochmals vielen Dank, ich muss mich wirklich x>=i*ials Alternative für die Verwendung erinnern Math.sqrt, da dies das zweite Mal ist, dass Sie das in meinem Code gespielt haben.
Kevin Cruijssen
2

R 73 77 Bytes

Danke an @Guiseppe für die 4 Bytes

sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())

Probieren Sie es online!

Habe die Vektorisierungsfunktion zur Berechnung des DMDP verloren und benutze nun eine Funktion, um dies zu ändern. Die Wahrheiten für Elemente, die kleiner als die Eingabe sind, werden für das Ergebnis summiert.

MickyT
quelle
Ah, mir ist nicht aufgefallen, dass DMDP der minimale Unterschied dieser Faktorliste ist! Sehr schön. Ich denke, sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())ist ein bisschen kürzer
Giuseppe
2

Mathematica, 64 Bytes

Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

Probieren Sie es auf Wolfram Sandbox

Verwendung

f = Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

 

f[1]
100
f /@ {1, 5, 13, 369, 777, 2000, 5000, 9000, 10000, 20000}
{100, 492, 1201, 6175, 7264, 8478, 9440, 9888, 10000, 10000}

Erläuterung

Divisors~Array~1*^4

Generieren Sie die Liste der Teiler von 1bis 10000. (Die Teilerlisten werden automatisch sortiert)

Count[ ..., a_/; ... ]

Zählen Sie die Vorkommen von Elementen a, so dass ...

#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]

(input) + (left one of the middle element(s)) > (right one of the middle element(s)) Wenn es nur ein mittleres Element gibt, ist left = right.

JungHwan min
quelle
2

05AB1E , 19 18 17 16 15 12 Bytes

4°ƒNÑÂα{нI‹O

Probieren Sie es online!

Erläuterung

4°ƒ            # for N in [0 ... 10**4] do:
   NÑ          # push divisors of N 
     Â         # bifurcate
      α        # element-wise absolute difference
       {       # sort
        н      # pop the head (smallest difference)
         I‹    # is it smaller than the input?
           O   # sum the stack
Emigna
quelle
1

MATL , 20 Bytes

1e4:"@Z\2Y"dJ2/)G<vs

Der Code läuft in TIO ab. Hier ist ein Beispiel, das mit dem Offline-Compiler ausgeführt wird:

>> matl 1e4:"@Z\2Y"dJ2/)G<vs
> 13
1201
Luis Mendo
quelle
1

R , 91 Bytes

function(n)sum(sapply(1:1e4,function(x,d=(1:x)[x%%1:x<1])diff(d[median(seq(d))+.5*0:1]))<n)

Es wird ein anderer (schlechterer) Ansatz für die Berechnung des DMDP gewählt als für die MickyT-Lösung, indem die Array-Indizierung verwendet und diffberechnet wird. Ach.

Probieren Sie es online!

Giuseppe
quelle
1

Mathematica, 119 115 Bytes

(n=#;Tr[1^Select[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),#<n&]])&

Endlich habe ich das Ding zum Laufen gebracht und ich habe es die letzte halbe Stunde versucht. ._.

Beispiellauf

Keine Beschreibung für dich!

total menschlich
quelle
Casesist 4Bytes kürzer: Tr[1^Cases[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]]&. Siehe diesen Tipp .
Genisis
1
@genisis ist eigentlich Countnoch kürzer als Cases. Count[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+‌​(1+Length@Divisors@#‌​)/2]]&/@Range@10000)‌​,n_/;n<#]&
JungHwan Min
Auch 10^4oder 1*^4ist kürzer als 10000und /@Range@ist äquivalent zu ~Array~.
JungHwan Min
1

Mathematica, 78 Bytes

(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&
J42161217
quelle
Casesist 4Bytes kürzer: Tr[1^Cases[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]]&. Siehe diesen Tipp .
Genisis
1
@ngenisis Countist noch kürzer:Count[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^‌​4}],s_/;s<#]&
JungHwan Min
1

Schale , 19 Bytes

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100

Kein TIO-Link, da Timeout. Diese Version verwendet 100 anstelle von 10000 und ist in wenigen Sekunden fertig.

Erläuterung

Husk hat noch keine Divisoren eingebaut oder unterstützt die wissenschaftliche Notation.

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100  Input is n (accessed with ⁰).
               □100  Square of 100: 10000
              ḣ      Inclusive range from 1.
#                    Count number of elements for which
 ȯ                   this composition of 3 functions gives truthy result:
                       Argument k, say k = 12.
         §f`¦ḣ         Divisors of k:
             ḣ           Range: [1,2,3,..,12]
         §f              Filter by
           `¦            divides k: [1,2,3,4,6,12]
     Sz≠↔              Absolute differences of divisor pairs:
        ↔                Reverse: [12,6,4,3,2,1]
     Sz                  Zip with divisor list
       ≠                 using absolute difference: [11,4,1,1,4,11]
  V<⁰                  Is any of these less than n?
Zgarb
quelle
1

Japt , 25 19 17 Bytes

L²õÈâ ®aX/ZÃd<UÃè

Probier es aus


Erläuterung

Implizite Eingabe einer Ganzzahl U.

L²õ

Generieren Sie ein Array von Ganzzahlen õ( L) im Quadrat von 1 bis 100 ( ).

Èâ          Ã

Übergeben Sie jeweils eine Funktion (wobei Xdas aktuelle Element ist), die ein Array der Teiler ( â) von erzeugt X.

®    Ã

Ordnen Sie über diesem Array von Teilern zu, wo Zsich das aktuelle Element befindet.

aX/Z

Holen Sie sich die absolute Differenz ( a) von Zund Xdividiert durch Z.

d<U

Ist eines der Elemente ( d) im resultierenden Array kleiner als U?

è

Zählen Sie die wahrheitsgemäßen Elemente und geben Sie das Ergebnis implizit aus.

Zottelig
quelle
1

TI-BASIC, 46 Bytes

Beachten Sie, dass TI-BASIC eine Token-Sprache ist. Außerdem ist das E in Zeile 2 ein kleines Kapital E, das durch Drücken von 2ND +, gefunden wird.

Input A
DelVar DFor(B,1,E4
For(C,1,√(B
If not(fPart(B/C
B/C-C<A
End
D+Ans→D
End

Das Ergebnis wird direkt nach der Programmausführung in D und Ans angezeigt. Wenn es angezeigt werden soll, würde das Hinzufügen von zwei weiteren Bytes (Newline und Ans) ausreichen.

Josiah Winslow
quelle
0

Python 2 , 134 Bytes

lambda i:len(filter(lambda n:n<i,[reduce(lambda x,y:y-x,[[x,n/x]for x in range(1,int(n**.5+1))if n%x<1][-1])for n in range(1,10001)]))

Probieren Sie es online!

Eugh ... muss es viel besser machen.

total menschlich
quelle
125 Bytes (-9 Bytes) unter Verwendung Ihres aktuellen Ansatzes, aber Ersetzen len(filter(lambda n:n<i,...))durchsum(n<i for n in ....)
Mr. Xcoder
114 Bytes basierend auf Mr.Xcoders Kommentar.
Ovs
113 Bytes basierend auf dem Kommentar von ovs.
Mr. Xcoder
0

Python 2 , 83 Bytes

Etwas langsam, benötigt 5 Sekunden pro Testfall

lambda x:sum(x>min(abs(y/t-t)for t in range(1,y+1)if y%t<1)for y in range(1,10001))

Probieren Sie es online!

Halvard Hummel
quelle
0

PHP, 94 + 1 Bytes

for(;$n++<1e4;$c+=$d<$argn)if(($i=$n**.5)>~~$i){while($n%++$i);for($d=1;$n%--$i;)$d++;}echo$c;

Laufen Sie als Pipe mit -nRoder probieren Sie es online aus .

Titus
quelle
0

VB.NET (.NET 4.5) 116 115 Bytes

Function A(n)
For i=1To 10^4
Dim s As Byte=Math.Sqrt(i)
While i Mod s>0
s-=1
End While
A-=i/s-s<n
Next
End Function

Erläuterung:

Eine Funktion, die nals Parameter verwendet und das Ergebnis zurückgibt.

Beginnt bei der Quadratwurzel und sucht nach der nächsten Ganzzahl, die sich gleichmäßig teilt (wird die kleinere der MaxMin Divisor Pair). Dann wird der größere Wert aus dem Paar ( i/s) ermittelt, der Unterschied ermittelt und mit der Eingabe verglichen.


Verwendete Golfstrategien:

  • Dim ist teuer, also je weniger Variablen ich deklariere, desto besser.
  • Ich beginne mit der Suche nach der Quadratwurzel, möchte aber nur Ganzzahlen betrachten. Durch die Deklaration sals integraler Typ wird er für mich zu Boden geworfen.
  • VB verwendet ^als Exponent. Während 10000also 5 Zeichen sind, sind 10^4es nur 4.
  • VB erstellt eine automatische Variable mit demselben Namen und Typ wie die Funktionsdefinition (in meinem Fall A). Wenn am Ende der Funktion keine vorhanden ist return, wird stattdessen der Wert der Funktionsvariablen zurückgegeben. Ich spare also Zeichen, indem ich keine separate Variable deklariere und keine return-Anweisung verwende.
  • VB hat sehr fehlerverzeihendes Schreiben / Casting. iwird angenommen, Integerweil ich ein Integer-Literal zugewiesen habe. Awird angenommen, Objectaber sobald ich eine ganze Zahl hinzufüge, verhält es sich wie ein Integer.
  • Anstatt zu ifüberprüfen, ob der Unterschied zufriedenstellend ist, fügen Sie ihn direkt zum Ergebnis hinzu, indem Sie den Booleschen Wert in eine Ganzzahl umwandeln. VB verwendet jedoch -1für True, also subtrahieren Sie, um das richtige Vorzeichen zu erhalten.
  • Technisch wollen wir Modnicht sein 0. Die Verwendung des Moduls einer negativen Zahl in VB.NET führt zu einem negativen Ergebnis. Aber, alles ist positiv , so ich ein Byte durch Drehen speichern kann <>in >.
  • Die größte zu überprüfende Zahl ist 10000. Die Quadratwurzel davon ist 100. Ich brauche also nur eine Byte, um das zu speichern, und speichere Bytes in der Deklaration, indem ich einen Typ mit kürzerem Namen verwende.

Probieren Sie es online!

Brian J
quelle