Квадратные числа - это те, которые принимают форму n^2целого числа n. Их также называют идеальными квадратами, потому что когда вы берете их квадратный корень, вы получаете целое число.

Первые 10 квадратных чисел: ( OEIS )

0, 1, 4, 9, 16, 25, 36, 49, 64, 81

Треугольные числа - это числа, которые могут образовывать равносторонний треугольник. Номер n-го треугольника равен сумме всех натуральных чисел от 1 до n.

Первые 10 треугольных чисел: ( OEIS )

0, 1, 3, 6, 10, 15, 21, 28, 36, 45

Квадратные треугольные числа являются числами, которые являются и квадратными и треугольными.

Первые 10 квадратных треугольных чисел: ( OEIS )

0, 1, 36, 1225, 41616, 1413721, 48024900, 1631432881, 55420693056, 1882672131025, 63955431761796

Существует бесконечное количество квадратных чисел, треугольных чисел и квадратных треугольных чисел.

Напишите программу или именованную функцию, которая задает входной (параметр или стандартный номер) номер n, вычисляет nквадратное треугольное число th и выводит / возвращает его, где n - положительное ненулевое число. (Для n = 1 вернуть 0)

Чтобы программа / функция была действительной отправкой, она должна иметь возможность возвращать как минимум все квадратные треугольные числа, меньшие 2 ^ 31-1.

бонус

-4 байта для возможности вывести все квадратные треугольные числа менее 2 ^ 63-1

-4 байта для теоретической возможности вывести квадратные треугольные числа любого размера.

Штраф + 8 байт за решения, которые занимают неполиномиальное время.

Стек бонусов.

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

CJam, 12 8 байт

XUri{_34*@-Y+}*;

Использует рекуррентное отношение из статьи Википедии.

Код длиной 16 байт соответствует обоим бонусам.

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

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

Мой код оказался идентичным кснуру во всех аспектах, за исключением того, что я использую стек CJam вместо переменных.

XU               e# Push 1 and 0 on the stack.
                 e# Since 34 * 0 - 1 + 2 = 1, this compensates for 1-based indexing.
  ri{        }*  e# Do int(input()) times:
     _34*        e#   Copy the topmost integer and multiply it by 34.
         @-      e#   Subtract the bottommost integer from the result.
           Y+    e#   Add 2.
               ; e# Discard the last result.

Python 2, 45 - 4 - 4 = 37

a=1;b=0
exec"a,b=b,34*b-a+2;"*input()
print a

Итерации с использованием рекурсии

f(0) = 1
f(1) = 0
f(k) = 34*f(k-1)-f(k-2)+2

Теоретически, это поддерживает числа любого размера, но работает в экспоненциальном времени, поэтому оно не должно претендовать на бонусы. Должно работать на номера любого размера. Например, за 100, дает

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

В рекурсивном решении используется 41 символ, но он не должен соответствовать требованиям, поскольку он занимает экспоненциальное время.

f=lambda k:k>2and 34*f(k-1)-f(k-2)+2or~-k

Pyth, 16 - 4 - 4 = 8 байт

Использует рекурсивную формулу из статьи OEIS.

K1uhh-*34G~KGtQZ

Он использует команду post-assign, которая довольно нова и выглядит действительно крутой. Использование сокращает n-1время итерации из-за индексации на основе 1.

K1            Set K=1
u       tQ    Reduce input()-1 times
         Z    With zero as base case
 hh            +2
  -           Subtract
   *34G       34 times iterating variable
   ~K         Assign to K and use old value
    G         Assign the iterating variable.

Кажется, полиномиальный, потому что он повторяется n раз и выполняет математику и присваивание каждой итерации, но я не ученый. Заканчивается n = 10000 практически мгновенно.

Попробуйте здесь онлайн .

Оазис , 7 - 4 - 4 = -1 (неконкурирующий)

34*c-»T

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

Пользы a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2

Oasis поддерживает произвольные целочисленные значения точности, поэтому он должен иметь возможность доходить до любого числа, если не происходит переполнение стека. Дайте мне знать, если это не считается бонусом из-за переполнения стека. Также возможно, что этот конкретный алгоритм является неполиномиальным, и дайте мне знать, если это так.

Не конкурирует, потому что языковые постдаты бросают вызов.

Объяснение:

34*c-»T -> 34*c-»10

a(0) = 0
a(1) = 1
a(n) = 34*c-»

34*c-»
34*    # 34*a(n-1)
   c-  # 34*a(n-1)-a(n-2)
     » # 34*a(n-1)-a(n-2)+2

Альтернативное решение:

-35*d+T

Вместо этого использует a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)

JavaScript (ES6), 29-4 = 25 байт

n=>n>1?34*f(n-1)-f(n-2)+2:n|0

Сохранено 5 байт благодаря @IsmaelMiguel !

Мне пришлось жестко кодировать 0, 1 и негативы, чтобы избежать бесконечной рекурсии.

Консоль, я назвал функцию f:

f(1);  // 0
f(13); // 73804512832419600
f(30); // 7.885505171090779e+42 or 7885505171090779000000000000000000000000000

РЕДАКТИРОВАТЬ : Оказывается, JavaScript округляет числа до 16 (15) цифр (Spec), потому что эти числа слишком велики, вызывая переполнение. Поместите 714341252076979033 в консоль JavaScript и убедитесь сами. Это скорее ограничение JavaScript

Excel VBA - 90 байт

Используя рекуррентное отношение со страницы Википедии:

n = InputBox("n")
x = 0
y = 1
For i = 1 To n
Cells(i, 1) = x
r = 34 * y - x + 2
x = y
y = r
Next i

При выполнении вам будет предложено ввести n, затем последовательность до n включительно выводится в столбец A:

Его можно запустить до n = 202 включительно, прежде чем он выдаст ошибку переполнения.

[Не конкурирует] Pyth (14 - 4 - 4 = 6 байт)

K1u/^tG2~KGQ36

Использовали первое повторение из OEIS , что после 0,1,36 можно найти A _n = (A _n-1 -1) ² / A _n-2 . A Не конкурирует, потому что это решение начинается с 36, если вы идете ниже, вы делитесь на ноль (поэтому ввод 0 дает 36). Также пришлось жестко закодировать 36.

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

Java, 53 - 4 = 49 байт

Это еще одна простая рекурсия, но я не часто публикую Java с оценкой <50, так что ...

long g(int n){return n<2?n<1?1:0:34*g(n-1)-g(n-2)+2;}

Теперь, для чего - то не -recursive, он получает совсем немного дольше. Этот и более длинный (112-4 = 108), и медленнее, поэтому я не уверен, почему я публикую его, за исключением того, что нужно что-то итеративное:

long f(int n){long a=0,b,c,d=0;for(;a<1l<<32&n>0;)if((c=(int)Math.sqrt(b=(a*a+a++)/2))*c==b){d=b;n--;}return d;}

Юля, 51 байт - 4 - 4 = 43

f(n)=(a=b=big(1);b-=1;for i=1:n a,b=b,34b-a+2end;a)

При этом используется первое отношение повторения, указанное на странице Википедии для квадратных треугольных чисел. Он вычисляет n = 1000 за 0,006 секунды и n = 100000 за 6,93 секунды. Это на несколько байтов длиннее рекурсивного решения, но это намного быстрее.

Ungolfed + объяснение:

function f(n)
    # Set a and b to be big integers
    a = big(1)
    b = big(0)

    # Iterate n times
    for i = 1:n
        # Use the recurrence relation, Luke
        a, b = b, 34*b - a + 2
    end

    # Return a
    a
end

Примеры:

julia> for i = 1:4 println(f(i)) end
0
1
36
1225

julia> @time for i = 1:1000 println(f(i)) end
0
... (further printing omitted here)
elapsed time: 1.137734341 seconds (403573226 bytes allocated, 38.75% gc time)

PHP, 65 59, 56-4 = 52 байта

while($argv[1]--)while((0|$r=sqrt($s+=$f++))-$r);echo$s;

повторять до тех пор, пока корень квадратный из $sis ∈ℤ: прибавить $fк сумме $s, увеличить $f;
повторить $argv[1]раз.
выходная сумма.

Пролог, 70 74 - 4 - 4 = 66

n(X,R):-n(X,0,1,R).
n(X,A,B,R):-X=0,R=A;Z is X-1,E is 34*B-A+2,n(Z,B,E,R).

Запуск n(100,R)выходов:

X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496

Требуется около 1 секунды для запуска n(10000,X)на моем компьютере.

Изменить : версия 66 является хвостовой рекурсии. Предыдущая нерекурсивная версия выглядит следующим образом:

n(X,[Z|R]):-X>1,Y is X-1,n(Y,R),R=[A,B|_],Z is 34*A-B+2;X=1,Z=1,R=[0];Z=0.

Они имеют одинаковую длину в байтах, но нерекурсивный генерирует переполнение стека после определенной точки (на моем компьютере около 20500).

Javascript ES6, 77 75 71 символов

// 71 chars
f=n=>{for(q=t=w=0;n;++q)for(s=q*q;t<=s;t+=++w)s==t&&--n&console.log(s)}

// No multiplication, 75 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2)for(;t<=s;t+=++w)s==t&&--n&console.log(s)}

// Old, 77 chars
f=n=>{for(s=t=w=0,q=-1;n;s+=q+=2){for(;t<s;t+=++w);s==t&&--n&console.log(s)}}

• Решение является линейным.
• Решение может вывести все числа меньше 2 ^ 53 из-за типа чисел.
• Сам алгоритм может быть использован для неограниченного числа.

Тест:

f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796

C 68 байтов

Это было забавное испытание с C

main(o,k){o==1?k=0:0;k<9e9&&k>=0&&main(34*o-k+2,o,printf("%d,",k));}

Смотреть его можно здесь: https://ideone.com/0ulGmM

Желе , 13 - 8 = 5 байт

Это соответствует обоим бонусам.

×8‘,µÆ²Ạ
0Ç#Ṫ

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

Совершено рядом с пирамидой в чате .

объяснение

× 8 ', µÆ²Ạ ~ Вспомогательная ссылка.

× 8 ~ 8 раз больше.
  '~ Увеличение.
   , ~ В паре с текущим номером.
    µ ~ Запускает новую монадическую (1-arg) ссылку.
     Ʋ ~ Векторизация "Квадрат?"
       All ~ все. Возвращайте 1, только если оба являются правдивыми.



0Ç # Ṫ ~ Главная ссылка.

0 # ~ Начиная с 0, соберите первые N целых чисел с достоверными результатами, когда они применяются:
 The ~ Последняя ссылка как монада.
   Last ~ Последний элемент. Вывод неявно.

Perl 6 , 25 - 8 = 17 байт

{(0,1,2-*+34* *…*)[$_]}

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

05AB1E , 10 - 8 = 2 байта

1ÎGDŠ34*Ìα

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

APL (NARS), 67 символов, 134 байта

r←f w;c;i;m
c←0⋄i←¯1⋄r←⍬
→2×⍳0≠1∣√1+8×m←i×i+←1⋄r←r,m⋄→2×⍳w>c+←1

тест:

  f 10
0 1 36 1225 41616 1413721 48024900 1631432881 55420693056 1882672131025 

f будет искать в квадратичной последовательности элементы, которые тоже имеют номер треугольника, поэтому они должны следовать формуле проверки треугольника в APL: 0 = 1∣√1 + 8 × m с номером m для проверки.