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

\$\endgroup\$
3
  • \$\begingroup\$ Sandbox. \$\endgroup\$
    – Mr. Xcoder
    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\$ 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\$
    – Mr. Xcoder
    Jun 24, 2017 at 13:05

38 Answers 38

1
2
1
\$\begingroup\$

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 .. $_
}
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 25 bytes

Lack of builtins is sad.

+/((⌈/∘⍸0=g|⊢)¨1+g←⍳1-⍨⊢)

Alternative dfn version: {+/{⌈/⍸0=⍵|⍨⍳1-⍨⍵}¨1+⍳1-⍨⍵}

Explanation:

+/((⌈/∘⍸0=g|⊢)¨1+g←⍳1-⍨⊢)
                 g←⍳1-⍨⊢   ⍝ numbers from 1 to ⍵-1 - define as `g`
               1+          ⍝ increment: numbers from 2 to ⍵.
              ¨            ⍝ for each of these...
        0=g|⊢              ⍝ mark evenly divisible indexes with 1
    ⌈/∘⍸                   ⍝ pick largest of proper divisors
+/                         ⍝ sum all

Try it online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 21 bytes

+/{*|&~(!x)!'x}'2_!1+

Try it online!

  • 2_!1+ generate integers in range 2..x
  • {*|&~(!x)!'x}' get largest divisor for each value in generated range
  • +/ take the sum
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 22 bytes

IL⪫E…·²N×⌈E…¹ι⎇﹪ιλ⁰λ1ω

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

      ²                 Literal 2
       N                Input number
    …·                  Inclusive range
   E                    Map with variable `i`
            ¹           Literal 1
             ι          Variable `i`
           …            Exclusive range
          E             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
 L                      Take the length
I                       Cast to string
                        Implicitly print

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

IΣE…·²N⌈E…¹ι⎇﹪ιλ⁰λ
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=max -p, 42 bytes

//,$\+=max grep$'%$_==0,1..$_-1for 2..$_}{

Try it online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.