Greatest Number in a Range When The Sum of Squares of its Prime Factors are Subtracted

Question

The formula

Take for instance the number 300

• The prime factors of 300 are [2, 3, 5] (unique numbers that are factors of 300 and prime)
• Squaring each of those numbers will give you [4, 9, 25]
• Summing that list will give you 4 + 9 + 25 = 38
• Finally subtract that sum (38) from your original number 300-38 = 262 (this is the result)

---

Input

Your input will be a positive integer greater than 2. You must check all numbers from 2 to the input value (inclusive) and find the number that produces the greatest result with the formula above.

---

Output

Your output will be two numbers separated by a space, comma, newline or whatever you language allows (the separation is necessary to distinguish the two numbers). These can be output to a file, stdout, or whatever your language uses. Your goal is to find the number in the range that produces the maximum output when run through the formula above. The first number displayed should be the starting number (like 300) and the second number should be the output that the formula produced (like 262)

---

Test Cases

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

---

Worked Through Example

Consider the input of 10, we must run the formula for all numbers from 2-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

As you can see the greatest result is 4, which was a result of inputting the value 8 into the formula. That means the output for an input of 10 should be 8, 4

---

Scoring & Rules

The default rules for inputs and outputs apply: Default for Code Golf: Input/Output methods
The standard loopholes are forbidden: Loopholes that are forbidden by default
Submissions can be functions or full programs

Shortest code in bytes wins

Answer 1

Pyth, 17 15 bytes

_eSttm,-ds^R2{P

Test suite.

Answer 2

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

I thought that must be possible in under 300 chars because... you know... Java!

And it is indeed possible even in under 200 chars!

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

I don't know whether this use of imports is legit but I assume, that it should be okay. Here is the lambda ungolfed into a class:

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

The primefactor-finding is based on this answer. The code uses the functionality of sets as they only save each value once, thus I don't have to care about added duplicates later on. The rest of the code is pretty straight forward, just following the question.

Updates

Removed the newline from the output.

Thanks to @ogregoire for golfing the Integer.MIN_VALUE to 1<<31!

After looking on the code again I found some more places where things could been golfed.

Thanks to @Blue for the ==0 to <1 trick!

Removed some leftover whitespace. Also for separation only one char is needed so no need to waste one char.

Thanks again to @ogregoire for pointing out that I can return the value instead of printing it and putting together the declarations! This saved a lot!

Found out I can use a ternary instead of the second if to save one more char.

Thanks to @AstronDan for the awesome usage of an array which saves the import. That also gave me the possibility to shorten the first if into a ternary.

Answer 3

Actually, 21 bytes

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

Try it online!

Explanation:

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
                

Answer 4

MATL, 18 bytes

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

Try it online!

The last case takes too long for the online compiler, but it produces the correct result (it takes about 11 seconds in my computer, running on Matlab):

Explanation

Straightforward application of the described procedure.

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

Answer 5

05AB1E, 19 17 16 bytes

Code:

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

Explanation:

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]

Try it online

Answer 6

C#, 194 bytes

My first Code Golf :). I used my favorite language despite its verbosity. I started this as a C# function port of @Frozn's Java but found several ways to shrink the code further with optimizations.

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

This uses an array to store the prime factors. Because it is indexed by the factor it will replace repeated factors with copies of the factor. This allows the function to have no imports. This does not even require System.

Answer 7

Bash + GNU utilities, 74

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

• seq generates all integers 2 to n
• factor gives the number followed by a colon, then a space separated list of all prime factors, including duplicates. e.g. the result for 12 is 12: 2 2 3
• sed removes the colon and duplicate factors, then generates the required arithmetic expression. e.g. for 12: 12- 2* 2- 3* 3
• bc evaluates this
• nl prefixes n back in (starting at 2)
• sort by the second column, numerically, in descending order
• seq prints the first line and quits.

Ideone.

Answer 8

Brachylog, 48 bytes

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

Explanation

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]

Answer 9

Jelly, 13 bytes

ÆfQ²S_@,µ€ḊṀṚ

Try it online! or verify all test cases.

How it works

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

Answer 10

Julia, 56 bytes

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

Try it online!

How it works

Given an input n, for each integer k such that 2 ≤ k ≤ n, we generate the tuple (f(k), k), where f(k) is the difference between k and the sum of the squares of its prime factors.

f(k) itself is calculated with k-sumabs2(k|>factor|>keys), which factors k into a Dict of prime keys and exponent values, extracts all the keys (prime factors), takes the sum of their squares and subtracts the resulting integer from k.

Finally, we take the lexicographical maximum of the generated tuples and reverse it by accesing it at indices 2 and 1.

Answer 11

05AB1E, 13 bytes

Ties Dennis's Jelly answer for #1.

L¦DfnO-Z©kÌ®)

Try it online!

L¦DfnO-Z©kÌ®)  # full program
         k     # push 0-based index of...
       Z       # maximum of...
               # (implicit) list of...
     O         # sums of...
               # (implicit) each element of list of...
   f           # unique prime factors of...
               # (implicit) each element of...
L D            # [1, 2, 3, ...,
               # ..., implicit input...
L D            # ]...
 ¦             # excluding the first element...
               # (implicit) with each element...
    n          # squared...
               # (implicit) with each element...
      -        # subtracted from...
               # (implicit) corresponding element in...
L              # [1, 2, 3, ...,
               # ..., implicit input...
L              # ]...
 ¦             # excluding the first element...
         k     # in...
               # (implicit) list of...
     O         # sums of...
               # (implicit) each element of list of...
   f           # unique prime factors of...
               # (implicit) each element of...
L D            # [1, 2, 3, ...,
               # ..., implicit input...
L D            # ]...
 ¦             # excluding the first element...
               # (implicit) with each element...
    n          # squared...
               # (implicit) with each element...
      -        # subtracted from...
               # (implicit) corresponding element in...
L              # [1, 2, 3, ...,
               # ..., implicit input...
L              # ]...
 ¦             # excluding the first element...
          Ì    # plus 2
       Z©  ®   # push maximum of...
               # (implicit) list of...
     O         # sums of...
               # (implicit) each element of list of...
   f           # unique prime factors of...
               # (implicit) each element of...
L D            # [1, 2, 3, ...,
               # ..., implicit input...
L D            # ]...
 ¦             # excluding the first element...
               # (implicit) with each element...
    n          # squared...
               # (implicit) with each element...
      -        # subtracted from...
               # (implicit) corresponding element in...
L              # [1, 2, 3, ...,
               # ..., implicit input...
L              # ]...
 ¦             # excluding the first element
            )  # push stack
               # implicit output

Note: If only the calculated number needed to be output, then 5 bytes could be saved by removing ©kÌ®).

Answer 12

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

Just follows the rules. Calculates prime factors of each number, put them to square and sum them. After that generate a list of vectors of 2 elements: initial number and its result and find the element with maximum value of second element.

You can see it online here: https://ideone.com/1J9i0y

Answer 13

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

I cheated and used a package, gmp.

Answer 14

CJam, 32 bytes

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

Try it online!

Answer 15

Pyke, 17 bytes

FODP}mXs-)DSei@Oi

Try it here!

Answer 16

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"

The first line calculates the values, the second is just output.

We start with creating a range from 2 up to our command-line argument $args[0] and loop that |%{...}. Each loop we set helper variables equal to our current value with $y=$z=$_. We then loop through every number from 2 up to our current number. Each inner loop we check whether that number is a divisor !($z%$_) and whether it's prime ('1'*$_-match'^(?!(..+)\1+$)..'), and if it's both we subtract the square from $y (the checks are done using Boolean multiplication).

Once we've gone through all prime divisors and subtracted the squares, if the number remaining is the largest we've seen so far $y-gt$o, we set our output variables $o=$y;$p=$_. After we've looped through the whole range, we simply output with a space between.

Answer 17

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

Usage example: f 50-> [48,35].

Prime factor functions are available only via import Data.Numbers.Primes which costs too many bytes, so I'm using @Lynn's prime checker. The rest is straight forward: for input m loop n through [2..m] and in an inner loop p through [2..n]. Keep all p that are prime and divide n, square and sum.

Answer 18

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)

Test it on Ideone.

Answer 19

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

No idea why I didn't think to do this recursively before.

Answer 20

J, 44 bytes

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

Straight-forward approach. Also returns all values of n that result in a maximum value.

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

Answer 21

Vyxal, 10 bytes

ḢλǏ²∑-;Z↑Ṅ

Try it Online!

Maximum by tail is useless they said. No one ever uses it they said. Well look who's laughing now.

Explained

ḢλǏ²∑-;Z↑Ṅ
Ḣ      Z   # Create a list of [x, f(x)] from range(2, input + 1) where f(x) = 
 λ    ;    # lambda x:
  Ǐ        #  prime factors
   ²       #  squared
    ∑      #  summed
     -     #  subtracted from x
        ↑  # maximum by tail
         Ṅ # joined on spaces

Answer 22

Japt -h, 17 bytes

Tried a few different approaches but can't seem to do better than 17 :\

ô í ¤mÇ-k â x²ÃñÌ

Try it

õ@[XX-k â x²]ÃÅñÌ

Try it