# 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. Jun 24, 2017 at 11:18
• If you're going to sandbox something, leave it in there for more than two hours. Jun 24, 2017 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. Jun 24, 2017 at 13:05

# Oasis, 4 bytes

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)

# Brachylog, 10 bytes

⟦bb{fkt}ᵐ+

Try it online!

• You have clearly won this in all languages so far :)) Jun 24, 2017 at 11:35
• -2 Oct 22, 2020 at 12:04

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

• 8 bytes Jun 24, 2017 at 17:46

ṁȯΠ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 Jun 25, 2017 at 2:55
• Right, not being able to use a decorator threw me off. Thanks! Jun 25, 2017 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

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

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. Jun 20, 2018 at 9:18
• @KevinCruijssen a very simple but effective trick. Nice idea! Jun 20, 2018 at 9:22

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. Jun 24, 2017 at 14:24
• Oh, haha... I swear I did not steal it... :) Jun 24, 2017 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"... Jun 24, 2017 at 11:30
• Also, this works in Python 2 as well Jun 24, 2017 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... Jun 25, 2017 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. Jun 26, 2017 at 8:53
• @KevinCruijssen Whoops, thanks for catching that! Jun 26, 2017 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;}

Try it here.

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.

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

# Thunno 2-S, 5 bytes

ı⁺FṫG

Try it online!

#### Explanation

ı⁺FṫG  # Implicit input
# Decrement the input
ı      # Map over [1..input-1]:
⁺     #  Increment the number
Fṫ   #  Push the proper divisors
G  #  Maximum of this list
# Sum the list
# Implicit output

# Arturo, 32 bytes

\$=>[∑map..2&=>[x:do factors&]]

Try it!

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