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

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ Sandbox. \$\endgroup\$ Commented Jun 24, 2017 at 11:18
  • 5
    \$\begingroup\$ If you're going to sandbox something, leave it in there for more than two hours. \$\endgroup\$ Commented Jun 24, 2017 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\$ Commented Jun 24, 2017 at 13:05

45 Answers 45

Reset to default
1
2
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)
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Brachylog, 10 bytes

⟦bb{fkt}ᵐ+

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ You have clearly won this in all languages so far :)) \$\endgroup\$ Commented Jun 24, 2017 at 11:35
  • \$\begingroup\$ -2 \$\endgroup\$ Commented Oct 22, 2020 at 12:04
5
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 8 bytes \$\endgroup\$ Commented Jun 24, 2017 at 17:46
5
\$\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!

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ Funny, I just wrote basically the same code. \$\endgroup\$ Commented Jun 24, 2017 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\$ Commented Jun 24, 2017 at 16:22
  • \$\begingroup\$ This seems to be marginally faster than my approach. Mind if I edit that into my answer? \$\endgroup\$ Commented Jun 24, 2017 at 16:42
  • \$\begingroup\$ Please, go for it. \$\endgroup\$ Commented Jun 24, 2017 at 16:43
  • 1
    \$\begingroup\$ @Mr.Xcoder Not in PyPy, but yes, sieves do fine for this kind of problem. \$\endgroup\$ Commented Jun 24, 2017 at 17:20
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.
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Since f is a pure function, you can memoize it to run the larger cases on TIO \$\endgroup\$ Commented Jun 25, 2017 at 2:55
  • \$\begingroup\$ Right, not being able to use a decorator threw me off. Thanks! \$\endgroup\$ Commented Jun 25, 2017 at 3:06
5
\$\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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ -2 bytes: f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1) \$\endgroup\$ Commented Jun 24, 2017 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\$ Commented Jun 24, 2017 at 21:49
  • 1
    \$\begingroup\$ until saves some more: until((<1).mod n)pred(n-1)+f(n-1) \$\endgroup\$ Commented Jun 25, 2017 at 4:30
5
\$\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
Improve this answer
\$\endgroup\$
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
Improve this answer
\$\endgroup\$
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.

Improve this answer
\$\endgroup\$
2
  • \$\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\$ Commented Jun 24, 2017 at 13:27
  • \$\begingroup\$ @officialaimm It works for n=1000 if you use e.g. node --stack_size=8000. \$\endgroup\$ Commented Jun 24, 2017 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
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Mathematica, 30 bytes

Divisors[i][[-2]]~Sum~{i,2,#}&
Improve this answer
\$\endgroup\$
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
Improve this answer
\$\endgroup\$
4
  • \$\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\$ Commented Jun 24, 2017 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\$ Commented Jun 24, 2017 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\$ Commented Jun 24, 2017 at 15:58
  • \$\begingroup\$ @ETHproductions note that this is not the consensus anymore. Flags do not count towards the byte count. \$\endgroup\$ Commented Oct 29, 2023 at 19:45
3
\$\begingroup\$

PHP, 56 bytes

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

Try it online!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 36 30 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\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 ≤ a ≤ n, 2 ≤ b ≤ largest-proper-divisor(a)},

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

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

and using the inclusion–exclusion principle:

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

where

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

The sum has C⋅n 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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Oooh, that's fast... \$\endgroup\$ Commented Jun 25, 2017 at 7:37
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.
Improve this answer
\$\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.
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I know it's been about a year, but you can golf break to j=0. \$\endgroup\$ Commented Jun 20, 2018 at 9:18
  • \$\begingroup\$ @KevinCruijssen a very simple but effective trick. Nice idea! \$\endgroup\$ Commented Jun 20, 2018 at 9:22
2
\$\begingroup\$

Actually, 12 bytes

u2x⌠÷R1@E⌡MΣ

Try it online!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You're getting close to the first revision of my answer... you can check my editing history. \$\endgroup\$ Commented Jun 24, 2017 at 14:24
  • \$\begingroup\$ Oh, haha... I swear I did not steal it... :) \$\endgroup\$ Commented Jun 24, 2017 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.

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

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

Improve this answer
\$\endgroup\$
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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 1+1+2+1+3+1+4 = 13 not 8. Apart from that: great answer so +1. \$\endgroup\$ Commented Jun 26, 2017 at 8:53
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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Arturo, 32 bytes

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

Try it!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 18 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.