La formule

Prenez par exemple le nombre 300

• Les facteurs premiers de 300 sont [2, 3, 5](les nombres uniques qui sont des facteurs de 300 et premiers)
• La mise au carré de chacun de ces nombres vous donnera [4, 9, 25]
• La sommation de cette liste vous donnera 4 + 9 + 25 = 38
• Enfin soustrayez cette somme (38) de votre nombre d'origine 300-38 = 262(c'est le résultat)

Contribution

Votre entrée sera un entier positif supérieur à 2. Vous devez vérifier tous les nombres de 2 à la valeur d'entrée (incluse) et trouver le nombre qui produit le meilleur résultat avec la formule ci-dessus.

Votre sortie sera composée de deux nombres séparés par un espace, une virgule, un retour à la ligne ou tout ce que votre langue permet (la séparation est nécessaire pour distinguer les deux nombres). Ceux-ci peuvent être exportés vers un fichier, une sortie standard ou tout ce que votre langue utilise. Votre objectif est de trouver le nombre dans la plage qui produit la sortie maximale lors de l'exécution de la formule ci-dessus. Le premier nombre affiché doit être le nombre de départ (comme 300) et le deuxième nombre doit être la sortie produite par la formule (comme 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

Considérez l'entrée de 10, nous devons exécuter la formule pour tous les nombres de 2 à 10 (inclus)

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

Comme vous pouvez le voir, le meilleur résultat est le 4résultat de la saisie de la valeur 8dans la formule. Cela signifie que la sortie d'une entrée de 10doit être8, 4

Notation et règles

Les règles par défaut pour les entrées et sorties s'appliquent: Par défaut pour Code Golf: Méthodes d'entrée / sortie
Les failles standard sont interdites: Les failles interdites par défaut
Les soumissions peuvent être des fonctions ou des programmes complets

Le code le plus court en octets gagne

Pyth, 17 15 octets

_eSttm,-ds^R2{P

Suite de tests.

Java 8 lambda, 247 239 233 225 224 219 198 161 caractères

Je pensais que cela devait être possible en moins de 300 caractères car ... vous savez ... Java!

Et c'est en effet possible même en moins de 200 caractères!

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;}

Je ne sais pas si cette utilisation des importations est légitime, mais je suppose qu'elle devrait être acceptable. Voici le lambda non golfé dans une classe:

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;
    }
}

La découverte du facteur principal est basée sur cette réponse . Le code utilise la fonctionnalité des ensembles car ils n'enregistrent chaque valeur qu'une seule fois, donc je n'ai pas à me soucier des doublons ajoutés plus tard. Le reste du code est assez simple, juste après la question.

Mises à jour

Suppression de la nouvelle ligne de la sortie.

Merci à @ogregoire d'avoir joué au Integer.MIN_VALUE au 1 << 31!

Après avoir regardé à nouveau le code, j'ai trouvé d'autres endroits où jouer.

Merci à @Blue pour l'astuce == 0 à <1!

Suppression de certains espaces restants. De plus, pour la séparation, un seul caractère est nécessaire, donc pas besoin de gaspiller un caractère.

Merci encore à @ogregoire d'avoir souligné que je peux retourner la valeur au lieu de l'imprimer et de rassembler les déclarations! Cela a sauvé beaucoup!

Découvert, je peux utiliser un ternaire au lieu du second si pour enregistrer un autre caractère.

Merci à @AstronDan pour l' utilisation impressionnante d'un tableau qui enregistre l'importation. Cela m'a également donné la possibilité de raccourcir le premier si en ternaire.

En fait, 21 octets

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

Essayez-le en ligne!

Explication:

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 octets

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

Essayez-le en ligne!

Le dernier cas prend trop de temps pour le compilateur en ligne, mais il produit le résultat correct (cela prend environ 11 secondes sur mon ordinateur, fonctionnant sur Matlab):

Explication

Application simple de la procédure décrite.

:         % 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 octets

Mon premier Code Golf :). J'ai utilisé ma langue préférée malgré sa verbosité. J'ai commencé cela comme un port de fonction C # de Java de @ Frozn, mais j'ai trouvé plusieurs façons de réduire davantage le code avec des optimisations.

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;}

Celui-ci utilise un tableau pour stocker les facteurs premiers. Parce qu'il est indexé par le facteur, il remplacera les facteurs répétés par des copies du facteur. Cela permet à la fonction de n'avoir aucune importation. Cela ne nécessite même pas de système.

Utilitaires Bash + GNU, 74

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

• seq génère tous les entiers 2 à n
• factordonne le nombre suivi de deux points, puis une liste séparée par des espaces de tous les facteurs premiers, y compris les doublons. Par exemple, le résultat pour 12 est12: 2 2 3
• sedsupprime les deux points et les facteurs en double, puis génère l'expression arithmétique requise. par exemple pour 12:12- 2* 2- 3* 3
• bc évalue cela
• nl préfixes n de retour (à partir de 2)
• sort par la deuxième colonne, numériquement, par ordre décroissant
• seq imprime la première ligne et quitte.

Ideone.

Brachylog , 48 octets

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

Explication

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]

Gelée , 13 octets

ÆfQ²S_@,µ€ḊṀṚ

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça fonctionne

Æ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 octets

Code:

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

Explication:

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]

Essayez-le en ligne

Julia, 56 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Étant donné une entrée n , pour chaque entier k tel que 2 ≤ k ≤ n , nous générons le tuple (f (k), k) , où f (k) est la différence entre k et la somme des carrés de ses facteurs premiers .

f (k) lui-même est calculé avec k-sumabs2(k|>factor|>keys), qui factorise k en un Dict de clés premières et de valeurs d'exposant, extrait toutes les clés (facteurs premiers), prend la somme de leurs carrés et soustrait l'entier résultant de k .

Enfin, nous prenons le maximum lexicographique des tuples générés et l'inversons en y accédant aux indices 2 et 1 .

Clojure, 215 octets

(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)))))

Suit juste les règles. Calcule les facteurs premiers de chaque nombre, les met au carré et les additionne. Après cela, générez une liste de vecteurs de 2 éléments: le nombre initial et son résultat et trouvez l'élément avec la valeur maximale du deuxième élément.

Vous pouvez le voir en ligne ici: https://ideone.com/1J9i0y

R 109 octets

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

J'ai triché et utilisé un paquet, gmp.

CJam, 32 octets

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

Essayez-le en ligne!

Pyke, 17 octets

FODP}mXs-)DSei@Oi

Essayez-le ici!

PowerShell v2 +, 124 120 117 octets

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

La première ligne calcule les valeurs, la seconde est juste sortie.

Nous commençons par créer une plage allant 2jusqu'à notre argument de ligne de commande $args[0]et bouclons cela |%{...}. Pour chaque boucle, nous définissons des variables d'assistance égales à notre valeur actuelle avec $y=$z=$_. Nous parcourons ensuite chaque numéro 2jusqu'à notre numéro actuel. Chaque boucle intérieure, nous vérifions si ce nombre est un diviseur !($z%$_)et s'il est premier ('1'*$_-match'^(?!(..+)\1+$)..') , et si c'est les deux, nous soustrayons le carré de$y (les vérifications sont effectuées en utilisant la multiplication booléenne).

Une fois que nous avons parcouru tous les diviseurs premiers et soustrait les carrés, si le nombre restant est le plus grand que nous ayons vu jusqu'à présent $y-gt$o, nous définissons nos variables de sortie $o=$y;$p=$_. Après avoir parcouru toute la gamme, nous sortons simplement avec un espace entre les deux.

Haskell, 91 octets

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]]

Exemple d'utilisation: f 50-> [48,35].

Les fonctions de facteur premier sont disponibles uniquement via import Data.Numbers.Primesce qui coûte trop d'octets, donc j'utilise le vérificateur principal de @ Lynn . Le reste est simple: pour l' entrée en mboucle à ntravers [2..m]et dans une boucle interne à ptravers [2..n]. Gardez tout ce pqui est premier et divisez n, carré et somme.

Python 2, 108 105 100 octets

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)

Testez-le sur Ideone .

JavaScript (ES6), 111 105 octets

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]}

Je ne sais pas pourquoi je ne pensais pas à le faire récursivement auparavant.

J, 44 octets

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

Approche directe. Renvoie également toutes les valeurs den ce résultat dans une valeur maximale.

Usage

   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