Les nombres carrés sont ceux qui prennent la forme n^2où n est un entier. Ils sont également appelés carrés parfaits, car lorsque vous prenez leur racine carrée, vous obtenez un entier.

Les 10 premiers nombres carrés sont: ( OEIS )

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

Les nombres triangulaires sont des nombres qui peuvent former un triangle équilatéral. Le n-ème nombre de triangle est égal à la somme de tous les nombres naturels de 1 à n.

Les 10 premiers nombres triangulaires sont: ( OEIS )

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

Les nombres triangulaires carrés sont des nombres à la fois carrés et triangulaires.

Les 10 premiers nombres triangulaires carrés sont: ( OEIS )

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

Il existe un nombre infini de nombres carrés, de nombres triangulaires et de nombres triangulaires carrés.

Écrivez un programme ou une fonction nommée qui a donné un numéro d'entrée (paramètre ou stdin) n, calcule le nnuméro triangulaire carré et le renvoie / le retourne, où n est un nombre positif non nul. (Pour n = 1, retournez 0)

Pour que le programme / la fonction soit une soumission valide, il doit être en mesure de renvoyer au moins tous les nombres triangulaires carrés inférieurs à 2 ^ 31-1.

Prime

-4 octets pour pouvoir sortir tous les nombres triangulaires carrés inférieurs à 2 ^ 63-1

-4 octets pour pouvoir théoriquement sortir des nombres triangulaires carrés de n'importe quelle taille.

Pénalité de +8 octets pour les solutions qui prennent du temps non polynomial.

Pile de bonus.

C'est un défi de code-golf, donc la réponse avec le moins d'octets l'emporte.

CJam, 12 8 octets

XUri{_34*@-Y+}*;

Utilise la relation de récurrence de l'article Wikipedia.

Le code est long de 16 octets et se qualifie pour les deux bonus.

Essayez-le en ligne dans l' interpréteur CJam .

Comment ça fonctionne

Mon code s'est avéré être identique à xnor dans tous les aspects, sauf que j'utilise la pile de CJam au lieu de variables.

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

Itère en utilisant la récurrence

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

En théorie, cela prend en charge des nombres de toute taille, mais fonctionne en temps exponentiel, donc il ne devrait pas être admissible aux bonus. Devrait fonctionner pour des numéros de toute taille. Par exemple, pour 100, donne

1185827220993342542557325920096705939276583904852110550753333094088280194260929920844987597980616456388639477930416411849864965254621398934978872054025

Une solution récursive utilise 41 caractères, mais ne doit pas être qualifiée car elle prend un temps exponentiel.

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

Pyth, 16-4-4 = 8 octets

Utilise la formule récursive de l'article OEIS.

K1uhh-*34G~KGtQZ

Il utilise la commande post-assign qui est assez nouvelle et semble vraiment cool. Les utilisations réduisent les temps d'itération en n-1raison de l'indexation basée sur 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.

Semble être polynomial car il boucle n fois et fait des calculs et des affectations à chaque itération, mais je ne suis pas un informaticien. Finit n = 10000 presque instantanément.

Essayez-le ici en ligne .

Oasis , 7 - 4 - 4 = -1 (sans compétition)

34*c-»T

Essayez-le en ligne!

Les usages a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2

Oasis prend en charge des nombres entiers de précision arbitraire, il devrait donc pouvoir atteindre n'importe quel nombre tant qu'aucun débordement de pile ne se produit. Faites-moi savoir si cela ne compte pas pour le bonus en raison du débordement de pile. Il est également possible que cet algorithme particulier soit non polynomial, et faites-moi savoir si c'est le cas.

Non concurrentiel parce que le défi des postdates linguistiques.

Explication:

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

Solution alternative:

-35*d+T

Utilise plutôt a(n) = 35*(a(n-1)-a(n-2)) + a(n-3)

JavaScript (ES6), 29-4 = 25 octets

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

5 octets enregistrés grâce à @IsmaelMiguel !

J'ai dû coder en dur le 0, 1 et les négatifs pour éviter une récursion infinie.

Console, j'ai nommé la fonction f:

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

EDIT : il s'avère que JavaScript arrondira les nombres à 16 (15) chiffres (Spec) car ces nombres sont trop grands, provoquant un débordement. Mettez 714341252076979033 dans votre console JavaScript et voyez par vous-même. C'est plus une limitation de JavaScript

Excel VBA - 90 octets

En utilisant la relation de récurrence de la page Wikipedia:

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

Une fois exécuté, vous êtes invité à entrer n, puis la séquence jusqu'à n inclus est sortie dans la colonne A:

Il peut être exécuté jusqu'à n = 202 inclusivement avant de donner une erreur de débordement.

[Pas de concurrence] Pyth (14 - 4 - 4 = 6 octets)

K1u/^tG2~KGQ36

Utilisé la première récurrence d' OEIS , qu'après 0,1,36 vous pouvez trouver A _n = (A _n-1 -1) ² / A _n-2 . A Pas en concurrence car cette solution commence à 36, si vous descendez, vous divisez par zéro (donc l'entrée de 0 donne 36). A également dû coder en dur 36.

Essayez-le ici

Java, 53-4 = 49 octets

C'est une autre récursion simple, mais je n'arrive pas souvent à publier Java avec un score <50, alors ...

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

Maintenant, pour quelque chose de non récursif, cela devient un peu plus long. Celui-ci est à la fois plus long (112-4 = 108) et plus lent, donc je ne sais pas pourquoi je le poste, sauf pour avoir quelque chose d'itératif:

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;}

Julia, 51 octets - 4 - 4 = 43

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

Cela utilise la première relation de récurrence répertoriée sur la page Wikipedia pour les nombres triangulaires carrés. Il calcule n = 1000 en 0,006 secondes et n = 100000 en 6,93 secondes. C'est quelques octets de plus qu'une solution récursive mais c'est beaucoup plus rapide.

Non golfé + explication:

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

Exemples:

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 octets

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

répéter jusqu'à ce que la racine carrée de $ssoit ∈ℤ: ajouter $fà la somme $s, incrémenter $f;
répéter $argv[1]fois.
somme de sortie.

Prolog, 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).

Exécution de n(100,R)sorties:

X = 40283218019606612026870715051828504163181534465162581625898684828251284020309760525686544840519804069618265491900426463694050293008018241080068813316496

Prend environ 1 seconde pour fonctionner n(10000,X)sur mon ordinateur.

Edit : La version 66 est récursive de queue. La version précédente, non récursive, est la suivante:

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.

Ils ont la même longueur en octets mais le non récursif de queue génère des débordements de pile au-delà d'un certain point (sur mon ordinateur, vers 20500).

Javascript ES6, 77 75 71 caractères

// 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)}}

• La solution est linéaire.
• La solution peut générer tous les nombres inférieurs à 2 ^ 53 en raison du type de nombre.
• L'algorithme lui-même peut être utilisé pour un nombre illimité.

Tester:

f(11)

0
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796

C, 68 octets

Ce fut un défi amusant avec C

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

Regardez-le fonctionner ici: https://ideone.com/0ulGmM

Gelée , 13 - 8 = 5 octets

Cela donne droit aux deux bonus.

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

Essayez-le en ligne!

Fait aux côtés de caird coinheringaahing dans le chat .

Explication

× 8 ', µÆ²Ạ ~ Lien d'assistance.

× 8 ~ 8 fois le nombre.
  '~ Incrément.
   , ~ Jumelé avec le numéro actuel.
    µ ~ Démarre une nouvelle liaison monadique (1-arg).
     Ʋ ~ Vectorisé "Is Square?".
       Ạ ~ Tout. Ne retournez 1 que si les deux sont véridiques.



0Ç # Ṫ ~ Lien principal.

0 # ~ À partir de 0, collectez les N premiers entiers avec des résultats véridiques, lorsqu'ils sont appliqués:
 Ç ~ Le dernier lien en tant que monade.
   Ṫ ~ Dernier élément. Sortie implicitement.

Perl 6 , 25 - 8 = 17 octets

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

Essayez-le en ligne!

05AB1E , 10 - 8 = 2 octets

1ÎGDŠ34*Ìα

Essayez-le en ligne!

APL (NARS), 67 caractères, 134 octets

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

tester:

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

f rechercherait en séquence quadratique les éléments qui sont également des nombres triangulaires, ils doivent donc suivre la formule de vérification triangulaire dans les APL: 0 = 1∣√1 + 8 × m avec le nombre m à vérifier.