Die Formel

Nehmen Sie zum Beispiel die Nummer 300

• Die Primfaktoren von 300 sind [2, 3, 5](eindeutige Zahlen, die Faktoren von 300 und Primzahlen sind)
• Durch Quadrieren jeder dieser Zahlen erhalten Sie [4, 9, 25]
• Wenn Sie diese Liste zusammenfassen, erhalten Sie 4 + 9 + 25 = 38
• Subtrahieren Sie schließlich diese Summe (38) von Ihrer ursprünglichen Zahl 300-38 = 262(dies ist das Ergebnis)

Eingang

Ihre Eingabe ist eine positive Ganzzahl größer als 2. Sie müssen alle Zahlen von 2 bis einschließlich des Eingabewerts überprüfen und die Zahl ermitteln, die mit der obigen Formel das beste Ergebnis erzielt.

Ihre Ausgabe besteht aus zwei Zahlen, die durch ein Leerzeichen, ein Komma, einen Zeilenvorschub oder in einer anderen Sprache voneinander getrennt sind (die Trennung ist erforderlich, um die beiden Zahlen voneinander zu unterscheiden). Diese können in eine Datei, eine Standardausgabe oder in eine andere Sprache ausgegeben werden. Ihr Ziel ist es, die Zahl in dem Bereich zu finden, der die maximale Ausgabe erzeugt, wenn Sie die obige Formel durchlaufen. Die erste angezeigte Zahl sollte die Startnummer sein (wie 300) und die zweite Zahl sollte die Ausgabe sein, die die Formel erzeugt hat (wie 262).

Input: 3       Output: 2, -2
Input: 10      Output: 8, 4
Input: 50      Output: 48, 35
Input: 1000    Output: 1000, 971
Input: 9999    Output: 9984, 9802

Betrachten wir die Eingabe von 10, müssen wir die Formel für alle Zahlen von 2-10 (einschließlich) ausführen.

Num PrimeFacs PrimeFacs^2 SumPrimeFacs^2 Result
2   [2]       [4]         4              -2
3   [3]       [9]         9              -6
4   [2]       [4]         4               0
5   [5]       [25]        25             -20
6   [2, 3]    [4, 9]      13             -7
7   [7]       [49]        49             -42
8   [2]       [4]         4               4
9   [3]       [9]         9               0
10  [2, 5]    [4, 25]     29             -19

Wie Sie sehen, ist das beste Ergebnis 4das Ergebnis der Eingabe des Werts 8in die Formel. Das heißt die Ausgabe für eine Eingabe von 10sollte sein8, 4

Wertung & Regeln

Es gelten die Standardregeln für Ein- und Ausgaben: Standard für Code Golf: Eingabe- / Ausgabemethoden
Die Standardlücken sind verboten: Lücken , die standardmäßig verboten sind
Einsendungen können Funktionen oder vollständige Programme sein

Kürzester Code in Bytes gewinnt

Pyth, 17 15 Bytes

_eSttm,-ds^R2{P

Testsuite.

Java 8 Lambda, 247 239 233 225 224 219 198 161 Zeichen

Ich dachte, das muss in weniger als 300 Zeichen möglich sein, weil ... du weißt ... Java!

Und es ist in der Tat sogar in weniger als 200 Zeichen möglich!

m->{int n=1,u,f,F[],g,G=g=1<<31;for(;++n<=m;){u=n;F=new int[m+1];for(f=1;++f<=u;)u/=u%f<1?(F[f]=f--):1;f=0;for(int p:F)f+=p*p;g=n-f>g?(G=n)-f:g;}return G+","+g;}

Ich weiß nicht, ob diese Verwendung von Importen legitim ist, aber ich gehe davon aus, dass es in Ordnung sein sollte. Hier ist der Lambda ungolfed in eine Klasse:

public class Q80507 {
    static String greatestAfterReduction(int maxNumber) {
        int number = 1, upper, factor, primeFactors[], greatestResult, greatestNumber = greatestResult = 1 << 31; // <-- Integer.MIN_VALUE;
        for (;++number <= maxNumber;) {
            // get unique primefactors
            upper = number;
            primeFactors = new int[maxNumber + 1];
            for (factor = 1; ++factor <= upper;)
                upper /= upper % factor < 1 ? (primeFactors[factor] = factor--) : 1;

            factor = 0;
            for (int prime : primeFactors)
                factor += prime * prime;

            greatestResult = number - factor > greatestResult ? (greatestNumber = number) - factor : greatestResult;
        }
        return greatestNumber + "," + greatestResult;
    }
}

Die Ermittlung des Primefaktors basiert auf dieser Antwort . Der Code nutzt die Funktionalität von Mengen, da sie jeden Wert nur einmal speichern, sodass ich mich später nicht mehr um hinzugefügte Duplikate kümmern muss. Der Rest des Codes ist ziemlich einfach und folgt nur der Frage.

Aktualisierung

Die neue Zeile wurde aus der Ausgabe entfernt.

Vielen Dank an @ogregoire für das Golfen der Integer.MIN_VALUE auf 1 << 31!

Nachdem ich den Code noch einmal durchgesehen hatte, fand ich einige weitere Stellen, an denen man Golf spielen konnte.

Vielen Dank an @Blue für den == 0 to <1 Trick!

Restliches Leerzeichen entfernt. Auch für die Trennung wird nur ein Char benötigt, sodass kein Char verschwendet werden muss.

Nochmals vielen Dank an @ogregoire für den Hinweis, dass ich den Wert zurückgeben kann, anstatt ihn auszudrucken und die Erklärungen zusammenzustellen! Das hat viel gespart!

Ich habe herausgefunden, dass ich anstelle des zweiten einen Ternären verwenden kann, um einen weiteren Buchstaben zu speichern.

Vielen Dank an @AstronDan für die großartige Verwendung eines Arrays, das den Import spart. Das gab mir auch die Möglichkeit, das erste wenn in ein ternäres zu kürzen.

Eigentlich 21 Bytes

u2x;`;y;*@-`M;M;)@í@E

Probieren Sie es online!

Erläuterung:

u2x;`;y;*@-`M;M;)@í@E
u2x;                   push two copies of range(2, n+1) ([2, n])
    `      `M          map:
     ;                   duplicate
      y;                 push two copies of prime divisors
        *                dot product of prime divisors lists (equivalent to sum of squares)
         @-              subtract from n
             ;M;)      duplicate, two copies of max, move one copy to bottom of stack
                 @í    get index of max element
                   @E  get corresponding element from range

MATL , 18 Bytes

:"@tYfu2^s-]v2#X>w

Probieren Sie es online!

Der letzte Fall dauert für den Online-Compiler zu lange, führt jedoch zu dem richtigen Ergebnis (es dauert ungefähr 11 Sekunden auf meinem Computer, der unter Matlab ausgeführt wird):

Erläuterung

Einfache Anwendung des beschriebenen Verfahrens.

:         % Implicit input n. Range [1 2 ... n]
"         % For each
  @       %   Push that number
  tYfu    %   Duplicate. Prime factors. Unique values
  2^s-    %   Square. Sum of array values. Subtract
]         % End for each
v         % Concatenate stack contents into vertical vector
2#X>      % Max and arg max
w         % Swap. Implicit display         

C #, 194 Bytes

Mein erster Code Golf :). Ich habe meine Lieblingssprache trotz ihrer Ausführlichkeit benutzt. Ich habe dies als C # -Funktionsport von @ Frozns Java gestartet, aber verschiedene Möglichkeiten gefunden, den Code durch Optimierungen weiter zu verkleinern.

string R(int a){int u,f,g,N=g=1<<31;for(int n=1;++n<=a;){u=n;int[]P=new int[a+1];for(f=1;++f<=u;){if(u%f<1){u/=f;P[f]=f--;}}f=0;foreach(var p in P){f+=p*p;}if(n-f>g){g=(N=n)-f;}}return N+","+g;}

Dies verwendet ein Array, um die Primfaktoren zu speichern. Da es durch den Faktor indiziert ist, werden wiederholte Faktoren durch Kopien des Faktors ersetzt. Dadurch kann die Funktion nicht importiert werden. Dies erfordert nicht einmal System.

Bash + GNU-Dienstprogramme, 74

seq 2 $1|factor|sed -r 's/:?( \w+)\1*/-\1*\1/g'|bc|nl -v2|sort -nrk2|sed q

• seq generiert alle ganzen Zahlen 2 bis n
• factorGibt die Zahl gefolgt von einem Doppelpunkt und einer durch Leerzeichen getrennten Liste aller Primfaktoren einschließlich Duplikate an. zB ist das Ergebnis für 1212: 2 2 3
• sedEntfernt den Doppelpunkt und doppelte Faktoren und generiert dann den erforderlichen arithmetischen Ausdruck. zB für 12:12- 2* 2- 3* 3
• bc bewertet dies
• nl Präfixe n wieder ein (ab 2)
• sort durch die zweite Spalte numerisch in absteigender Reihenfolge
• seq druckt die erste Zeile und wird beendet.

Ideone.

Brachylog , 48 Bytes

:2:{eI$pd:{:2^.}a+:I--:I.}fF$\hor:0m:Ir.r~m[F:J]

Erläuterung

Main predicate:

:2:{}fF                     Unify F with the list of all binding for which predicate 1 is
                            true, given [Input, 2] as input.
       $\hor:0m             Retrieve the max of F by diagonalizing it, taking the
                            first row, sorting that row and reversing the sorted row.
               :Ir.         Unify the Output with [I, Max],
                   r~m[F:J] [I, Max] is in F at index J (the index is unimportant)


Predicate 1:

eI                          I is an integer in the range given in Input
  $pd                       Get the list of prime factors of I, with no duplicates
     :{:2^.}a               Apply squaring to each element of that list
             +              Sum the list
              :I-           Subtract I from the sum
                 -          Multiply by -1 (let's call it Result)
                  :I.       Unify the Output with [Result, I]

Jelly , 13 Bytes

ÆfQ²S_@,µ€ḊṀṚ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

ÆfQ²S_@,µ€ḊṀṚ  Main link. Argument: n

        µ      Combine the chain to the left into a link.
         €     Apply it to each k in [1, ..., n].
Æf               Yield k's prime factors as a list.
  Q              Unique; deduplicate the prime factors.
   ²             Square each unique prime factor.
    S            Compute their sum.
     _@          Subtract the result from k.
       ,         Pair with k, yielding [result(k), k].
          Ḋ    Dequeue; discard the first pair which corresponds to k = 1.
           Ṁ   Get the maximum (lexicographical order).
            Ṛ  Reverse the pair.

05AB1E, 19 17 16 Bytes

Code:

L©f€n€O®-®)ø¦{¤R

Erläuterung:

L                    # make a list of 1..input [1,2,3,4,5,6]
 ©                   # save the list for reuse
  f                  # get primefactors of numbers in list [[],[2],[3],[2],[5],[2,3]]
   €n                # square each factor [[],[4],[9],[4],[25],[4,9]]
     €O              # sum the factors [0,4,9,4,25,13]
       ®-            # subtract from saved list [1,-2,-6,0,-20,-7]
         ®)ø         # zip with saved list [[1,1],[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
            ¦        # drop the first item (n=1) [[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
             {       # sort [[-20,5],[-7,6],[-6,3],[-2,2],[0,4]]
              ¤      # get last item [0,4]
               R     # reverse [4,0]

Probieren Sie es online aus

Julia, 56 Bytes

!n=maximum(k->(k-sumabs2(k|>factor|>keys),k),2:n)[[2,1]]

Probieren Sie es online!

Wie es funktioniert

Bei einer Eingabe n erzeugen wir für jede ganze Zahl k , die 2 ≤ k ≤ n ist , das Tupel (f (k), k) , wobei f (k) die Differenz zwischen k und der Summe der Quadrate seiner Primfaktoren ist .

f (k) selbst wird berechnet mit k-sumabs2(k|>factor|>keys), welche Faktoren k in ein Dict von Prim- und Exponentenwerten, alle Schlüssel (Primfaktoren) extrahiert, die Summe ihrer Quadrate und die resultierende ganze Zahl von k subtrahiert .

Schließlich nehmen wir das lexikographische Maximum der generierten Tupel und kehren es um, indem wir auf die Indizes 2 und 1 zugreifen .

Clojure, 215 Bytes

(fn j[x](apply max-key second(map(fn[w][w(- w(let[y(reduce +(map #(* % %)(set(flatten((fn f[q](let[c(filter(fn[r](=(mod q r)0))(range 2 q))](if(empty? c)q(map f c))))w)))))](if(= y 0)(* w w)y)))])(range 2(inc x)))))

Befolgen Sie einfach die Regeln. Berechnet die Primfaktoren jeder Zahl, setzt sie in Quadrate und summiert sie. Danach erzeugen Sie eine Liste von Vektoren aus 2 Elementen: Anfangszahl und deren Ergebnis und finden das Element mit dem Maximalwert des zweiten Elements.

Sie können es hier online sehen: https://ideone.com/1J9i0y

R 109 Bytes

y=sapply(x<-2:scan(),FUN=function(x)x-sum(unique(as.numeric(gmp::factorize(x))^2)));c(x[which.max(y)],max(y))

Ich habe geschummelt und ein Päckchen benutzt gmp.

CJam, 32 Bytes

ri({))_mf_|2f#:+-}/]_:e>_@#))\]p

Probieren Sie es online!

Pyke, 17 Bytes

FODP}mXs-)DSei@Oi

Probieren Sie es hier aus!

PowerShell v2 +, 124 120 117 Byte

2..$args[0]|%{$y=$z=$_;2..$_|%{$y-=$_*$_*!($z%$_)*('1'*$_-match'^(?!(..+)\1+$)..')};if($y-gt$o){$o=$y;$p=$_}}
"$p $o"

Die erste Zeile berechnet die Werte, die zweite Zeile wird gerade ausgegeben.

Wir beginnen mit der Erstellung eines Bereichs von 2bis zu unserem Befehlszeilenargument $args[0]und wiederholen diesen |%{...}. In jeder Schleife setzen wir Hilfsvariablen gleich unserem aktuellen Wert mit $y=$z=$_. Wir durchlaufen dann jede Nummer von 2bis zu unserer aktuellen Nummer. In jeder inneren Schleife prüfen wir, ob diese Zahl ein Divisor !($z%$_)und eine Primzahl ist ('1'*$_-match'^(?!(..+)\1+$)..') , und subtrahieren das Quadrat von beiden$y (die Prüfungen werden mit Boolescher Multiplikation durchgeführt).

Sobald wir alle Primteiler durchlaufen und die Quadrate subtrahiert haben und die verbleibende Zahl die größte ist, die wir bisher gesehen haben $y-gt$o, setzen wir unsere Ausgabevariablen $o=$y;$p=$_. Nachdem wir den gesamten Bereich durchlaufen haben, geben wir einfach mit einem Leerzeichen dazwischen aus.

Haskell, 91 Bytes

f m=reverse$maximum[[n-sum[p^2|p<-[2..n],mod n p<1,mod(product[1..p-1]^2)p>0],n]|n<-[2..m]]

Anwendungsbeispiel: f 50 -> [48,35].

Prime Factor-Funktionen sind nur verfügbar import Data.Numbers.Primes, wenn sie zu viele Bytes kosten. Daher verwende ich @ Lynns Prime Checker . Der Rest ist einfach: für mEingangsschleife ndurch [2..m]und in einer inneren Schleife pdurch [2..n]. Behalte alles p, was Primzahl und Teilung ist n, Quadrat und Summe.

Python 2, 108 105 100 Bytes

f=lambda n,m=2,p=1:m>n or-~f(n,m+1,p*m*m)-(n%m<p%m)*m*m
r=max(range(2,input()+1),key=f)
print r,f(r)

Teste es auf Ideone .

JavaScript (ES6), 111 bis 105 Byte

f=n=>{r=n<2?[]:f(n-1);for(s=[],j=n,i=2;j>1;k%i?i++:j/s[i]=i);s.map(i=>j-=i*i,j=n);return j<r[1]?r:[n,j]}

Keine Ahnung, warum ich vorher nicht daran gedacht habe, dies rekursiv zu tun.

J, 44 Bytes

[:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.

Unkomplizierter Ansatz. Gibt auch alle Werte ndieses Ergebnisses in einem Maximalwert zurück.

Verwendung

   f =: [:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.
   f 3
2 _2
   f 10
8 4
   f 50
48 35
   f 1000
1000 971
   f 9999
9984 9802
   f 950
900 862
945 862