Сколько способов записать числа в виде сумм квадратов?

12

задача

Даны два целых числа dи n, найти количество способов выразить nкак сумму dквадратов. То есть n == r_1 ^2 + r_2 ^2 + ... + r_d ^2такое, что r_mявляется целым числом для всех целых чисел 1 ≤ m ≤ d. Обратите внимание, что обмен двух разных значений (например, r_1и r_2) считается отличным от исходного решения.

Например, число 45 может быть записано как сумма 2 квадратов 8 различными способами:

45
== (-6)^2 + (-3)^2
== (-6)^2 + 3^2
== (-3)^2 + (-6)^2
== (-3)^2 + 6^2
== 3^2 + (-6)^2
== 3^2 + 6^2
== 6^2 + (-3)^2
== 6^2 + 3^2

правила

  • Встроенные решения разрешены, но не конкурируют (например, Mathematica )
  • Стандартные лазейки также запрещены.
  • Входы могут быть обратными.

Пример ввода / вывода

In:   d, n

In:   1, 0
Out:  1

In:   1, 2
Out:  0

In:   2, 2
Out:  4

In:   2, 45
Out:  8

In:   3, 17
Out:  48

In:   4, 1000
Out:  3744

In:   5, 404
Out:  71440

In:   11, 20
Out:  7217144

In:   22, 333
Out:  1357996551483704981475000

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

code-golf number number-theory combinatorics Юнг Хван Мин
источник
Почему вы удалили это и опубликовали новое, когда можете редактировать удаленное сообщение?
Дрянная Монахиня
@LeakyNun Мой браузер выдавал ошибки, когда я пытался редактировать это, даже прежде, чем удалить его.
JungHwan Мин.
Связанные
Луис Мендо
1
Нет, n равно 0, а не d.
Утренняя монахиня
1
@DeadPossum Для 1, 0теста, есть 1способ выразить 0в виде суммы 1квадрата: 0 == 0^2.
JungHwan Мин.

Ответы:

7

Python 3 , 125 байт

n,d=eval(input())
W=[1]+[0]*n
exec("W=[sum(-~(j>0)*W[i-j*j]for j in range(int(i**.5)+1))for i in range(n+1)];"*d)
print(W[n])

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

Завершает последний тестовый случай за 0,078 с. Наивная сложность O ( d n 2 ).

Дрянная Монахиня
источник
5

Mathematica, 8 байтов, не конкурирует

SquaresR
alephalpha
источник
3
Как будто это было даже необходимо ... не добавляет ничего нового к вопросу. : P
Эрик Outgolfer
@EriktheOutgolfer Вини вопрос; в нем прямо говорится, что это разрешено.
JollyJoker
Те моменты, когда не встроенные решения почти
Дэвид Малдер
@JollyJoker Я хочу сказать, что ответы должны что-то добавить к вопросу, иначе зачем их публиковать? *
пожимает
@DavidMulder Я сначала пропустил «почти» и был немного шокирован ...
Эрик Outgolfer
5

Желе , 9 байт

Nr⁸²ṗS€ċ⁸

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

Берет nи dв таком порядке.

Эрик Outgolfer
источник
Сколько лет потребуется для последнего теста?
Утренняя монахиня
@ LeakyNun Я не знаю, это за пределами моего понимания ...
Эрик Outgolfer
4

MATL , 13 байт

y_t_&:Z^U!s=s

Входы есть n, тогда d. В некоторых тестовых случаях не хватает памяти.

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

объяснение

Рассмотрим входы 17, 3.

y     % Implicit inputs. Duplicate from below
      % STACK: 17, 3, 17
_     % Negate
      % STACK: 17, 3, -17
t_    % Duplicate. Negate
      % STACK: 17, 3, -17, 17
&:    % Two-input range
      % STACK: 17, 3, [-17 -16 ... 17]
Z^    % Cartesian power. Gives a matrix where each Cartesian tuple is a row
      % STACK: 17, [-17 -17 -17; -17 -17 -16; ...; 17 17 17]
U     % Square, element-wise
      % STACK: 17, [289 289 289; 289 289 256; ...; 289 289 289]
!s    % Transpose. Sum of each column
      % STACK: 17, [867 834 ... 867]
=     % Equals?, element-wise
      % STACK: 17, [0 0 ... 0] (there are 48 entries equal to 1 in between)
s     % Sum. Implicit display
      % STACK: 48
Луис Мендо
источник
3

Haskell , 43 байта

0#0=1
d#n=sum[(d-1)#(n-k*k)|d>0,k<-[-n..n]]

Просто ваша основная рекурсия. Определяет двоичную инфиксную функцию #.Попробуйте онлайн!

объяснение

0#0=1            -- If n == d == 0, give 1.
d#n=             -- Otherwise,
 sum[            -- give the sum of
  (d-1)#(n-k*k)  -- these numbers
  |d>0,          -- where d is positive
   k<-[-n..n]]   -- and k is between -n and n.

Если d == 0и n /= 0, мы во втором случае, и условие d>0заставляет список быть пустым. Сумма пустого списка равна 0, что является правильным выводом в этом случае.

Zgarb
источник
2

05AB1E , 10 байтов

Ð(Ÿ²ã€nOQO

Принимает аргументы как n, а затем d. Есть проблемы с решением больших тестовых случаев.

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

объяснение

Ð(Ÿ²ã€nOQO   Arguments n, d
Ð            Triplicate n on stack
 (           Negate n
  Ÿ          Range: [-n ... n]
   ²ã        Caertesian product of length d
     €n      Square each number
       OQ    Sum of pair equals n
         O   Total sum (number of ones)
kalsowerus
источник
2

Mathematica, 38 байт

Count[Tr/@Tuples[Range[-#,#]^2,#2],#]&

Чистая функция принимает входные данные в порядке n, d. Range[-#,#]^2дает набор всех возможных релевантных квадратов с положительными квадратами, перечисленными дважды, чтобы сделать счет правильным; Tuples[...,#2]создает dкортежи таких квадратов; Tr/@суммирует каждый dнабор; иCount[...,#] считает, сколько результатов равно n.

Первые несколько тестовых случаев быстро заканчиваются, но я полагаю, что для выполнения тестового примера потребуется около полугода 1000,4. Замена Range[-#,#]на (более длинное, но) более разумное Range[-Floor@Sqrt@#,Floor@Sqrt@#]ускоряет это вычисление примерно до 13 секунд.

Грег Мартин
источник
1

Mathematica, 53 51 байт

SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&
alephalpha
источник
1

Python 2, 138

Очень неэффективное решение с моим любимым eval. Почему нет?
Попробуйте онлайн

lambda n,d:d and 4*eval(eval("('len({('+'i%s,'*d+'0)'+'for i%s in range(n)'*d+'if '+'i%s**2+'*d+'0==n})')%"+`tuple(range(d)*3)`),locals())

Он генерирует и оценивает код следующим образом:

len({(i0,i1,0)for i0 in range(n)for i1 in range(n)if i0**2+i1**2+0==n})

Поэтому для некоторого большого d он будет работать очень долго и занимать много памяти, имея сложность O (n ^ d)

Мертвый Опоссум
источник