Um divisor apropriado é um divisor de um número n , que não é n em si. Por exemplo, os divisores adequados de 12 são 1, 2, 3, 4 e 6.

Você receberá um número inteiro x , x ≥ 2, x ≤ 1000 . Sua tarefa é somar todos os divisores apropriados mais altos de números inteiros de 2 a x (inclusive) (OEIS A280050 ).

Exemplo (com x = 6):

• Encontre todos os números inteiros entre 2 e 6 (inclusive): 2,3,4,5,6.

• Obtenha os divisores adequados de todos eles e escolha os mais altos de cada número:

  • 2 -> 1
  • 3 -> 1
  • 4 -> 1, 2
  • 5 -> 1
  • 6 -> 1, 2, 3 .

• Resumir os mais altos divisores apropriados: 1 + 1 + 2 + 1 + 3 = 8.

• O resultado final é 8.

Casos de teste

Entrada | Saída
------- + ---------
       |
 2 1
 4 4
 6 8
 8 13
 15 41.
 37 229
 100 1690
 1000 165279

Regras

• Aplicam-se lacunas padrão .

• Você pode receber e fornecer saída por qualquer método padrão .

• Este é o código-golfe , o menor envio válido em cada idioma vence! Diverta-se!

Oásis , 4 bytes

Código:

nj+U

Experimente online!

Explicação:

Versão extendida:

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)

Casca , 7 bytes

ṁȯΠtptḣ

Experimente online!

Explicação

Husk não tem built-in para calcular os divisores diretamente (ainda), então estou usando a fatoração primária. O maior divisor próprio de um número é o produto de seus fatores primos, exceto o menor. Eu mapeio essa função no intervalo de 2 à entrada e soma os resultados.

ṁȯΠ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]

Isso é lento e nem consegue lidar com a entrada 15 no TIO.

Experimente online!

No entanto, a memorização ( obrigado @ musicman523 ) pode ser usada para verificar todos os casos de teste.

Experimente online!

Versão alternativa, 52 bytes

Ao custo de 2 bytes, podemos escolher entre calcular f(n,k+1)ou 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))

Com alguns truques, isso funciona para todos os casos de teste, mesmo no TIO.

Experimente online!

Gelatina , 6 bytes

ÆḌ€Ṫ€S

Experimente online!

Como funciona

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum

Braquilog , 10 bytes

⟦bb{fkt}ᵐ+

Experimente online!

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>

Um número é igual ao produto do seu maior divisor próprio e do menor fator primo.

05AB1E , 9 8 bytes

-1 Byte, graças ao truque principal de Leaky Nun em sua resposta Pyth

L¦vyÒ¦PO

Experimente online!

Explicação

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

Solução alternativa de 8 bytes (que não funciona no TIO)

L¦vyѨθO    

e ofc solução alternativa de 9 bytes (que funciona no TIO)

L¦vyѨ®èO    

Retina , 31 24 bytes

7 bytes graças a Martin Ender.

.+
$*
M!&`(1+)(?=\1+$)
1

Experimente online!

Como funciona

O regex /^(1+)\1+$/captura o maior divisor próprio de um determinado número representado em unário. No código, o \1+é transformado em uma sintaxe lookahead.

Mathematica, 30 bytes

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

Pitão , 13 9 8 bytes

1 byte graças ao jacoblaw.

tsm*FtPh

Conjunto de teste .

Como funciona

O maior divisor apropriado é o produto dos fatores primos, exceto o menor.

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)

Não é a resposta mais curta do Python, mas isso apenas passa pelos casos de teste. O TIO lida com entradas de até 30.000.000 sem suar a camisa; meu computador de mesa lida com 300.000.000 em um minuto.

Com o custo de 2 bytes , a condição n>dpode ser usada para uma aceleração de ~ 10%.

Agradecemos a @xnor pela r=[0]*nideia, que salvou 3 bytes!

Experimente online!

Haskell, 48 46 43 bytes

f 2=1
f n=until((<1).mod n)pred(n-1)+f(n-1)

Experimente online!

Edit: @rogaos salvou dois bytes. Obrigado!

Edite II: ... e @xnor mais 3 bytes.

Japt , 8 + 2 = 10 8 6 bytes

òâ1 xo

Teste-o

• 1 byte economizado graças à ETHproductions.

Explicação

    :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

MATL, 12 bytes

q:Q"@Z\l_)vs

Experimente no MATL Online

Explicação

        % 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

PHP , 56 bytes

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

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

Experimente online!

Cubix , 27 39 bytes

?%\(W!:.U0IU(;u;p+qu.@Op\;;

Experimente online!

Cubificado

      ? % \
      ( W !
      : . U
0 I U ( ; u ; p + q u .
@ O p \ ; ; . . . . . .
. . . . . . . . . . . .
      . . .
      . . .
      . . .

Assista

• 0IUConfigure a pilha com um acumulador e o número inteiro inicial. Inversão de marcha em U para o circuito externo
• :(? duplicar a parte superior atual da pilha, diminuir e testar
• \pO@ se o loop for zero ao redor do cubo em um espelho, pegue o fundo da pilha, produza e pare
• %\! se positivo, mod, relete e teste.
  • u;.W se for verdade, faça inversão de marcha, remova o resultado do mod e a faixa volte ao loop interno
  • U;p+qu;;\(se falsey, inversão de marcha, remova o resultado da modificação, coloque o acumulador no topo, adicione o divisor inteiro atual (superior) ao empurrão para baixo e inversão de marcha. Limpe a pilha para ter apenas o acumulador e o número inteiro atual, diminua o número inteiro e insira o loop externo novamente.

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

Experimente online!

• 2 bytes raspados graças a Kevin Cruijssen.

Na verdade , 12 bytes

u2x⌠÷R1@E⌡MΣ

Experimente online!

Python 3 , 78 75 73 71 bytes

Nem mesmo perto da resposta em python da freira Leaky na contagem de bytes.

f=lambda z:sum(max(i for i in range(1,y)if 1>y%i)for y in range(2,z+1))

Experimente online!

Python 3 , 69 63 59 bytes

4 bytes graças a Dennis.

f=lambda n:n-1and max(j for j in range(1,n)if n%j<1)+f(n-1)

Experimente online!

Defino o limite de recursão para 2000 para que isso funcione para 1000.

Carvão , 37 bytes

Ａ⁰βＦ…·²Ｎ«Ａ⟦⟧δＦ⮌…¹ι«¿¬﹪ικ⊞δκ»Ａ⁺β⌈δβ»Ｉβ

Experimente online!

O link é para a versão detalhada. Levei quase todo o dia para descobrir como resolver uma questão não relacionada à arte ASCII em Charcoal, mas finalmente entendi e tenho muito orgulho de mim. :-D

Sim, tenho certeza que isso pode ser muito praticado. Acabei de traduzir minha resposta em C # e tenho certeza de que as coisas podem ser feitas de maneira diferente no carvão vegetal. Pelo menos resolve o1000 caso em alguns segundos ...

Pari / GP , 36 30 bytes

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

Experimente online!

Python 2 (PyPy) , 145 bytes

Como transformar competições de código-golfe em competições de código mais rápido é divertido, aqui está um algoritmo O ( n ) que, no TIO, resolve n = 5.000.000.000 em 30 segundos. ( A peneira de Dennis é 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)

Experimente online!

Como funciona

Contamos o tamanho do conjunto

S = {( a , b ) | 2 ≤ a ≤ n , 2 ≤ b ≤ maior divisor próprio ( a )},

reescrevendo-a como a união, sobre todos os primos p ≤ √n, de

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

e usando o princípio de inclusão-exclusão :

| S | = ∑ (−1) ^{m - 1} | S _{p 1} ∩ ⋯ S _{p m} | acima de m ≥ 1 e inicia p ₁ <⋯ < p _m ≤ √n,

Onde

S _{p 1} ∩ _p S _{p m} = {( p ₁ ⋯ p _m ⋅ e , b ) | 1 ≤ e ≤ n / ( p ₁ ⋯ p _m ), 2 ≤ b ≤ p ₁ ⋯ p _{m - 1} e },
| S _{p 1} ∩ ⋯ S _{p m} | = ⌊ n / ( p ₁ ⋯ p _m ) ⌋⋅ ( p ₁ ⋯p _{m - 1} ⋅ (⌊ n / ( p ₁ ⋯ p _m ) ⌋ + 1) - 2) / 2.

A soma tem C ⋅ n termos diferentes de zero, onde C converge para alguma constante que é provavelmente 6 ⋅ (1 - ln 2) / π ² ≈ 0,186544. O resultado final é então | S | + n - 1.

NewStack , 5 bytes

Felizmente, na verdade há um embutido.

Nᵢ;qΣ

O colapso:

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.

Em inglês real:

Vamos executar um exemplo para uma entrada 8.

Nᵢ: Faça uma lista de números naturais de 1 a 8: 1, 2, 3, 4, 5, 6, 7, 8

;: Calcule os maiores fatores: 1, 1, 1, 2, 1, 3, 1, 4

q. Remova o primeiro elemento:1, 1, 2, 1, 3, 1, 4

ΣE pegue a soma: 1+1+2+1+3+1+4=13

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

Porto da resposta C # de @CarlosAlejo .

Experimente aqui.

Resposta antiga (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;}

Experimente aqui.

Explicação (da resposta antiga):

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

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)

Experimente online!

J , 18 bytes

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

Experimente online!

Empilhados , 31 bytes

[2\|>[divisors:pop\MAX]map sum]

Experimente online!(Todos os casos de teste, exceto 1000, que excedem o limite de tempo on-line de 60 segundos.)

Explicação

[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

C (gcc) , 53 bytes

x;s;f(n){for(s=0;n>1;--n){for(x=n;n%--x;);s+=x;}n=s;}

Experimente online!

Confortavelmente, passa rapidamente em todos os casos de teste.