20
\$\begingroup\$

A proper divisor is a divisor of a number n, which is not n itself. For example, the proper divisors of 12 are 1, 2, 3, 4 and 6.

You will be given an integer x, x ≥ 2, x ≤ 1000. Your task is to sum all the highest proper divisors of the integers from 2 to x (inclusive) (OEIS A280050).

Example (with x = 6):

  • Find all the integers between 2 and 6 (inclusive): 2,3,4,5,6.

  • Get the proper divisors of all of them, and pick the highest ones from each number:

    • 2 -> 1
    • 3 -> 1
    • 4 -> 1, 2
    • 5 -> 1
    • 6 -> 1, 2, 3.
  • Sum the highest proper divisors: 1 + 1 + 2 + 1 + 3 = 8.

  • The final result is 8.

Test Cases

Input  |  Output
-------+---------
       |
 2     | 1
 4     | 4
 6     | 8
 8     | 13
 15    | 41
 37    | 229
 100   | 1690
 1000  | 165279

Rules

\$\endgroup\$
  • \$\begingroup\$ Sandbox. \$\endgroup\$ – Mr. Xcoder Jun 24 '17 at 11:18
  • 5
    \$\begingroup\$ If you're going to sandbox something, leave it in there for more than two hours. \$\endgroup\$ – Peter Taylor Jun 24 '17 at 12:57
  • \$\begingroup\$ @PeterTaylor I sandboxed the post only to receive feedback, because this is a very simple challenge which I would usually not post in the sandbox at all. BTW thanks for the edit. \$\endgroup\$ – Mr. Xcoder Jun 24 '17 at 13:05

35 Answers 35

13
\$\begingroup\$

Oasis, 4 bytes

Code:

nj+U

Try it online!

Explanation:

Extended version:

nj+00

    0   = a(0)
   0    = a(1)

a(n) =

n       # Push n
 j      # Get the largest divisor under n
  +     # Add to a(n - 1)
\$\endgroup\$
5
\$\begingroup\$

Husk, 7 bytes

ṁȯΠtptḣ

Try it online!

Explanation

Husk has no built-in for computing the divisors directly (yet), so I'm using prime factorization instead. The largest proper divisor of a number is the product of its prime factors except the smallest one. I map this function over the range from 2 to the input, and sum the results.

ṁȯΠtptḣ  Define a function:
      ḣ  Range from 1 to input.
     t   Remove the first element (range from 2).
ṁ        Map over the list and take sum:
 ȯ        The composition of
    p     prime factorization,
   t      tail (remove smallest prime) and
  Π       product.
\$\endgroup\$
5
\$\begingroup\$

Python 2, 50 bytes

f=lambda n,k=2:n/k and(f(n,k+1),n/k+f(n-1))[n%k<1]

This is slow and can't even cope with input 15 on TIO.

Try it online!

However, memoization (thanks @musicman523) can be used to verify all test cases.

Try it online!

Alternate version, 52 bytes

At the cost of 2 bytes, we can choose whether to compute f(n,k+1) or n/k+f(n-1).

f=lambda n,k=2:n>1and(n%k and f(n,k+1)or n/k+f(n-1))

With some trickery, this works for all test cases, even on TIO.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Since f is a pure function, you can memoize it to run the larger cases on TIO \$\endgroup\$ – musicman523 Jun 25 '17 at 2:55
  • \$\begingroup\$ Right, not being able to use a decorator threw me off. Thanks! \$\endgroup\$ – Dennis Jun 25 '17 at 3:06
4
\$\begingroup\$

Jelly, 6 bytes

ÆḌ€Ṫ€S

Try it online!

How it works

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum
\$\endgroup\$
4
\$\begingroup\$

Brachylog, 10 bytes

⟦bb{fkt}ᵐ+

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You have clearly won this in all languages so far :)) \$\endgroup\$ – Mr. Xcoder Jun 24 '17 at 11:35
4
\$\begingroup\$

JavaScript (ES6), 40 bytes

f=(n,i=2)=>n<2?0:n%i?f(n,i+1):n/i+f(n-1)
<input type=number oninput=o.textContent=f(this.value)><pre id=o>

A number equals the product of its highest proper divisor and its smallest prime factor.

\$\endgroup\$
  • \$\begingroup\$ stack overflows for n>352(at least in this snippet, dont know if it is my browser/machine dependency) while you are supposed to support at least upto n=1000. \$\endgroup\$ – officialaimm Jun 24 '17 at 13:27
  • \$\begingroup\$ @officialaimm It works for n=1000 if you use e.g. node --stack_size=8000. \$\endgroup\$ – Neil Jun 24 '17 at 22:01
4
\$\begingroup\$

05AB1E, 9 8 bytes

-1 Byte thanks to Leaky Nun's prime factor trick in his Pyth answer

L¦vyÒ¦PO

Try it online!

Explanation

L¦vyÒ¦PO
L¦       # Range [2 .. input]
  vy     # For each...
    Ò¦    # All prime factors except the first one
      P   # Product
       O  # Sum with previous results
         # Implicit print

Alternative 8 Byte solution (That doesnt work on TIO)

L¦vyѨθO    

and ofc alternative 9 Byte solution (That works on TIO)

L¦vyѨ®èO    
\$\endgroup\$
4
\$\begingroup\$

Retina, 31 24 bytes

7 bytes thanks to Martin Ender.

.+
$*
M!&`(1+)(?=\1+$)
1

Try it online!

How it works

The regex /^(1+)\1+$/ captures the largest proper divisor of a certain number represented in unary. In the code, the \1+ is turned to a lookahead syntax.

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

Mathematica, 30 bytes

Divisors[i][[-2]]~Sum~{i,2,#}&
\$\endgroup\$
4
\$\begingroup\$

Pyth, 13 9 8 bytes

1 byte thanks to jacoblaw.

tsm*FtPh

Test suite.

How it works

The largest proper divisor is the product of the prime factors except the smallest one.

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

Python 2 (PyPy), 73 71 70 bytes

n=input();r=[0]*n;d=1
while n:n-=1;r[d+d::d]=n/d*[d];d+=1
print sum(r)

Not the shortest Python answer, but this just breezes through the test cases. TIO handles inputs up to 30,000,000 without breaking a sweat; my desktop computer handles 300,000,000 in a minute.

At the cost of 2 bytes, the condition n>d could be used for a ~10% speed-up.

Thanks to @xnor for the r=[0]*n idea, which saved 3 bytes!

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Funny, I just wrote basically the same code. \$\endgroup\$ – xnor Jun 24 '17 at 16:12
  • \$\begingroup\$ l=[0]*n should allow you to get rid of -2. exec kinda kills the speed, but even a while loop would be shorter than my approach. \$\endgroup\$ – Dennis Jun 24 '17 at 16:22
  • \$\begingroup\$ This seems to be marginally faster than my approach. Mind if I edit that into my answer? \$\endgroup\$ – Dennis Jun 24 '17 at 16:42
  • \$\begingroup\$ Please, go for it. \$\endgroup\$ – xnor Jun 24 '17 at 16:43
  • 1
    \$\begingroup\$ @Mr.Xcoder Not in PyPy, but yes, sieves do fine for this kind of problem. \$\endgroup\$ – Dennis Jun 24 '17 at 17:20
4
\$\begingroup\$

Haskell, 48 46 43 bytes

f 2=1
f n=until((<1).mod n)pred(n-1)+f(n-1)

Try it online!

Edit: @rogaos saved two bytes. Thanks!

Edit II: ... and @xnor another 3 bytes.

\$\endgroup\$
  • \$\begingroup\$ -2 bytes: f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1) \$\endgroup\$ – vroomfondel Jun 24 '17 at 21:28
  • \$\begingroup\$ @rogaos: Thanks! I've tried the explicit recursion myself, but didn't remove sum, so I thought it isn't shorter. \$\endgroup\$ – nimi Jun 24 '17 at 21:49
  • 1
    \$\begingroup\$ until saves some more: until((<1).mod n)pred(n-1)+f(n-1) \$\endgroup\$ – xnor Jun 25 '17 at 4:30
4
\$\begingroup\$

Japt, 8+2=10 8 6 bytes

òâ1 xo

Test it

  • 1 byte saved thanks to ETHproductions.

Explanation

    :Implicit input of integer U.
ò   :Generate an array of integers from 1 to U, inclusive
â   :Get the divisors of each number,
1   :  excluding itself.
x   :Sum the main array
o   :by popping the last element from each sub-array.
    :Implicit output of result
\$\endgroup\$
  • \$\begingroup\$ Note that -x counts as two bytes according to this post. However, I think you can save a byte with ò2_â1 o (â excludes the original number when given an argument) \$\endgroup\$ – ETHproductions Jun 24 '17 at 14:02
  • \$\begingroup\$ Thanks, @ETHproductions; I'd missed both those things. I wonder does that apply retroactively to all solutions where we counted flags as 1 byte? I was working up an alternative solution that didn't use a flag anyway; pointing out â's argument got me the saving I was looking for. \$\endgroup\$ – Shaggy Jun 24 '17 at 14:27
  • \$\begingroup\$ I would assume so, since we weren't really following a consensus before. BTW, I had been playing with õ Å before and found a couple 8- and 9-byters: õ Åx_/k g, õ Åx_k Å×, õ Åx_â¬o. And by combining õ and Å with your genius xo trick I found a 7-byte solution :-) \$\endgroup\$ – ETHproductions Jun 24 '17 at 15:58
3
\$\begingroup\$

MATL, 12 bytes

q:Q"@Z\l_)vs

Try it at MATL Online

Explanation

        % Implicitly grab input (N)
q       % Subtract one
:       % Create an array [1...(N-1)]
Q       % Add one to create [2...N]
"       % For each element
  @Z\   % Compute the divisors of this element (including itself)
  l_)   % Grab the next to last element (the largest that isn't itself)
  v     % Vertically concatenate the entire stack so far
  s     % Sum the result
\$\endgroup\$
3
\$\begingroup\$

PHP, 56 bytes

for($i=1;$v||$argn>=$v=++$i;)$i%--$v?:$v=!$s+=$v;echo$s;

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Prolog (SWI), 72 bytes

f(A,B):-A=2,B=1;C is A-1,f(C,D),between(2,A,E),divmod(A,E,S,0),B is D+S.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Cubix, 27 39 bytes

?%\(W!:.U0IU(;u;p+qu.@Op\;;

Try it online!

Cubified

      ? % \
      ( W !
      : . U
0 I U ( ; u ; p + q u .
@ O p \ ; ; . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Watch It Run

  • 0IU Set up the stack with an accumulator, and the starting integer. U-turn into the outer loop
  • :(? duplicate the current top of stack, decrement and test
  • \pO@ if zero loop around the cube to a mirror, grab the bottom of stack, output and halt
  • %\! if positive, mod, relect and test.
    • u;.W if truthy, u-turn, remove mod result and lane change back into inner loop
    • U;p+qu;;\( if falsey, u-turn, remove mod result, bring accumulator to top, add current integer (top) divisor push to bottom and u-turn. Clean up the stack to have just accumulator and current integer, decrement the integer and enter the outer loop again.
\$\endgroup\$
3
\$\begingroup\$

C# (.NET Core), 74 72 bytes

n=>{int r=0,j;for(;n>1;n--)for(j=n;--j>0;)if(n%j<1){r+=j;j=0;}return r;}

Try it online!

  • 2 bytes shaved thanks to Kevin Cruijssen.
\$\endgroup\$
  • 1
    \$\begingroup\$ I know it's been about a year, but you can golf break to j=0. \$\endgroup\$ – Kevin Cruijssen Jun 20 '18 at 9:18
  • \$\begingroup\$ @KevinCruijssen a very simple but effective trick. Nice idea! \$\endgroup\$ – Charlie Jun 20 '18 at 9:22
2
\$\begingroup\$

Actually, 12 bytes

u2x⌠÷R1@E⌡MΣ

Try it online!

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

Python 3, 78 75 73 71 bytes

Not even close to Leaky nun's python answer in byte count.

f=lambda z:sum(max(i for i in range(1,y)if 1>y%i)for y in range(2,z+1))

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You're getting close to the first revision of my answer... you can check my editing history. \$\endgroup\$ – Leaky Nun Jun 24 '17 at 14:24
  • \$\begingroup\$ Oh, haha... I swear I did not steal it... :) \$\endgroup\$ – officialaimm Jun 24 '17 at 14:29
2
\$\begingroup\$

Python 3, 69 63 59 bytes

4 bytes thanks to Dennis.

f=lambda n:n-1and max(j for j in range(1,n)if n%j<1)+f(n-1)

Try it online!

I set the recursion limit to 2000 for this to work for 1000.

\$\endgroup\$
  • \$\begingroup\$ +1 You have my brownie points! That's the solution I was talking about when saying "shorter than 70 bytes"... \$\endgroup\$ – Mr. Xcoder Jun 24 '17 at 11:30
  • \$\begingroup\$ Also, this works in Python 2 as well \$\endgroup\$ – Mr. Xcoder Jun 24 '17 at 11:45
2
\$\begingroup\$

Charcoal, 37 bytes

A⁰βF…·²N«A⟦⟧δF⮌…¹ι«¿¬﹪ικ⊞δκ»A⁺β⌈δβ»Iβ

Try it online!

Link is to the verbose version. It took me almost all day to figure out how could I solve a non-ASCII-art-related question in Charcoal, but finally I got it and I am very proud of me. :-D

Yes, I am sure this can be golfed a lot. I just translated my C# answer and I am sure things can be done differently in Charcoal. At least it solves the 1000 case in a couple of seconds...

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

Pari/GP, 36 30 bytes

n->sum(i=2,n,i/divisors(i)[2])

Try it online!

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

Python 2 (PyPy), 145 bytes

Because turning code-golf competitions into fastest-code competitions is fun, here is an O(n) algorithm that, on TIO, solves n = 5,000,000,000 in 30 seconds. (Dennis’s sieve is O(n log n).)

import sympy
n=input()
def g(i,p,k,s):
 while p*max(p,k)<=n:l=k*p;i+=1;p=sympy.sieve[i];s-=g(i,p,l,n/l*(n/l*k+k-2)/2)
 return s
print~g(1,2,1,-n)

Try it online!

How it works

We count the size of the set

S = {(a, b) | 2 ≤ an, 2 ≤ b ≤ largest-proper-divisor(a)},

by rewriting it as the union, over all primes p ≤ √n, of

Sp = {(pd, b) | 2 ≤ dn/p, 2 ≤ bd},

and using the inclusion–exclusion principle:

|S| = ∑ (−1)m − 1 |Sp1 ∩ ⋯ ∩ Spm| over m ≥ 1 and primes p1 < ⋯ < pm ≤ √n,

where

Sp1 ∩ ⋯ ∩ Spm = {(p1pme, b) | 1 ≤ en/(p1pm), 2 ≤ bp1pm − 1e},
|Sp1 ∩ ⋯ ∩ Spm| = ⌊n/(p1pm)⌋⋅(p1pm − 1⋅(⌊n/(p1pm)⌋ + 1) − 2)/2.

The sum has Cn nonzero terms, where C converges to some constant that’s probably 6⋅(1 − ln 2)/π2 ≈ 0.186544. The final result is then |S| + n − 1.

\$\endgroup\$
  • \$\begingroup\$ Oooh, that's fast... \$\endgroup\$ – Mr. Xcoder Jun 25 '17 at 7:37
2
\$\begingroup\$

NewStack, 5 bytes

Luckily, there's actually a built in.

Nᵢ;qΣ

The breakdown:

Nᵢ       Add the first (user's input) natural numbers to the stack.
  ;      Perform the highest factor operator on whole stack.
   q     Pop bottom of stack.
    Σ    Sum stack.

In actual English:

Let's run an example for an input of 8.

Nᵢ: Make list of natural numbers from 1 though 8: 1, 2, 3, 4, 5, 6, 7, 8

;: Compute the greatest factors: 1, 1, 1, 2, 1, 3, 1, 4

q. Remove the first element: 1, 1, 2, 1, 3, 1, 4

Σ And take the sum: 1+1+2+1+3+1+4 = 13

\$\endgroup\$
  • \$\begingroup\$ 1+1+2+1+3+1+4 = 13 not 8. Apart from that: great answer so +1. \$\endgroup\$ – Kevin Cruijssen Jun 26 '17 at 8:53
  • \$\begingroup\$ @KevinCruijssen Whoops, thanks for catching that! \$\endgroup\$ – Graviton Jun 26 '17 at 8:56
2
\$\begingroup\$

Java 8, 78 74 72 bytes

n->{int r=0,j;for(;n>1;n--)for(j=n;j-->1;)if(n%j<1){r+=j;j=0;}return r;}

Port of @CarlosAlejo's C# answer.

Try it here.

Old answer (78 bytes):

n->{int r=0,i=1,j,k;for(;++i<=n;r+=k)for(j=1,k=1;++j<i;k=i%j<1?j:k);return r;}

Try it here.

Explanation (of old answer):

n->{                    // Method with integer parameter and integer return-type
  int r=0,              //  Result-integers
      i=1,j,k;          //  Some temp integers
  for(;++i<=n;          //  Loop (1) from 2 to `n` (inclusive)
      r+=k)             //    And add `k` to the result after every iteration
    for(j=1,k=1;++j<i;  //   Inner loop (2) from `2` to `i` (exclusive)
      k=i%j<1?j:k       //    If `i` is dividable by `j`, replace `k` with `j`
    );                  //   End of inner loop (2)
                        //  End of loop (2) (implicit / single-line body)
  return r;             //  Return result-integer
}                       // End of method
\$\endgroup\$
1
\$\begingroup\$

Lua, 74 bytes

c=0 for i=2,...do for j=1,i-1 do t=i%j<1 and j or t end c=c+t end print(c)

Try it online!

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

J, 18 bytes

[:+/1}.&.q:@+}.@i.

Try it online!

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

Stacked, 31 bytes

[2\|>[divisors:pop\MAX]map sum]

Try it online! (All testcases except for 1000, which exceeds the 60 second online time limit.)

Explanation

[2\|>[divisors:pop\MAX]map sum]
 2\|>                               range from 2 to the input inclusive
     [                ]map          map this function over the range
      divisors                      get the divisors of the number (including the number)
              :pop\                 pop a number off the array and swap it with the array
                   MAX              gets the maximum value from the array
                           sum      sum's all the max's
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 53 bytes

x;s;f(n){for(s=0;n>1;--n){for(x=n;n%--x;);s+=x;}n=s;}

Try it online!

Comfortably an quickly passes all test cases.

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