Proper Divisor mash-up

Question

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

• Default Loopholes apply.

• You can take input and provide output by any standard method.

• This is code-golf, the shortest valid submission in each language wins! Have Fun!

• Mr. Xcoder: Sandbox.
• Peter Taylor: If you're going to sandbox something, leave it in there for more than two hours.
• Mr. Xcoder: @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.

Answer 1

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)

Answer 2

Brachylog, 10 bytes

⟦bb{fkt}m+

Try it online!

• Mr. Xcoder: You have clearly won this in all languages so far :))
• Unrelated String: -2

Answer 3

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.

• jacoblaw: 8 bytes

Answer 4

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!

• xnor: Funny, I just wrote basically the same code.
• Dennis: 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: This seems to be marginally faster than my approach. Mind if I edit that into my answer?
• xnor: Please, go for it.
• Dennis: @Mr.Xcoder Not in PyPy, but yes, sieves do fine for this kind of problem.

Answer 5

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.

Answer 6

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!

• musicman523: Since f is a pure function, you can memoize it to run the larger cases on TIO
• Dennis: Right, not being able to use a decorator threw me off. Thanks!

Answer 7

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.

• vroomfondel: -2 bytes: f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
• nimi: @rogaos: Thanks! I've tried the explicit recursion myself, but didn't remove sum, so I thought it isn't shorter.
• xnor: until saves some more: until((<1).mod n)pred(n-1)+f(n-1)

Answer 8

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

Answer 9

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

Answer 10

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.

• 0xffcourse: 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.
• Neil: @officialaimm It works for n=1000 if you use e.g. node --stack_size=8000.

Answer 11

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 

Answer 12

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.

Answer 13

Mathematica, 30 bytes

Divisors[i][[-2]]~Sum~{i,2,#}&

Answer 14

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

• ETHproductions: 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)
• Shaggy: 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.
• ETHproductions: 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 :-)
• The Empty String Photographer: @ETHproductions note that this is not the consensus anymore. Flags do not count towards the byte count.

Answer 15

PHP, 56 bytes

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

Try it online!

Answer 16

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!

Answer 17

Pari/GP, (削除) 36 (削除ここまで) 30 bytes

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

Try it online!

Answer 18

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 ≤ a ≤ n, 2 ≤ b ≤ largest-proper-divisor(a)},

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

S_p = {(p⋅d, b) | 2 ≤ d ≤ n/p, 2 ≤ b ≤ d},

and using the inclusion–exclusion principle:

|S| = ∑ (−1)^{m − 1} |S_p1 ∩ ⋯ ∩ S_pm| over m ≥ 1 and primes p₁ < ⋯ < p_m ≤ √n,

where

S_p1 ∩ ⋯ ∩ S_pm = {(p₁⋯p_m⋅e, b) | 1 ≤ e ≤ n/(p₁⋯p_m), 2 ≤ b ≤ p₁⋯p_{m − 1}e},
|S_p1 ∩ ⋯ ∩ S_pm| = ⌊n/(p₁⋯p_m)⌋⋅(p₁⋯p_{m − 1}⋅(⌊n/(p₁⋯p_m)⌋ + 1) − 2)/2.

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

• Mr. Xcoder: Oooh, that's fast...

Answer 19

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.

Answer 20

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.

• Kevin Cruijssen: I know it's been about a year, but you can golf break to j=0.
• Charlie: @KevinCruijssen a very simple but effective trick. Nice idea!

Answer 21

Actually, 12 bytes

u2x⌠÷R1@E⌡MΣ

Try it online!

Answer 22

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!

• Leaky Nun: You're getting close to the first revision of my answer... you can check my editing history.
• 0xffcourse: Oh, haha... I swear I did not steal it... :)

Answer 23

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.

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

Answer 24

Charcoal, 37 bytes

A0βF...·2N«A⟦⟧δF⮌...1ι«¿¬%ικ⊞δκ»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...

Answer 25

NewStack, 5 bytes

Luckily, there's actually a built in.

Ni;qΣ

The breakdown:

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

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

• Kevin Cruijssen: 1+1+2+1+3+1+4 = 13 not 8. Apart from that: great answer so +1.

Answer 26

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

Answer 27

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

Answer 28

Arturo, 32 bytes

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

Try it!

Answer 29

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!

Answer 30

J, 18 bytes

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

Try it online!