Суммируйте силы, которые будут

35

Простая, но, надеюсь, не совсем тривиальная задача:

Напишите программу или функцию, которая суммирует числа, kразделяющие число n. Более конкретно:

  • Входные данные: два натуральных числа nи k(или упорядоченная пара целых чисел и т. Д.)
  • Вывод: сумма всех положительных делителей nэтих kстепеней целых чисел

Например, 11! = 39916800 имеет шесть делителей , которые являются кубами, а именно : 1, 8, 27, 64, 216 и 1728. Таким образом , данные входов 39916800и 3, программа должна вернуть их сумму, 2044.

Другие тестовые случаи:

{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

Это код гольф, поэтому чем короче ваш код, тем лучше. Я приветствую гольф-код на всех языках, даже если какой-то другой язык может обходиться меньшим количеством байтов, чем ваш.

Грег Мартин
источник
12
Когда я впервые увидел твой вызов, у меня было странное чувство, что это название песни Metallica.
Арно
1
Какая? Для этого нет встроенного Mathematica?
boboquack

Ответы:

13

05AB1E , 9 байтов

DLImDŠÖÏO

Попробуйте онлайн!

объяснение

Пример ввода 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
источник
6

Mathematica, 28 байт

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

Безымянная функция принимает nи в kкачестве входных данных в этом порядке.

Мартин Эндер
источник
2
DivisorSumразочаровывающе близко к тому, чтобы быть полезным здесь.
ngenisis
5

Haskell , 37 35 34 байта

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

Попробуйте онлайн! Использование:

Prelude> 40320 ! 1
159120

Код довольно неэффективен, потому что он всегда вычисляет 1^k, 2^k, ..., n^k.

Изменить: Сохраненный один байт благодаря Zgarb.

Объяснение:

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
источник
1
mod n(x^k)может быть n`mod`x^k.
Згарб
5

Python 2, 54 52 байта

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

Спасибо @Rod за сокращение 2 байта.

hashcode55
источник
Вы можете заменить x%i**n==0с x%i**n<1, и перейти на другую сторону,i**n*(x%i**n<1)
Rod
4

Рубин, 45 байт

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

Короче было бы использовать "сумму" в Ruby 2.4. Время обновить?

гигабайт
источник
4
Время обновить.
Yytsi
4

MATL , 10 байт

t:i^\~5M*s

Попробуйте онлайн!

Как это работает

Пример с 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
Луис Мендо
источник
4

Желе , 7 6 байт

-1 байт благодаря Деннису (обходить неявный диапазон)
. Умное сохранение эффективности также Деннисом при стоимости 0 байт
(ранее ÆDf*€Sфильтр фильтровал бы те делители, которые являются степенью k любого натурального числа, до n . Но обратите внимание, что n может только когда-либо есть делитель i k, если он все равно имеет делитель i !)

ÆDf*¥S

Попробуйте онлайн!

Как?

Æ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
Джонатан Аллан
источник
3

JavaScript (ES7), 56 53 байта

Берет nи kв карри синтаксис (n)(k).

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

Контрольные примеры

Arnauld
источник
3

Perl 6 , 39 байт

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

Как это работает

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

Попытайся

SMLS
источник
2

Japt , 10 байт

Сохранено много байтов благодаря @ETHproductions

òpV f!vU x

объяснение

ò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

Проверьте это онлайн!

Оливер
источник
vUОбнаруживает ли числа, делимые на U, или числа, которые делятся U?
Грег Мартин
@GregMartin fvUфильтрует элементы, которые делятся на U; f!vUфильтрует элементы, которые Uделятся на. !меняет аргументы.
Оливер
Круто, так что код выглядит правильно, но объяснение может потребоваться изменить.
Грег Мартин
@GregMartin Теперь должно быть понятнее.
ETHproductions
2

Scala 63 байта

(n:Int,k:Int)=>1 to n map{Math.pow(_,k).toInt}filter{n%_==0}sum
jaxad0127
источник
2

Python 2 , 50 байт

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

Попробуйте онлайн! Большие входные данные могут превышать глубину рекурсии в зависимости от вашей системы и реализации.

XNOR
источник
2

JavaScript (ES7), 49 46 байт

n=>g=(k,t=i=0,p=++i**k)=>p>n?t:g(k,t+p*!(n%p))
Нил
источник
Так как вы не повторяете, почему бы и нет n=>k=>? +1.
Yytsi
@TuukkaX Я придумал что-то лучше. (Я действительно имел это ранее iкак локальный, который стоит 4 дополнительных байта, и забыл, что я мог злоупотреблять так iже, как я делал с моей другой формулировкой.)
Нейл
1

PHP, 86 байт

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

Попробуй это здесь!

Сломать :

$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
источник
игра в гольф, но не проверена: for(;$x<$n=$argv[1];)$n%($x=++$i**$argv[2])?:$s+=$x;echo$s;59 байт; требует PHP 5.6 или выше.
Титус
1

CJam , 20 байтов

Вероятно, не оптимально в гольфе, но я не вижу каких-либо очевидных изменений, чтобы сделать ...

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

Попробуйте онлайн!

Бизнес Кот
источник
1

Утилиты Bash + Unix, 44 байта

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

Попробуйте онлайн!

Тестовые прогоны:

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
Митчелл Спектор
источник
1

Python , 56 байт

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

Попробуйте онлайн!

Довольно просто. Единственное, что заслуживает внимания, это то, что j**k**-1%1всегда возвращает число с плавающей запятой в [0,1), а n%jвсегда возвращает неотрицательное целое число, поэтому они могут быть равны, только если оба равны 0 .

Деннис
источник
1

Пакет, 138 байт

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

Так как Batch не имеет оператора питания, я злоупотребляю set/aкак форма eval. Очень медленно, когда k=1. 32-разрядная целочисленная арифметика ограничивает поддерживаемые значения nи 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
Нил
источник
0

R, 28 байтов прямой, 43 байта для функции

если n, k в памяти:

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

для функции:

r=function(n,k)sum((n%%(1:n)^k==0)*(1:n)^k)
Захиро Мор
источник