Właściwe połączenie dzielnika

20

Właściwa dzielnik jest dzielnikiem z szeregu N , które nie są n siebie. Na przykład odpowiednimi dzielnikami 12 są 1, 2, 3, 4 i 6.

Otrzymasz liczbę całkowitą x , x ≥ 2, x ≤ 1000 . Twoim zadaniem jest zsumowanie wszystkich najwyższych właściwych dzielników liczb całkowitych od 2 do x (włącznie) (OEIS A280050 ).

Przykład (z x = 6):

  • Znajdź wszystkie liczby całkowite od 2 do 6 (włącznie): 2,3,4,5,6.

  • Zdobądź odpowiednie dzielniki wszystkich i wybierz najwyższe z każdej liczby:

    • 2 -> 1
    • 3 -> 1
    • 4 -> 1, 2
    • 5 -> 1
    • 6 -> 1, 2, 3 .
  • Podsumowując najwyższe odpowiednie dzielniki: 1 + 1 + 2 + 1 + 3 = 8.

  • Ostateczny wynik to 8.

Przypadki testowe

Wejście | Wynik
------- + ---------
       |
 2 | 1
 4 | 4
 6 | 8
 8 | 13
 15 | 41
 37 | 229
 100 | 1690
 1000 | 165279

Zasady

Pan Xcoder
źródło
Piaskownica.
Pan Xcoder
5
Jeśli zamierzasz coś w piaskownicy, zostaw to na dłużej niż dwie godziny.
Peter Taylor
@PeterTaylor Piaskowiłem post tylko po to, by otrzymać informację zwrotną, ponieważ jest to bardzo proste wyzwanie, którego zwykle nie publikowałem w piaskownicy. BTW dzięki za edycję.
Pan Xcoder

Odpowiedzi:

13

Oaza , 4 bajty

Kod:

nj+U

Wypróbuj online!

Wyjaśnienie:

Rozszerzona wersja:

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)
Adnan
źródło
5

Łuska , 7 bajtów

ṁȯΠtptḣ

Wypróbuj online!

Wyjaśnienie

Husk nie ma wbudowanego (jeszcze) obliczania dzielników bezpośrednio, więc zamiast tego używam faktoryzacji pierwotnej. Największy właściwy dzielnik liczby jest iloczynem jego głównych czynników, z wyjątkiem najmniejszego. Mapuję tę funkcję w zakresie od 2 do danych wejściowych i sumuję wyniki.

ṁȯΠ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.
Zgarb
źródło
5

Python 2 , 50 bajtów

f=lambda n,k=2:n/k and(f(n,k+1),n/k+f(n-1))[n%k<1]

Jest to powolne i nawet nie radzi sobie z wejściem 15 na TIO.

Wypróbuj online!

Jednak do weryfikacji wszystkich przypadków testowych można wykorzystać notatkę ( dzięki @ musicman523 ).

Wypróbuj online!

Alternatywna wersja, 52 bajty

Kosztem 2 bajtów możemy wybrać, czy obliczyć, f(n,k+1)czy 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))

Z pewnymi podstępami działa to dla wszystkich przypadków testowych, nawet w TIO.

Wypróbuj online!

Dennis
źródło
Ponieważ fjest to czysta funkcja , możesz ją zapamiętać, aby uruchamiać większe skrzynki na TIO
musicman523
Racja, brak możliwości korzystania z dekoratora mnie wyrzucił. Dzięki!
Dennis
4

Galaretka , 6 bajtów

ÆḌ€Ṫ€S

Wypróbuj online!

Jak to działa

ÆḌ€Ṫ€S
ÆḌ€    map proper divisor (1 would become empty array)
           implicitly turns argument into 1-indexed range
   Ṫ€  map last element
     S sum
Leaky Nun
źródło
4

JavaScript (ES6), 40 bajtów

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>

Liczba równa się iloczynowi jej najwyższego właściwego dzielnika i najmniejszego czynnika pierwszego.

Neil
źródło
przepełnienie stosu dla n>352(przynajmniej w tym fragmencie, nie wiem, czy jest to zależność mojej przeglądarki / maszyny), podczas gdy powinieneś wspierać przynajmniej upto n=1000.
officialaimm
@officialaimm Działa, n=1000jeśli używasz np node --stack_size=8000.
Neil
4

05AB1E , 9 8 bajtów

-1 dzięki Byte do nieszczelnego Nun „s czynnik pierwszy trik w swoim Pyth odpowiedź

L¦vyÒ¦PO

Wypróbuj online!

Wyjaśnienie

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

Alternatywne rozwiązanie 8-bajtowe (to nie działa na TIO)

L¦vyѨθO    

i ofc alternatywne rozwiązanie 9-bajtowe (które działa na TIO)

L¦vyѨ®èO    
Datboi
źródło
4

Retina , 31 24 bajtów

7 bajtów dzięki Martinowi Enderowi.

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

Wypróbuj online!

Jak to działa

Wyrażenie regularne /^(1+)\1+$/przechwytuje największy właściwy dzielnik o określonej liczbie reprezentowany w jedności. W kodzie \1+zmieniono na składnię lookahead.

Leaky Nun
źródło
4

Mathematica, 30 bajtów

Divisors[i][[-2]]~Sum~{i,2,#}&
J42161217
źródło
4

Pyth , 13 9 8 bajtów

1 bajt dzięki Jacoblaw.

tsm*FtPh

Zestaw testowy .

Jak to działa

Największy właściwy dzielnik jest iloczynem czynników pierwszych, z wyjątkiem najmniejszego.

Leaky Nun
źródło
8 bajtów
jacoblaw
4

Python 2 (PyPy) , 73 71 70 bajtów

n=input();r=[0]*n;d=1
while n:n-=1;r[d+d::d]=n/d*[d];d+=1
print sum(r)

Nie jest to najkrótsza odpowiedź w języku Python, ale po prostu przegląda przypadki testowe. TIO obsługuje wejścia do 30 000 000 bez zerwania potu; mój komputer stacjonarny obsługuje 300 000 000 minut.

Kosztem 2 bajtów warunek n>dmoże być wykorzystany do przyspieszenia o ~ 10%.

Dzięki @xnor za r=[0]*npomysł, który oszczędził 3 bajty!

Wypróbuj online!

Dennis
źródło
Zabawne, właśnie napisałem w zasadzie ten sam kod .
xnor
l=[0]*npowinien pozwolić ci się pozbyć -2. exectrochę zabija prędkość, ale nawet whilepętla byłaby krótsza niż moje podejście.
Dennis
To wydaje się być nieco szybsze niż moje podejście. Masz coś przeciwko, jeśli zmienię to w mojej odpowiedzi?
Dennis
Proszę, idź po to.
xnor
1
@ Mr.Xcoder Nie w PyPy, ale tak, sita dobrze sobie radzą z tego rodzaju problemami.
Dennis
4

Haskell, 48 46 43 bajtów

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

Wypróbuj online!

Edycja: @rogaos zapisał dwa bajty. Dzięki!

Edytuj II: ... i @xnor kolejne 3 bajty.

nimi
źródło
-2 bajty:f 2=1 f n=last[d|d<-[1..n-1],mod n d<1]+f(n-1)
vroomfondel
@rogaos: Dzięki! Sam spróbowałem jawnej rekursji, ale jej nie usunąłem sum, więc pomyślałem, że nie jest krótsza.
nimi
1
untiloszczędza trochę więcej:until((<1).mod n)pred(n-1)+f(n-1)
xnor
4

Japt , 8 + 2 = 10 8 6 bajtów

òâ1 xo

Sprawdź to

  • 1 bajt zaoszczędzony dzięki produktom ETH.

Wyjaśnienie

    :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
Kudłaty
źródło
Zauważ, że -xliczy się jako dwa bajty zgodnie z tym postem . Myślę jednak, że można zapisać bajt za pomocą ò2_â1 o( âwyklucza oryginalny numer, gdy podano argument)
ETHproductions
Dzięki, @ETHproductions; Brakowało mi obu tych rzeczy. Zastanawiam się, czy to działa z mocą wsteczną na wszystkie rozwiązania, w których liczymy flagi jako 1 bajt? Pracowałem nad alternatywnym rozwiązaniem, które i tak nie korzystało z flagi; wskazanie âargumentu przyniosło mi oszczędności, których szukałem.
Kudłaty
Zakładam, że tak, ponieważ tak naprawdę wcześniej nie dochodziliśmy do konsensusu. BTW, grałem z õ Åprzed i znalazłem parę 8- i 9-byters: õ Åx_/k g, õ Åx_k Å×, õ Åx_â¬o. I łącząc õi Åze swoim genius xosztuczki znalazłem rozwiązanie 7-bajtowy :-)
ETHproductions
3

MATL, 12 bajtów

q:Q"@Z\l_)vs

Wypróbuj w MATL Online

Wyjaśnienie

        % 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
Suever
źródło
3

Cubix , 27 39 bajtów

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

Wypróbuj online!

Cubified

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

Watch It Run

  • 0IUUstaw stos z akumulatorem i początkową liczbą całkowitą. Zawracanie w zewnętrzną pętlę
  • :(? zduplikuj bieżącą górę stosu, zmniejszenie i test
  • \pO@ jeśli zero pętli wokół sześcianu do lustra, złap dno stosu, wyjście i zatrzymaj
  • %\! jeśli pozytywne, mod, relect i test.
    • u;.W jeśli to prawda, należy zawracać, usuwać wynik mod i zmienić pas z powrotem w wewnętrzną pętlę
    • U;p+qu;;\(jeśli falsey, zawracanie, usuń wynik mod, przenieś akumulator na górę, dodaj bieżącą liczbę całkowitą (górną) wciśnij do dołu i zawróć. Oczyść stos, aby mieć tylko akumulator i bieżącą liczbę całkowitą, zmniejsz liczbę całkowitą i ponownie wejdź do zewnętrznej pętli.
MickyT
źródło
3

C # (.NET Core) , 74 72 bajty

n=>{int r=0,j;for(;n>1;n--)for(j=n;--j>0;)if(n%j<1){r+=j;j=0;}return r;}

Wypróbuj online!

  • Ogolono 2 bajty dzięki Kevinowi Cruijssenowi.
Charlie
źródło
1
Wiem, że minął już rok, ale możesz grać breakw golfa j=0.
Kevin Cruijssen
@KevinCruijssen to bardzo prosta, ale skuteczna sztuczka. Dobry pomysł!
Charlie,
2

Python 3 , 78 75 73 71 bajtów

Nawet w pobliżu pythonowej nieszczelnej odpowiedzi zakonnicy w liczbie bajtów.

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

Wypróbuj online!

Officialaimm
źródło
1
Zbliżasz się do pierwszej wersji mojej odpowiedzi ... możesz sprawdzić moją historię edycji.
Leaky Nun
Och, haha ​​... Przysięgam, że go nie ukradłem ... :)
officialaimm
2

Python 3 , 69 63 59 bajtów

4 bajty dzięki Dennisowi.

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

Wypróbuj online!

Ustawiłem limit rekurencji na 2000, aby działało to dla 1000.

Leaky Nun
źródło
+1 Masz moje punkty brownie! Oto rozwiązanie, o którym mówiłem, mówiąc „mniej niż 70 bajtów” ...
Pan Xcoder
Działa to również w Pythonie 2
Pan Xcoder
2

Węgiel drzewny , 37 bajtów

A⁰βF…·²N«A⟦⟧δF⮌…¹ι«¿¬﹪ικ⊞δκ»A⁺β⌈δβ»Iβ

Wypróbuj online!

Link jest do pełnej wersji. Prawie cały dzień zajęło mi ustalenie, w jaki sposób mogę rozwiązać pytanie niezwiązane ze sztuką ASCII w Charcoal, ale w końcu je zrozumiałem i jestem z niego bardzo dumny. :-RE

Tak, jestem pewien, że można w to dużo grać w golfa. Właśnie przetłumaczyłem moją odpowiedź w języku C # i jestem pewien, że w Charcoal można to zrobić inaczej. Przynajmniej rozwiązuje 1000sprawę w ciągu kilku sekund ...

Charlie
źródło
2

Python 2 (PyPy) , 145 bajtów

Ponieważ przekształcanie zawodów w golfa w zawody z najszybszym kodem jest fajne, oto algorytm O ( n ), który w TIO rozwiązuje n = 5 000 000 000 w 30 sekund. ( Sito Dennisa to 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)

Wypróbuj online!

Jak to działa

Liczymy rozmiar zestawu

S = {( a , b ) | 2 ≤ an , 2 ≤ b ≤ największy dzielnik właściwy ( a )},

przepisując go jako sumę, dla wszystkich liczb pierwszych p ≤ √n, z

S p = {( pd , b ) | 2 ≤ dn / p , 2 ≤ bd },

i stosując zasadę włączenia / wyłączenia :

| S | = ∑ (−1) m - 1 | S p 1 ∩ ⋯ ∩ S p m | powyżej m ≥ 1 i liczb pierwszych p 1 <⋯ < p m ≤ √n,

gdzie

S p 1 ∩ ⋯ ∩ S p m = {( p 1p me , b ) | 1 ≤ en / ( p 1p m ), 2 ≤ bp 1p m - 1 e },
| S p 1 ∩ ⋯ ∩ S p m | = ⌊ n / ( p 1p m ) ⌋⋅ ( p 1p m - 1 ⋅ (⌊ n / ( p 1p m ) ⌋ + 1) - 2) / 2.

Suma ma Cn niezerowe warunki, gdzie C jest zbieżne do pewnej stałej, która prawdopodobnie wynosi 6⋅ (1 - 1 n 2) / π 2 ≈ 0,186544. Ostateczny wynik to | S | + n - 1.

Anders Kaseorg
źródło
Oooh, to szybko ...
Pan Xcoder,
2

NewStack , 5 bajtów

Na szczęście w rzeczywistości jest wbudowany.

Nᵢ;qΣ

Podział:

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.

W aktualnym języku angielskim:

Uruchommy przykład dla danych wejściowych 8.

Nᵢ: Zrób listę liczb naturalnych od 1 do 8: 1, 2, 3, 4, 5, 6, 7, 8

;: Oblicz największe czynniki: 1, 1, 1, 2, 1, 3, 1, 4

q. Usuń pierwszy element:1, 1, 2, 1, 3, 1, 4

ΣI weź sumę: 1+1+2+1+3+1+4=13

Grawiton
źródło
1+1+2+1+3+1+4= 13nie 8. Poza tym: świetna odpowiedź, więc +1.
Kevin Cruijssen
@KevinCruijssen Ups, dzięki za złapanie tego!
Graviton
2

Java 8, 78 74 72 bajty

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 odpowiedzi C # @CarlosAlejo .

Wypróbuj tutaj.

Stara odpowiedź (78 bajtów):

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

Wypróbuj tutaj.

Objaśnienie (starej odpowiedzi):

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
Kevin Cruijssen
źródło
1

Ułożone , 31 bajtów

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

Wypróbuj online! (Wszystkie przypadki testowe z wyjątkiem 1000, które przekraczają 60-sekundowy limit czasu online).

Wyjaśnienie

[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
Conor O'Brien
źródło