# Proper Divisor mash-up

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

• Sandbox. – Mr. Xcoder Jun 24 '17 at 11:18
• If you're going to sandbox something, leave it in there for more than two hours. – Peter Taylor Jun 24 '17 at 12:57
• @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. – Mr. Xcoder Jun 24 '17 at 13:05

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


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


# 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!

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

# 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


# Brachylog, 10 bytes

⟦bb{fkt}ᵐ+


Try it online!

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

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

• 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. – officialaimm Jun 24 '17 at 13:27
• @officialaimm It works for n=1000 if you use e.g. node --stack_size=8000. – Neil Jun 24 '17 at 22:01

# 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


# Retina, 31 24 bytes

7 bytes thanks to Martin Ender.

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


Try it online!

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. # Mathematica, 30 bytes Divisors[i][[-2]]~Sum~{i,2,#}&  # Pyth, 139 8 bytes 1 byte thanks to jacoblaw. tsm*FtPh  ## How it works The largest proper divisor is the product of the prime factors except the smallest one. # Python 2 (PyPy), 7371 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! • Funny, I just wrote basically the same code. – xnor Jun 24 '17 at 16:12 • 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. – Dennis Jun 24 '17 at 16:22 • This seems to be marginally faster than my approach. Mind if I edit that into my answer? – Dennis Jun 24 '17 at 16:42 • Please, go for it. – xnor Jun 24 '17 at 16:43 • @Mr.Xcoder Not in PyPy, but yes, sieves do fine for this kind of problem. – Dennis Jun 24 '17 at 17:20 ## Haskell, 4846 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. • -2 bytes: f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1) – vroomfondel Jun 24 '17 at 21:28 • @rogaos: Thanks! I've tried the explicit recursion myself, but didn't remove sum, so I thought it isn't shorter. – nimi Jun 24 '17 at 21:49 • until saves some more: until((<1).mod n)pred(n-1)+f(n-1) – xnor Jun 25 '17 at 4:30 # Japt, 8+2=108 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  • 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) – ETHproductions Jun 24 '17 at 14:02 • 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. – Shaggy Jun 24 '17 at 14:27 • 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 :-) – ETHproductions Jun 24 '17 at 15:58 # 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  # PHP, 56 bytes for($i=1;$v||$argn>=$v=++$i;)$i%--$v?:$v=!$s+=$v;echo$s;


Try it online!

# 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!

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

# 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.
• I know it's been about a year, but you can golf break to j=0. – Kevin Cruijssen Jun 20 '18 at 9:18
• @KevinCruijssen a very simple but effective trick. Nice idea! – Charlie Jun 20 '18 at 9:22

# Actually, 12 bytes

u2x⌠÷R1@E⌡MΣ


Try it online!

# 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!

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

# Python 3, 6963 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.

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

# Charcoal, 37 bytes

Ａ⁰βＦ…·²Ｎ«Ａ⟦⟧δＦ⮌…¹ι«¿¬﹪ικ⊞δκ»Ａ⁺β⌈δβ»Ｉβ


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

# Pari/GP, 36 30 bytes

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


Try it online!

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

• Oooh, that's fast... – Mr. Xcoder Jun 25 '17 at 7:37

# 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

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

# Java 8, 7874 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


# 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!

# J, 18 bytes

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


Try it online!

# 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


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