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!

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

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!

Answer 3

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 4

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 5

Brachylog, 10 bytes

⟦bb{fkt}ᵐ+

Try it online!

Answer 6

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.

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.

Answer 8

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.

Answer 9

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

Answer 10

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

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!

Answer 13

Mathematica, 30 bytes

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

Answer 14

PHP, 56 bytes

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

Try it online!

Answer 15

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

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.

Answer 18

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 19

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.

Answer 20

Actually, 12 bytes

u2x⌠÷R1@E⌡MΣ

Try it online!

Answer 21

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!

Answer 22

Pari/GP, 36 30 bytes

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

Try it online!

Answer 23

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

Answer 24

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.

Answer 25

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

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

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 28

J, 18 bytes

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

Try it online!

Answer 29

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

Answer 30

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.

Answer 31

Perl 6, 36 bytes

{sum map {max grep $_%%*,^$_},2..$_}

Test it

Expanded:

{
  sum
    map
    {
      max
        grep
        $_ %% *, # is the input to this block divisible by
        ^$_      # Range of possible divisors
    },
    2 .. $_
}

Answer 32

Alice, 17 bytes

/o
\i@/&w!qB;?+]k

Try it online!

Explanation

This is a standard format for a program which takes input as an integer, outputs an integer, and does everything else in cardinal mode.

The program tries to add up the highest proper divisor of every number from 0 to n. In the case of 0 and 1, the number added comes from the implicit zeros on the stack, so we don't have to bother skipping these cases.

i    Take input string (in ordinal mode)
&w   Implicitly convert into an integer, and push a return address n times.
     This starts the main loop, which will run a total of n+1 times.
!    Store the accumulator on the current tape cell.
q    Get the tape position. (initially zero)
B    Compute all divisors.
;    Remove the top of the stack (the number itself).
?    Copy accumulator back from tape.
+    Add to greatest proper divisor.
]    Move tape right.
k    Return to pushed return address.  The (n+1)st time through this loop, 
     there is nowhere to return to, and the program continues.
o    Output the integer (as a string in ordinal mode).
@    Terminate.

Answer 33

Neim, 7 bytes

Γ)

Explanation:

Example input: 6
        Inclusive range [1 .. input]
         stack: [1 2 3 4 5 6]
 Γ       For each...
          Get factors
           stack: [[1] [1 2] [1 3] [1 2 4] [1 5] [1 2 3 6]]
          Remove last element
           stack: [[] [1] [1] [1 2] [1] [1 2 3]]
          Get greatest element
           stack: [0 1 1 2 1 3]
      )  End for each
        Sum.
         stack: [8]
Implicit output: 8

Try it!

Answer 34

Charcoal, 22 bytes

ＩＬ⪫Ｅ…·²Ｎ×⌈Ｅ…¹ι⎇﹪ιλ⁰λ1ω

Try it online! Link is to verbose version of code. Explanation:

      ²                 Literal 2
       Ｎ                Input number
    …·                  Inclusive range
   Ｅ                    Map with variable `i`
            ¹           Literal 1
             ι          Variable `i`
           …            Exclusive range
          Ｅ             Map with variable `l`
                ι       Variable `i`
                 λ      Variable `l`
               ﹪        Modulo
              ⎇         Ternary
                  ⁰     If nonzero then zero
                   λ    If zero then variable `l`
         ⌈              Take the maximum
                    1   Arbitrary character
        ×               Repeat it
  ⪫                  ω  Join the strings together
 Ｌ                      Take the length
Ｉ                       Cast to string
                        Implicitly print

The Sum function has been added since the question was asked, reducing the code to 18 bytes:

ＩΣＥ…·²Ｎ⌈Ｅ…¹ι⎇﹪ιλ⁰λ

Answer 35

R, 53 bytes

function(n){for(i in 2:n)F=F+(y=(i-1):1)[!i%%y][1]
F}

Try it online!

For each integer i in 2...n, computes the divisors of i in decreasing order with (y=(i-1):1)[!i%%y] and then selects the first, as that will be the largest, adding it to F, which is by default initialized to FALSE or 0.