Suma mocy, które są

35

Proste, ale miejmy nadzieję, nie całkiem trywialne wyzwanie:

Napisz program lub funkcję, która sumuje kpotęgę dzielącą liczbę n. Dokładniej:

  • Dane wejściowe: dwie dodatnie liczby całkowite ni k(lub uporządkowana para liczb całkowitych itp.)
  • Wyjście: suma wszystkich dodatnich dzielników ntego są kpotęgami liczb całkowitych

Na przykład 11! = 39916800 ma sześć dzielniki które są kostki, mianowicie 1, 8, 27, 64, 216 i 1728 W związku z danymi wyjściowymi 39916800i 3program powinien zwracać Sum 2044.

Inne przypadki testowe:

{40320, 1} -> 159120
{40320, 2} -> 850
{40320, 3} -> 73
{40320, 4} -> 17
{40320, 5} -> 33
{40320, 6} -> 65
{40320, 7} -> 129
{40320, 8} -> 1
{46656, 1} -> 138811
{46656, 2} -> 69700
{46656, 3} -> 55261
{46656, 4} -> 1394
{46656, 5} -> 8052
{46656, 6} -> 47450
{46656, 7} -> 1
{1, [any positive integer]} -> 1

To jest golf golfowy, więc im krótszy kod, tym lepiej. Z zadowoleniem przyjmuję kod do gry w golfa we wszystkich różnych językach, nawet jeśli jakiś inny język może uciec z mniejszą liczbą bajtów niż twój.

Greg Martin
źródło
12
Kiedy po raz pierwszy zobaczyłem twoje wyzwanie, miałem dziwne wrażenie, że to tytuł piosenki Metalliki.
Arnauld,
1
Co? Nie ma do tego wbudowanej Mathematiki?
Boboback

Odpowiedzi:

13

05AB1E , 9 bajtów

DLImDŠÖÏO

Wypróbuj online!

Wyjaśnienie

Przykładowe dane wejściowe 46656, 3

D          # duplicate first input
           # STACK: 46656, 46656
 L         # range [1 ... first input]
           # STACK: 46656, [1 ... 46656]
  Im       # each to the power of second input
           # STACK: 46656, [1, 8, 27 ...]
    D      # duplicate
           # STACK: 46656, [1, 8, 27 ...], [1, 8, 27 ...]
     Š     # move down 2 spots on the stack
           # STACK: [1, 8, 27 ...], 46656, [1, 8, 27 ...]
      Ö    # a mod b == 0
           # STACK: [1, 8, 27 ...], [1,1,1,1,0 ...]
       Ï   # keep only items from first list which are true in second
           # STACK: [1, 8, 27, 64, 216, 729, 1728, 5832, 46656]
        O  # sum
           # OUTPUT: 55261
Emigna
źródło
6

Mathematica, 28 bajtów

Tr[Divisors@#⋂Range@#^#2]&

Pobieranie nienazwanej funkcji ni kjako dane wejściowe w tej kolejności.

Martin Ender
źródło
2
DivisorSumjest frustrująco bliski przydatności w tym przypadku.
ngenisis,
5

Haskell , 37 35 34 bajtów

n!k=sum[x^k|x<-[1..n],n`mod`x^k<1]

Wypróbuj online! Stosowanie:

Prelude> 40320 ! 1
159120

Kod jest dość nieefektywny, ponieważ zawsze się oblicza 1^k, 2^k, ..., n^k.

Edycja: Zapisano jeden bajt dzięki Zgarbowi.

Wyjaśnienie:

n!k=             -- given n and k, the function ! returns
 sum[x^k|        -- the sum of the list of all x^k
   x<-[1..n],    -- where x is drawn from the range 1 to n
   n`mod`x^k<1]  -- and n modulus x^k is less than 1, that is x^k divides n
Laikoni
źródło
1
mod n(x^k)może być n`mod`x^k.
Zgarb,
5

Python 2, 54 52 bajty

lambda x,n:sum(i**n*(x%i**n<1)for i in range(1,-~x))

Dzięki @Rod za odcięcie 2 bajtów.

hashcode55
źródło
Można wymienić x%i**n==0z x%i**n<1, i przejść na drugą stronę, jaki**n*(x%i**n<1)
Rod
4

Rubinowy, 45 bajtów

->n,m{(1..n).reduce{|a,b|n%(c=b**m)<1?a+c:a}}

Byłoby krótsze przy użyciu „sum” w Ruby 2.4. Czas na aktualizację?

GB
źródło
4
Czas na aktualizację.
Yytsi,
4

MATL , 10 bajtów

t:i^\~5M*s

Wypróbuj online!

Jak to działa

Przykład z 46656, 6.

t      % Implicitly input n. Duplicate
       % STACK: 46656, 46656
:      % Range
       % STACK: 46656, [1 2 ... 46656]
i      % Input k
       % STACK: 46656, [1 2 ... 46656], 6
^      % Power, element-wise
       % STACK: 46656, [1 64 ... 46656^6]
\      % Modulo
       % STACK: [0 0 0 1600 ...]
~      % Logically negate
       % STACK: [true true true false ...]
5M     % Push second input to function \ again
       % STACK: [true true true false ...], [1^6 2^6 ... 46656^6]
*      % Multiply, element-wise
       % STACK: [1 64 729 0 ...]
s      % Sum of array: 47450
       % Implicitly display
Luis Mendo
źródło
4

Galaretka , 7 6 bajtów

-1 bajt dzięki Dennisowi (przemieść ukryty zakres)
Sprytna efektywność oszczędzana również przez Dennisa przy koszcie 0 bajtów
(Wcześniej ÆDf*€Sfiltrowałby te dzielniki, które są potęgą k dowolnej liczby naturalnej do n . Ale zauważ, że n może tylko dzielnik i k tylko wtedy, gdy ma dzielnik i !)

ÆDf*¥S

Wypróbuj online!

W jaki sposób?

ÆDf*¥S - Main link: n, k
ÆD     - divisors of n  -> divisors = [1, d1, d2, ..., n]
    ¥  - last two links as a dyadic chain
  f    -     filter divisors keeping those that appear in:
   *   -     exponentiate k with base divisors (vectorises)
       - i.e. [v for v in [1, d1, d2, ..., n] if v in [1^k, d1^k, ..., n^k]]
     S - sum
Jonathan Allan
źródło
3

JavaScript (ES7), 56 53 bajtów

Trwa ni kw currying składni (n)(k).

n=>k=>[...Array(n)].reduce(p=>n%(a=++i**k)?p:p+a,i=0)

Przypadki testowe

Arnauld
źródło
3

Perl 6 , 39 bajtów

->\n,\k{sum grep n%%*,({++$**k}...*>n)}

Jak to działa

->\n,\k{                              }  # A lambda taking two arguments.
                        ++$              # Increment an anonymous counter
                           **k           # and raise it to the power k,
                       {      }...       # generate a list by repeatedly doing that,
                                  *>n    # until we reach a value greater than n.
            grep n%%*,(              )   # Filter factors of n from the list.
        sum                              # Return their sum.

Spróbuj

smls
źródło
2

Japt , 10 bajtów

Zaoszczędzono wiele bajtów dzięki produktom @ETH

òpV f!vU x

Wyjaśnienie

òpV f!vU x
ò           // Creates a range from 0 to U
 pV         // Raises each item to the power of V (Second input)
    f       // Selects all items Z where
     !vU    //   U is divisible by Z
            //   (fvU would mean Z is divisible by U; ! swaps the arguments)
         x  // Returns the sum of all remaining items

Przetestuj online!

Oliver
źródło
Czy vUwykrywa liczby podzielne przez Ulub liczby dzielące U?
Greg Martin
@GregMartin fvUfiltruje do elementów, które można podzielić U; f!vUfiltry do elementów, które Umożna podzielić. !zamienia argumenty.
Oliver,
Fajnie, więc kod wygląda poprawnie, ale wyjaśnienie może wymagać poprawienia.
Greg Martin
@GregMartin Teraz powinno być jaśniej.
ETHprodukcje
2

Scala 63 bajty

(n:Int,k:Int)=>1 to n map{Math.pow(_,k).toInt}filter{n%_==0}sum
jaxad0127
źródło
2

Python 2 , 50 bajtów

f=lambda n,k,i=1:n/i and(n%i**k<1)*i**k+f(n,k,i+1)

Wypróbuj online! Duże nakłady mogą przekraczać głębokość rekurencji w zależności od systemu i implementacji.

xnor
źródło
2

JavaScript (ES7), 49 46 bajtów

n=>g=(k,t=i=0,p=++i**k)=>p>n?t:g(k,t+p*!(n%p))
Neil
źródło
Skoro nie rekursujesz, dlaczego nie n=>k=>? +1.
Yytsi
@TuukkaX Wymyśliłem coś lepszego. (Właściwie miałem to wcześniej ijako lokalny, który kosztuje 4 dodatkowe bajty, i zapomniałem, że mogę nadużywać iw taki sam sposób, jak to robiłem z moim innym sformułowaniem.)
Neil
1

PHP, 86 bajtów

$n=$argv[1];$k=$argv[2];for($i=1;$i<=$n**(1/$k);$i++)if($n%$i**$k<1)$s+=$i**$k;echo$s;

Wypróbuj tutaj!

Awaria :

$n=$argv[1];$k=$argv[2];       # Assign variables from input
for($i=1;$i<=$n**(1/$k);$i++)  # While i is between 1 AND kth root of n
    if($n%$i**$k<1)            #     if i^k is a divisor of n
        $s+=$i**$k;            #         then add to s
echo$s;                        # echo s (duh!)
roberto06
źródło
grał w golfa, ale nie testowano: for(;$x<$n=$argv[1];)$n%($x=++$i**$argv[2])?:$s+=$x;echo$s;59 bajtów; wymaga PHP 5.6 lub nowszego.
Tytus
1

CJam , 20 bajtów

Prawdopodobnie nie jest optymalnie golfowy, ale nie widzę żadnych oczywistych zmian, aby wprowadzić ...

ri:N,:)rif#{N\%!},:+

Wypróbuj online!

Business Cat
źródło
1

Narzędzia Bash + Unix, 44 bajty

bc<<<`seq "-fx=%.f^$2;s+=($1%%x==0)*x;" $1`s

Wypróbuj online!

Przebiegi testowe:

for x in '40320 1' '40320 2' '40320 3' '40320 4' '40320 5' '40320 6' '40320 7' '40320 8' '46656 1' '46656 2' '46656 3' '46656 4' '46656 5' '46656 6' '46656 7' '1 1' '1 2' '1 3' '1 12' ; do echo -n "$x "; ./sumpowerdivisors $x; done

40320 1 159120
40320 2 850
40320 3 73
40320 4 17
40320 5 33
40320 6 65
40320 7 129
40320 8 1
46656 1 138811
46656 2 69700
46656 3 55261
46656 4 1394
46656 5 8052
46656 6 47450
46656 7 1
1 1 1
1 2 1
1 3 1
1 12 1
Mitchell Spector
źródło
1

Python , 56 bajtów

lambda n,k:sum(j*(j**k**-1%1==n%j)for j in range(1,n+1))

Wypróbuj online!

Dość bezpośredni. Jedyną godną uwagi rzeczą jest to, że j**k**-1%1zawsze zwraca liczbę zmiennoprzecinkową w [0,1), a n%jzawsze zwraca nieujemną liczbę całkowitą, więc mogą być równe tylko wtedy, gdy oba są równe 0 .

Dennis
źródło
1

Partia, 138 bajtów

@set s=n
@for /l %%i in (2,1,%2)do @call set s=%%s%%*n
@set/at=n=0
:l
@set/an+=1,p=%s%,t+=p*!(%1%%p)
@if %p% lss %1 goto l
@echo %t%

Ponieważ Batch nie ma operatora mocy, nadużywam set/ajako formy eval. Bardzo wolno kiedy k=1. 32-bitowa arytmetyka liczb całkowitych ogranicza obsługiwane wartości ni k:

           n   k
  (too slow)   1
 <1366041600   2
 <1833767424   3
 <2019963136   4
 <2073071593   5
 <1838265625   6
 <1801088541   7
 <1475789056   8
 <1000000000   9
 <1073741824  10
 <1977326743  11
  <244140625  12
 <1220703125  13
  <268435456  14
 <1073741824  15
   <43046721  16
  <129140163  17
  <387420489  18
 <1162261467  19
    <1048576  20
           ...
 <1073741824  30
Neil
źródło
0

R, 28 bajtów bezpośrednio, 43 bajty na funkcję

jeśli n, k w pamięci:

sum((n%%(1:n)^k==0)*(1:n)^k)

dla funkcji:

r=function(n,k)sum((n%%(1:n)^k==0)*(1:n)^k)
Zahiro Mor
źródło