A fórmula

Tomemos, por exemplo, o número 300

• Os fatores primos de 300 são [2, 3, 5](números únicos que são fatores de 300 e primos)
• Ao quadrado de cada um desses números, você [4, 9, 25]
• Somando essa lista, você terá 4 + 9 + 25 = 38
• Finalmente subtraia essa soma (38) do seu número original 300-38 = 262(este é o resultado)

Entrada

Sua entrada será um número inteiro positivo maior que 2. Você deve verificar todos os números de 2 ao valor de entrada (inclusive) e encontrar o número que produz o melhor resultado com a fórmula acima.

Sua saída será dois números separados por um espaço, vírgula, nova linha ou o que o idioma permitir (a separação é necessária para distinguir os dois números). Eles podem ser enviados para um arquivo, stdout ou o que o seu idioma usar. Seu objetivo é encontrar o número no intervalo que produz a saída máxima ao executar a fórmula acima. O primeiro número exibido deve ser o número inicial (como 300) e o segundo número deve ser a saída que a fórmula produziu (como 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

Considere a entrada 10, devemos executar a fórmula para todos os números de 2 a 10 (inclusive)

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

Como você pode ver, o melhor resultado é o 4resultado da inserção do valor 8na fórmula. Isso significa que a saída para uma entrada de 10deve ser8, 4

Pontuação e Regras

As regras padrão para entradas e saídas se aplicam: Padrão para Code Golf: Métodos de entrada / saída
As brechas padrão são proibidas: Brechas que são proibidas por padrão Os
envios podem ser funções ou programas completos

O menor código em bytes ganha

Pitão, 17 15 bytes

_eSttm,-ds^R2{P

Suíte de teste.

Java 8 lambda, 247 239 233 225 224 219 198 161 caracteres

Eu pensei que isso deveria ser possível em menos de 300 caracteres porque ... você sabe ... Java!

E é realmente possível mesmo em menos de 200 caracteres!

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

Não sei se esse uso de importações é legítimo, mas presumo que esteja tudo bem. Aqui está o lambda ungolfed em uma 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;
    }
}

A descoberta do primefator é baseada nesta resposta . O código usa a funcionalidade de conjuntos, pois eles salvam cada valor apenas uma vez, portanto, não preciso me preocupar com duplicatas adicionadas posteriormente. O restante do código é bastante direto, apenas seguindo a pergunta.

Atualizações

Removida a nova linha da saída.

Graças a @ogregoire por jogar golfe o Integer.MIN_VALUE para 1 << 31!

Depois de analisar o código novamente, encontrei mais alguns lugares onde as coisas podiam ser jogadas no golfe.

Obrigado a @Blue pelo truque == 0 a <1!

Removido algum espaço em branco restante. Também para a separação, é necessário apenas um caractere, para que não seja necessário desperdiçar um caractere.

Mais uma vez obrigado a @ogregoire por apontar que eu posso retornar o valor em vez de imprimi-lo e reunir as declarações! Isso economizou muito!

Descobri que posso usar um ternário em vez do segundo para salvar mais um caractere.

Obrigado a @AstronDan pelo impressionante uso de uma matriz que salva a importação. Isso também me deu a possibilidade de encurtar o primeiro caso para um ternário.

Na verdade, 21 bytes

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

Experimente online!

Explicação:

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

Experimente online!

O último caso demora muito para o compilador online, mas produz o resultado correto (leva cerca de 11 segundos no meu computador, rodando no Matlab):

Explicação

Aplicação direta do procedimento descrito.

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

Meu primeiro Code Golf :). Eu usei meu idioma favorito apesar de sua verbosidade. Comecei isso como uma porta de função C # do Java do @ Frozn, mas encontrei várias maneiras de reduzir ainda mais o código com otimizações.

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

Isso usa uma matriz para armazenar os principais fatores. Por ser indexado pelo fator, substituirá os fatores repetidos por cópias do fator. Isso permite que a função não tenha importações. Isso nem sequer requer sistema.

Utilitários Bash + GNU, 74

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

• seq gera todos os números inteiros 2 para n
• factorfornece o número seguido de dois pontos e, em seguida, uma lista separada por espaços de todos os fatores primos, incluindo duplicatas. por exemplo, o resultado para 12 é12: 2 2 3
• sedremove o cólon e os fatores duplicados e gera a expressão aritmética necessária. por exemplo, para 12:12- 2* 2- 3* 3
• bc avalia isso
• nl prefixos n de volta (começando em 2)
• sort pela segunda coluna, numericamente, em ordem decrescente
• seq imprime a primeira linha e sai.

Ideone.

Braquilog , 48 bytes

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

Explicação

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]

Gelatina , 13 bytes

ÆfQ²S_@,µ€ḊṀṚ

Experimente online! ou verifique todos os casos de teste .

Como funciona

Æ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

Código:

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

Explicação:

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]

Experimente online

Julia, 56 bytes

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

Experimente online!

Como funciona

Dada uma entrada n , para cada número inteiro k tal que 2 ≤ k ≤ n , geramos a tupla (f (k), k) , onde f (k) é a diferença entre k e a soma dos quadrados de seus fatores primos .

O próprio f (k) é calculado com k-sumabs2(k|>factor|>keys)quais fatores k em um Dict de chaves primas e valores de expoente, extrai todas as chaves (fatores primos), pega a soma de seus quadrados e subtrai o número inteiro resultante de k .

Finalmente, pegamos o máximo lexicográfico das tuplas geradas e o revertemos acessando-o nos índices 2 e 1 .

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

Apenas segue as regras. Calcula os fatores primos de cada número, coloque-os no quadrado e some-os. Depois disso, gere uma lista de vetores de 2 elementos: número inicial e seu resultado e encontre o elemento com o valor máximo do segundo elemento.

Você pode vê-lo online aqui: 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))

Eu trapacei e usei um pacote gmp.

CJam, 32 bytes

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

Experimente online!

Pyke, 17 bytes

FODP}mXs-)DSei@Oi

Experimente aqui!

PowerShell v2 +, 124 120 117 bytes

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

A primeira linha calcula os valores, a segunda é apenas a saída.

Começamos com a criação de um intervalo 2até o argumento da linha de comando $args[0]e fazemos um loop |%{...}. Cada loop definimos variáveis ​​auxiliares iguais ao nosso valor atual com $y=$z=$_. Em seguida, percorreremos todos os números 2até o número atual. A cada loop interno, verificamos se esse número é um divisor !($z%$_)e se é primo ('1'*$_-match'^(?!(..+)\1+$)..') , e se os dois subtraímos o quadrado de$y (as verificações são feitas usando a multiplicação booleana).

Depois de passar por todos os divisores primos e subtrair os quadrados, se o número restante for o maior que vimos até agora $y-gt$o, definimos nossas variáveis ​​de saída $o=$y;$p=$_. Depois de percorrer todo o intervalo, simplesmente produzimos um espaço entre eles.

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

Exemplo de uso: f 50-> [48,35].

As funções de fator principal estão disponíveis apenas através do import Data.Numbers.Primesqual custa muitos bytes, por isso estou usando o verificador principal do @ Lynn . O resto é simples: para a entrada de mcircuito natravés de [2..m]e num ciclo interno patravés [2..n]. Mantenha tudo o pque é primo e divida n, quadrado e soma.

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 em Ideone .

JavaScript (ES6), 111 105 bytes

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

Não faço ideia por que não pensei em fazer isso recursivamente antes.

J, 44 bytes

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

Abordagem direta. Também retorna todos os valores ndesse resultado em um valor máximo.

Uso

   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