17
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I've fixed a few spelling and grammar errors, and made the title more descriptive. I also changed the bit about disallowing whitespace separators, since that's clearly not what you meant (since newlines and spaces are whitespace characters). If this is not what you intended, feel free to revert the edit and make your intention clearer. \$\endgroup\$ – Mego May 24 '16 at 8:04
  • 2
    \$\begingroup\$ What should happen if several numbers are tied for the maximal result? \$\endgroup\$ – Dennis May 24 '16 at 15:32
  • 1
    \$\begingroup\$ @Dennis is it acceptable for me to allow it to be any number that generates the maximum result? I don't want to impose a new rule that breaks all the existing solutions. \$\endgroup\$ – Keatinge May 24 '16 at 16:24
  • 2
    \$\begingroup\$ Yes, that's probably the best option. 950 could be an example, where both [900, 862] and [945, 862] would be valid answers. \$\endgroup\$ – Dennis May 24 '16 at 16:44
  • 1
    \$\begingroup\$ Can I output the numbers in reverse order, e.g. for input 50: 35, 48? \$\endgroup\$ – nimi May 24 '16 at 17:56

19 Answers 19

5
\$\begingroup\$

Pyth, 17 15 bytes

_eSttm,-ds^R2{P

Test suite.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Integer.MIN_VALUE can be shortened as 1<<31. \$\endgroup\$ – Olivier Grégoire May 24 '16 at 13:21
  • 1
    \$\begingroup\$ Save 1 bytes with if(u%f<1) instead \$\endgroup\$ – Blue May 24 '16 at 16:25
  • 1
    \$\begingroup\$ Declare all your ints at the same place to avoid repeating int several times, and assign them their value there if possible. \$\endgroup\$ – Olivier Grégoire May 25 '16 at 10:47
  • 1
    \$\begingroup\$ Also, get rid of that System.out.println(...) and return a value instead of printing it: as the OP mentions, standard I/O method is in use. \$\endgroup\$ – Olivier Grégoire May 25 '16 at 10:51
  • 1
    \$\begingroup\$ You can also use the array trick that I used in C# to turn the hashset into an int array. This will likely let you drop the import saving many bytes. \$\endgroup\$ – AstroDan May 25 '16 at 13:05
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can you link to this language? \$\endgroup\$ – Not that Charles May 24 '16 at 16:03
  • 1
    \$\begingroup\$ @NotthatCharles You can click the language's name in the online interpreter. \$\endgroup\$ – Dennis May 24 '16 at 18:25
  • \$\begingroup\$ Ok I googled Actually Programming Language and found nothing even after browsing the 5th page of google results. What is this language? \$\endgroup\$ – Tejas Kale May 25 '16 at 11:16
  • 2
    \$\begingroup\$ @Tejas You could click on the name of the language which would send you to its source: github.com/Mego/Seriously \$\endgroup\$ – Amndeep7 May 25 '16 at 15:29
3
\$\begingroup\$

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

enter image description here

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         
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is a REALLY nice trick! Will try use it in my version \$\endgroup\$ – Frozn May 25 '16 at 13:16
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

CJam, 32 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pyke, 17 bytes

FODP}mXs-)DSei@Oi

Try it here!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.