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
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 64
Divisoren
{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 Code-Golf. Die kürzeste Antwort in Bytes gewinnt .
10000
als zweiten, variablen Eingang zu haben?Antworten:
JavaScript (ES7), 60 Byte
Überschreitet wahrscheinlich Ihr Rekursionslimit, sodass Sie möglicherweise die iterative Version für 70 Bytes bevorzugen:
quelle
Gelee , 13 Bytes
1 Byte danke an Jonathan Allan.
Probieren Sie es online!
quelle
ÆDạ"Ṛ$Ṃ
spart dir ein byte mehr alsÆDạ:@¥⁸Ṃ
(ich hatteạ"ṚṂ
...ȷ4RÆDÇ€<⁸S
für 15 - zu ähnlich - BEARBEITEN: hmm oder war es, nicht:
beteiligt ... was denkst du?)Java 8,
151111110101 Bytes-10 Bytes dank @Nevay .
Erläuterung:
Probieren Sie es hier aus.
quelle
for(i=1,i+=Math.sqrt(x);--i>0;)if(...
1 Byte speichern.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;}
x>=i*i
als Alternative für die Verwendung erinnernMath.sqrt
, da dies das zweite Mal ist, dass Sie das in meinem Code gespielt haben.R 73
77BytesDanke an @Guiseppe für die 4 Bytes
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.
quelle
sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())
ist ein bisschen kürzerMathematica, 64 Bytes
Probieren Sie es auf Wolfram Sandbox
Verwendung
Erläuterung
Generieren Sie die Liste der Teiler von
1
bis10000
. (Die Teilerlisten werden automatisch sortiert)Zählen Sie die Vorkommen von Elementen
a
, so dass ...(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.quelle
05AB1E ,
191817161512 BytesProbieren Sie es online!
Erläuterung
quelle
MATL , 20 Bytes
Der Code läuft in TIO ab. Hier ist ein Beispiel, das mit dem Offline-Compiler ausgeführt wird:
quelle
R , 91 Bytes
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
diff
berechnet wird. Ach.Probieren Sie es online!
quelle
Mathematica,
119115 BytesEndlich habe ich das Ding zum Laufen gebracht und ich habe es die letzte halbe Stunde versucht. ._.
Beispiellauf
quelle
Cases
ist4
Bytes kürzer:Tr[1^Cases[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]]&
. Siehe diesen Tipp .Count
noch kürzer alsCases
.Count[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]&
10^4
oder1*^4
ist kürzer als10000
und/@Range@
ist äquivalent zu~Array~
.Mathematica, 78 Bytes
quelle
Cases
ist4
Bytes kürzer:Tr[1^Cases[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]]&
. Siehe diesen Tipp .Count
ist noch kürzer:Count[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]&
Schale , 19 Bytes
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.
quelle
Japt ,
251917 BytesProbier es aus
Erläuterung
Implizite Eingabe einer Ganzzahl
U
.Generieren Sie ein Array von Ganzzahlen
õ
(L
) im Quadrat von 1 bis 100 ( ).Übergeben Sie jeweils eine Funktion (wobei
X
das aktuelle Element ist), die ein Array der Teiler (â
) von erzeugtX
.Ordnen Sie über diesem Array von Teilern zu, wo
Z
sich das aktuelle Element befindet.Holen Sie sich die absolute Differenz (
a
) vonZ
undX
dividiert durchZ
.Ist eines der Elemente (
d
) im resultierenden Array kleiner alsU
?Zählen Sie die wahrheitsgemäßen Elemente und geben Sie das Ergebnis implizit aus.
quelle
Ruby, 62 Bytes
Probieren Sie es online aus.
quelle
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.
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.quelle
Python 2 , 134 Bytes
Probieren Sie es online!
Eugh ... muss es viel besser machen.
quelle
len(filter(lambda n:n<i,...))
durchsum(n<i for n in ....)
Python 2 , 83 Bytes
Etwas langsam, benötigt 5 Sekunden pro Testfall
Probieren Sie es online!
quelle
PHP, 94 + 1 Bytes
Laufen Sie als Pipe mit
-nR
oder probieren Sie es online aus .quelle
VB.NET (.NET 4.5)
116115 BytesErläuterung:
Eine Funktion, die
n
als 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.s
als integraler Typ wird er für mich zu Boden geworfen.^
als Exponent. Während10000
also 5 Zeichen sind, sind10^4
es nur 4.return
, wird stattdessen der Wert der Funktionsvariablen zurückgegeben. Ich spare also Zeichen, indem ich keine separate Variable deklariere und keine return-Anweisung verwende.i
wird angenommen,Integer
weil ich ein Integer-Literal zugewiesen habe.A
wird angenommen,Object
aber sobald ich eine ganze Zahl hinzufüge, verhält es sich wie einInteger
.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-1
fürTrue
, also subtrahieren Sie, um das richtige Vorzeichen zu erhalten.Mod
nicht sein0
. 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>
.Byte
, um das zu speichern, und speichere Bytes in der Deklaration, indem ich einen Typ mit kürzerem Namen verwende.Probieren Sie es online!
quelle
C # (.NET Core) , 104 Byte
Probieren Sie es online!
quelle