Подсчитать суммы двух квадратов

45

Учитывая неотрицательное число n, выведите количество способов выразить nкак сумму двух квадратов целых чисел n == a^2 + b^2( OEIS A004018 ). Обратите внимание, что aи bможет быть положительным, отрицательным или нулевым, и их порядок имеет значение. Побеждает несколько байтов.

Например, n=25дает, 12потому что 25может быть выражен как

(5)^2  + (0)^2
(4)^2  + (3)^2
(3)^2  + (4)^2
(0)^2  + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2  + (-5)^2
(3)^2  + (-4)^2
(4)^2  + (-3)^2

Вот значения до n=25. Будьте осторожны, чтобы ваш код работал n=0.

0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12

Вот значения до n=100списка.

[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]

Забавные факты. Последовательность содержит произвольно высокие слагаемые, а предел ее скользящего среднего равен π.

Leaderboard:

Показать фрагмент кода

code-golf math combinatorics number-theory XNOR
источник
4
Чего ждать?? «Последовательность содержит произвольно высокие слагаемые, а предел ее скользящего среднего составляет π».
Стьюи Гриффин
@StewieGriffin Два утверждения согласуются. Рассмотрим последовательность 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Обрезая последовательность после любого ненулевого числа, среднее значение пока равно 1. И прогоны 0 оказывают все меньшее и меньшее влияние на последующую последовательность.
xnor
5
Я знаю, что это согласуется .. =) Я проверил первые 10.000 номеров, когда разместил комментарий. Чего я не понимаю, так это почему Пи?
Стьюи Гриффин
29
@StewieGriffin Сумма слагаемых до N соответствует точкам (a, b) с a ^ 2 + b ^ 2 <= N. Это точки решетки в окружности радиуса sqrt (N), площадь которых равна πN.
xnor
2
@xnor и там происходит волшебство :(
Андрас Дик

Ответы:

19

Python ( 59 57 56 байт)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Онлайн демо

Как и в моем ответе CJam, он использует инверсию Мёбиуса и работает в псевдоквазилинейном времени.

Спасибо Sp3000 за 2 байта экономии и feersum за 1.

Питер Тейлор
источник
1
Эти скобки раздражают.
Lirtosiast
@ThomasKwa, расскажи мне об этом. В одной из версий, которые я передал по пути к первой, которую я опубликовал, меня поразило то, что так было -1**xвсегда -1. Я ожидал, что -1это будет один целочисленный буквенный токен, а не унарный минус с низким приоритетом, за которым следует один.
Питер Тейлор
2
Поздравляю с наградой! Ваш код короче всего, что я придумал. Ваше решение основано на совершенно новой и неожиданной математической идее, и я радуюсь тому, что это возможно даже в такой простой задаче. Обратный результат Мёбиуса довольно симпатичен, и я с удовольствием получил доказательство для себя.
xnor
1 байт можно сохранить, переместив умножение на 4 после **x.
feersum
@PeterTaylor Можете ли вы рассказать, как работает ваш алгоритм / можете ли вы указать мне ресурс? Я не совсем понимаю, как можно применить инверсию Мёбиуса к числу сумм чисел Сукарес.
Flawr
15

Mathematica, 13 байт

Если встроенные модули разрешены, это как сделать это в Mathematica.

2~SquaresR~#&

Для 0 <= n <= 100

2~SquaresR~# & /@ Range[0, 100]

{1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0 , 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4 , 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8 , 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0 , 12}

DavidC
источник
1
Конечно, у Mathematica есть встроенная функция для этого.
HyperNeutrino
14

Python 2, 44 байта

f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2

Это почти то же самое, что и решение xsot (которое основано на решении Питера Тейлора ), но экономит 8 байтов, упрощая способ обработки знаков.

Обратите внимание, что для полной программы мы можем сохранить 2 байта в функции без дополнительных затрат:

f=lambda n,x=1:x>n or(n%x<1)-f(n,x+2)/4<<2
print+f(input())

Два дополнительных байта для полной программы таким образом:

n=input()
f=lambda x:x>n or(n%x<1)-f(x+2)/4<<2
print+f(1)

Для n > 0 существует очень разборчивое 40-байтовое решение:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Митч Шварц
источник
1
Поздравляю с победой! Рекурсивное вычитание - это чистый и короткий способ выразить знакопеременную сумму для нечетных делителей без необходимости извлекать знак из самого делителя. Также, спасибо xsot за упорядочение решения Питера Тейлора до рекурсивного с умной обработкой n = 0.
xnor
12

Pyth, 13 байт

/sM^^R2}_QQ2Q

Тестирование

/sM^^R2}_QQ2Q
                 Q = eval(input())
       }_QQ      Inclusive range from -Q to Q (all possible a and b)
    ^R2          Map to their squares
   ^       2     Form all pairs
 sM              Sum pairs
/           Q    Count occurances of Q
isaacg
источник
Поздно, но я не думаю, что тебе нужно последнее Q.
Эрик Outgolfer
12

J, 16 байт

+/@,@:=+&*:/~@i:

Это монадический глагол (другими словами, унарная функция). Попробуйте онлайн или посмотрите, пройдете ли вы все тесты .

объяснение

+/@,@:=+&*:/~@i:  Denote input by n
              i:  The array of integers from -n to n
           /~@    Take outer product wrt the following function:
       +           the sum of
        &*:        squares of both inputs
                  This results in a 2D array of a^2+b^2 for all a, b between -n and n
      =           Replace by 1 those entries that are equal to n, and others by 0
   ,@:            Flatten the binary matrix
+/@               Take its sum
Zgarb
источник
11

Python 2, 69 55 53 52 байта

f=lambda n,x=1:+(x>n)or(2-x%4)*(n%x<1)+f(n,x+2)/4<<2

Это рекурсивная функция, основанная на превосходном решении Питера Тейлора .

xsot
источник
1
Это большое улучшение. Но есть еще способ сделать его короче, и я призываю вас искать его.
xnor
1
@xnor Еще один байт вниз. Я надеюсь, что у тебя больше нет трюков в рукавах.
xsot
2
Я не знаю , должен ли я сделать ответ его, это только ваше решение плюс один трюк: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. Кроме того, я полагаю, нам не важно превышать максимальную глубину рекурсии по умолчанию?
Митч Шварц
1
@MitchSchwartz Я думаю, что это невероятное улучшение, достойное награды и, вероятно, окончательная оптимизация, которую имел в виду xnor.
xsot
1
@MitchSchwartz Да, это оптимизация, о которой я думал! И хитрость xsot /4<<2делает его короче, чем у меня.
xnor
8

Юлия, 40 байт

n->n>0?4sum(i->(n-i^2)^.5%1==0,1:n^.5):1

Ungolfed:

function f(n)
  if n==0
    return 1           # Handle special case of n=0
  else
    m=0                # Start the counter at zero
    for i=1:sqrt(n)    # Loop over the values (i) whose squares are
                       # less than n (except zero)
      k=sqrt(n-i^2)    # Find k such that n=k^2+i^2
      if k==floor(k)   # if k is an integer, we've found a pair
        m+=4           # Add one for each of k^2+i^2, (-k)^2+(-i)^2, and the other two
      end
    end
    return m           # Return the resulting count
  end
end

Обратите внимание, что цикл не включает в себя i==0, потому что когда nэто квадрат, он уже включен i=sqrt(n), и есть только четыре, а не восемь, для этой формы ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Глен О
источник
7

CJam, 25 23 байта

Zri:R#Ym*{Rf-Yf#:+R=},,

Это теоретическое решение, требующее O (9 н. ) и памяти для ввода n .

За счет одного дополнительного байта - всего 24 байта - мы можем уменьшить сложность до O (n 2 ) :

ri:R)Y*Ym*{Rf-Yf#:+R=},,

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

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

Или

Z                  Push 3.
 ri:R              Read an integer from STDIN and save it in R.
     #             Compute 3**R.

или

ri:R               Read an integer from STDIN and save it in R.
    )Y*            Add 1 and multiply by 2.

затем

Ym*                Take the second Cartesian power, i.e., compute all pairs.
   {          },   Filter the pairs:
    Rf-              Subtract R from each.
       Yf#           Square the differences.
          :+         Add the squares.
            R=       Compare with R.
                   If = pushed 1, keep the pair.
                ,  Count the kept pairs.
Деннис
источник
И при сохранении одного байта можно снизить сложность до Õ (n)
Питер Тейлор
Да я увидел. Это восхитительно.
Деннис
7

CJam ( 25 24 22 21 байт)

{:X!X{X\2*)%!4*\-}/z}

Онлайн демо

Это выполняется в псевдоквазилинейном времени * и использует утверждение OEIS, что

Преобразование Мебиуса представляет собой последовательность периода 4 [4, 0, -4, 0, ...]. - Майкл Сомос, 17 сентября 2007 г.

Вход 0 , очевидно, являются особым случаем (преобразования Мёбиуса и аннигиляторы не сочетаются друг с другом), но в итоге стоили всего один символ.

* Псевдо - потому что оно квазилинейно по значению ввода, а не по размеру ввода; квази, потому что он выполняет Theta(n)операции над целыми числами порядка n; bоперацию -битового мода следует принимать b lg bвремя, так что в целом это занимает Theta(n lg n lg lg n)время.

Питер Тейлор
источник
6

Japt , 42 37 33 байта

Japt - это сокращенная версия Ja vaScri pt . переводчик

V=Un oU+1;Vr@X+(Vf_p2 +Y*Y¥U)l ,0

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

           // Implicit: U = input number
V=Un oU+1  // Set variable V to range(-U, U+1). Ends up like [-U,-U+1,...,U-1,U]
Vr@    ,0  // Reduce each item Y in V with this function, starting at 0:
X+(     l  //  Return the previous value X + the length of:
Vf_p2      //   V filtered by items Z where Z*Z
+Y*Y==U)   //    + Y*Y equals U.
           // This ends up as the combined length of all fitting pairs of squares.
           // Implicit: return last expression

Возможно, есть лучшая техника; предложения приветствуются.

ETHproductions
источник
6

Python 3, 68 61 60 байт

lambda n:0**n+4*sum(i**.5%1+(n-i)**.5%1==0for i in range(n))

Использование двух вложенных списков слишком дорого. Вместо этого он проверяет, являются ли обе координаты на окружности радиуса sqrt (n) целыми числами.

Питер Тейлор победил это с помощью подхода, основанного на инверсии Мебиуса .

lirtosiast
источник
Отлично сработано. Я возился с рекурсивной функцией, но не мог решить n=0элегантно.
xsot
5

Октава, 28 байт

@(n)nnz((a=(-n:n).^2)'+a==n)
alephalpha
источник
5

Haskell, 42 байта

f n|q<-[-n..n]=sum[1|a<-q,b<-q,a*a+b*b==n]

Пример использования:

*Main> map f [0..25]
[1,4,4,0,4,8,0,0,4,4,8,0,0,8,0,0,4,8,4,0,8,0,0,0,0,12]
*Main>
Ними
источник
3
Привязка qв охране умная, я запомню этот трюк.
xnor
5

Юлия, 89 79 63 байта

g(x)=cos(π*x^.5)^2÷1
a(n)=(n==0)+4sum([g(i)g(n-i)for i=1:n])

Это именованная функция, aкоторая принимает целое число и возвращает число с плавающей точкой. Вызывает вспомогательную функцию g.

Ungolfed:

function g(x::Integer)
    floor(cos(π*sqrt(x))^2)
end

function a(n::Integer)
    (n == 0) + 4*sum([g(i)*g(n-i) for i=1:n])
end

Подход здесь использует упрощенную формулу Уэсли Ивана Херта, указанную в OEIS. Упрощение было найдено Гленом О, тем же человеком, который отбросил 26 байтов этого ответа!

Алекс А.
источник
Используйте, x^.5а не sqrt(x)сохранять 3 байта. И (n==0)сохраняет 2 байта 1÷(n+1). И вы можете сохранить еще 4 символа, используя cos(π*sqrt(x))^2÷1вместо floor(cos(π*sqrt(x))^2). Кроме того, используйте 1:n/2вместо 1:n÷2, потому что использование поплавка не повредит, g(x)и в iлюбом случае оно будет заблокировано целыми числами . И sum(i->g(i)g(n-i),1:n/2)побреет еще несколько персонажей тоже.
Глен О
@GlenO Отличные предложения, спасибо. sumТрюк не выполняется для n=0, поэтому я держал массив понимания.
Алекс А.
1
Таким образом, это может быть восстановлено - если вы позволите i=0делу случиться в сумме, вы можете включить знак 4g(n). Итак (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), что не встретится с ошибкой. Но вы можете сделать еще лучше, отметив симметрии -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Глен O
@GlenO Это упрощение серьезно гениально. Я рекомендую вам представить это в качестве альтернативной формулы для последовательности в OEIS!
Алекс А.
4

Pyth, 16 15 байт

lfqQs^R2T^}_QQ2

Попробуйте онлайн в компиляторе Pyth .

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

lfqQs^R2T^}_QQ2

          }_QQ   Compute the inclusive range from -Q to Q (input).
         ^    2  Take the second Cartesian power, i.e., compute all pairs.
 f               Filter; for each T in the list of pairs:
     ^R2T          Compute the squares of T's elements.
    s              Add the squares.
  qQ               Compare the sum with Q.
                 If q returned True, keep T.
l                Count the kept pairs.
Деннис
источник
4

TI-BASIC, 23 байта

sum(seq(Σ(X²+Y²=Ans,X,-Ans,Ans),Y,-Ans,Ans

Довольно просто. Σ(это суммирование.

Странно, sum(seq(sum(seq(бросает ERR:ILLEGAL NEST, и так делает Σ(Σ(, но sum(seq(Σ(это хорошо. Я решил положить Σ(внутрь, чтобы спасти близкого человека.

lirtosiast
источник
Какая разница между sumа Σ?
алефальфа
1
@alephalpha Σ (принимает суммирование, суммируя все X²+Y²=Ansзначения from из X между -Ansи Ans. sum (является суммой списка , поэтому нам нужно сначала создать список, используя seq (..., Y, -Ans, Ans
Lirtosiast
4

JavaScript (ES6), 66 60 байт

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

6 байтов сохранено благодаря @ edc65 !

объяснение

n=>eval(`              // use eval to allow for loops in an unparenthesised arrow function
  for(r=0,             // r = number of pairs
    a=~n;a++<n;        // a = first number to square
  )
      for(b=~n;b++<n;) // b = second number to square
        r+=a*a+b*b==n  // add one to the result if a^2 + b^2 == n
                       // implicit: return r
`)

Тест

n = <input type="number" oninput='result.innerHTML=(

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

)(+this.value)' /><pre id="result"></pre>
Развернуть фрагмент

user81655
источник
1
60:n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
edc65
@ edc65 Отлично! Я не думал об использовании, evalчтобы поместить forциклы в функцию стрелки без скобок. Я тоже забыл про ~оператора хаха.
user81655 26.11.15
4

Python 3, 93 62 69 байт

Itertools не работал, поэтому я снова использовал два диапазона, но переместил диапазон, чтобы сохранить байты.

Изменить: предыдущий код на самом деле не работал, так как я определил диапазон по n, прежде чем я определил n.

lambda n:sum(i*i+j*j==n for i in range(-n,n+1)for j in range(-n,n+1))
Sherlock9
источник
2

APL, 23 20 19 байт

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}

Объяснение:

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}        Monadic function:
                 ⍳⍵          1 2 3 ... ⍵
               ,⍨            Duplicate
             0,              Concatenate to 0
          ×⍨                 Square everything
      ∘.+⍨                   Make an addition table
     ∊                       Flatten
   ⍵=                        1s where equal to the input
 +/                          Sum up the 1s

Помимо того факта, что в APL нет функции J i:(числа от -n до n), это работает во многом как ответ J.

Мы не можем использовать поезд, потому что получение, -\⍳2×⍵чтобы не анализировать (-\) ⍳ (2×⍵), стоило бы три байта; аналогично с другой парой топов. Все эти скобки делают обычную функцию короче.

Попробуй это здесь . Вывод 1означает, что все значения совпадают.

lirtosiast
источник
2

Matlab 41 байт

Еще меньше, чем предыдущие ответы

@(n)nnz(~mod(sqrt(n-(1:n^.5).^2),1))*4+~n

По сути, ответ Agawa001 с заменой мощности и площади

Jonas
источник
2

Candy , 17 14 байтов

Первоначально вход помещен в стек

~TbAT1C(sWs+Aeh)Z

~T0C(sWs+Aeh)Z

peekA    # copy arg from stack to register A
range2   # create double sided range on stack, -A, 1-A, ... A-1, A
digit0   # prefix argument to 'cart', 
cart     # cartesian product of current stack(0), and other stack(0)
while    # while stack not empty
  sqr    # pop and square and push
  swap   # swap two stack elements
  sqr    # pop and square and push
  add    # pop and pop and add and push
  pushA  # push original argument
  equal  # equality test 0/1
  popAddZ  # Z := Z + pop
endwhile
pushZ    # push Z onto stack, will be output to stdout on termination
Дейл Джонсон
источник
2

CJam, 28

qi_mF{3a>},{~)\4%2-&}%4+:*1?

Не очень короткий, но эффективный. Например, результат для 15625 мгновенно равен 28. Использует формулу на основе факторизации из OEIS.
Попробуйте онлайн

Объяснение:

qi       read input and convert to integer
_        make a copy (will be used to handle the 0 case at the end)
mF       factorize into [prime exponent] pairs
{…},     filter the array of pairs
  3a>    with the condition that the pair is greater than [3]
          which means the prime factor must be ⩾3
{…}%     transform each pair as follows:
  ~      dump the prime factor and exponent onto the stack
  )      increment the exponent
  \      swap with the prime
  4%     get the remainder mod 4 (it will be 1 or 3)
  2-     subtract 2 (resulting in -1 or 1)
  &      bitwise AND with the incremented exponent (see below)
4+       append a 4 to the array
:*       multiply all
1?       if the input was 0, use 1, else use the above result

Некоторые подробности о расчете:

  • если простое число 1 мод 4, код рассчитывает (exponent + 1) & -1 , чтоexponent + 1
  • если простое число равно 3 mod 4, вычисляется код (exponent + 1) & 1, который равен 0, если показатель степени нечетный, и 1, если четный

Все эти значения, умноженные вместе и умноженные на 4, являются в точности формулой OEIS.

aditsu
источник
2

Python 2, 68 байт

def x(n):r=range(-n,n+1);print sum(a*a+b*b==n for a in r for b in r)

Определяет вызываемую функцию, x()которая принимает число n.

Попробуйте онлайн. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
источник
Вы пропустите printили returnзаявление.
Згарб
Спасибо, я полностью забыл. Ссылка имеет оператор печати, хотя. Я редактировал свой код, пока я делал код.
2012 г.
Хорошо, не волнуйтесь. Но это также, кажется, дает неправильные результаты для n=0и n=1(0 и 2 вместо 1 и 4). Может быть, ограничения диапазона требуют корректировки?
Згарб
@Zgarb Да, они должны закончиться на n+1.
Lirtosiast
1
Я поищу это.
Rɪᴋᴇʀ
2

Pyth, 41 35 33 30 27 байт

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

Редактировать: Благодаря isaacg , я получил mи *Fна работу! ДА!

?Q*F+4m.&tt%ed4hhdr-PQ2 8 1
                                (implicit) Q = input()
?Q                              If Q != 0
      m                           Map to d (exponent, prime) from ...
                  r-PQ2 8         run-length-encoded(PQ with 2's removed)
       .&                           Bitwise and
           %ed4                       d[-1] % 4
         tt                           -2
                hd                  with d[0]
               h                      +1
    +4                            Append 4 to the resulting array
  *F                              Then multiply it all together
                          1     Else 1

Редактировать: положить побитовый и обратно для большей экономии байтов! Также я удалил все "Бывшие" вещи. Это начало становиться загроможденным.

Благодаря aditsu и его решению CJam, и maltysen и его советам (Однажды я доберусь m*Fdдо работы. Однажды ...)

J4Vr-PQ2 8=J*J.&tt%eN4hhN;?QJ1
                                (implicit) Q=input()
J4                              J=4
    -PQ2                        Remove all 2's from the prime factorization of Q
   r     8                      run-length encode (exponent, prime factor)
  V                      ;      For N in range( the above ):
          =J*J                      J = J * ...
                tt%eN4                N[-1] mod 4 -2 
                      hhN             (exponent + 1)
              .&                    bitwise and
                          ?QJ1  if Q != 0 print(J) else print(1)

Обратите внимание, что,

  • если простое число 1 мод 4, мы получаем -1 & (exponent + 1), чтоexponent + 1

  • но если простое число 3 mod 4, мы получаем 1 & (exponent + 1), что 0если показатель степени нечетен, и 1если четный

Умножим все это вместе (4 раза в начале), и мы получим количество сумм двух квадратов, которые складываются с нашим вводом.

Sherlock9
источник
2

Python, 57 байт

Хороший вызов. К сожалению, я не получаю это короче, чем это в данный момент.

lambda n:0**n+sum(2-d%4for d in range(1,n+1)if d%2>n%d)*4
Willem
источник
2

PARI / GP, 34 28 байт

Использование генерирующих функций:

Сохранено 6 байтов благодаря Митчу Шварцу .

n->sum(i=-n,n,x^i^2)^2\x^n%x

Используя встроенные модули, 33 байта (сэкономил 1 байт благодаря Митчу Шварцу .):

n->if(n,2*qfrep(matid(2),n)[n],1)

qfrep (q, B, {flag = 0}): вектор (половины) числа векторов норм от 1 до B для целочисленной и определенной квадратичной формы q. Если флаг равен 1, считать векторы четной нормы от 1 до 2В.

alephalpha
источник
matid(2)сохраняет байт.
Митч Шварц
1
И до 28 для подхода производящей функции:n->sum(i=-n,n,x^i^2)^2\x^n%x
Митч Шварц
1

Matlab, 72 байта

n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))
Луис Мендо
источник
Вам не нужно dispв этом вызове, Луис! =)
Стьюи Гриффин
@ StewieGriffin Спасибо! Но в данном случае это программа, а не функция. Так что согласно принятому ответу в вашей ссылке это нужно, не так ли?
Луис Мендо
1

Matlab, 63 50 байт

@(y)nnz(~mod(sqrt(y-power((1:sqrt(y)),2)),1))*4+~y

  • Это превосходит другой код с таким же названием, поэтому я поставил его: D.

  • Программа находит положительные целочисленные решения, затем умножают на 4, чтобы охватить отрицательные.

  • Он может выполнить все 25 первых тестов

    for i=1:25 ans(i)
end

   1

   4

   4

   0

   4

   8

   0

   0

   4

   4

   8

   0

   0

   8

   0

   0

   4

   8

   4

   0

   8

   0

   0

   0

   0

   12
Abr001am
источник
Вам не нужно dispв этом вызове ! =)
Стьюи Гриффин
спасибо @StewieGriffin, я включил его просто как честную игру, относящуюся к игре luis '
Abr001am
Советы: Когда вы планируете опубликовать результаты в MATLAB, используйте format compact=)
Stewie Griffin
1

JavaScript, 89 байт

n=prompt()
p=Math.pow
for (x=c=(+n?0:1);x<=n;x++)if(x&&p(n-p(x,2),.5)%1===0)c+=4
alert(c)

Я знаю, что это не самый короткий ответ JavaScript, даже если бы мне пришлось удалить строки ввода / вывода, но я действительно думаю, что это самый эффективный ответ JS, дающий мне результат за миллион в течение нескольких секунд (десять миллионов заняли около минуты).

Адам Далли
источник
Можете ли вы использовать == вместо ===?
Lirtosiast
Я мог бы, просто используя лучшие практики, ха-ха.
Адам Дэлли
1

PHP, 70 байт, не конкурирует

for($x=-1;$x++<=$n=$argv[1];)$s+=(-($n%($x-~$x)<1))**$x*4;echo$n?$s:1;

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

Titus
источник
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;экономит 5 байт. $x-~$xравно, 2*$x+1и теперь вы можете начать без назначения переменной.
Йорг Хюльсерманн