Contexte

Une grille triangulaire est une grille formée en mosaïque régulière du plan avec des triangles équilatéraux de longueur 1. L'illustration ci-dessous est un exemple de grille triangulaire.

Un point de réseau triangulaire est un sommet d'un triangle formant la grille triangulaire.

L' origine est un point fixe sur le plan, qui est l'un des points du réseau triangulaire.

Défi

À partir d'un entier non négatif n, recherchez le nombre de points de réseau triangulaires dont la distance euclidienne par rapport à l'origine est inférieure ou égale à n.

Exemple

La figure suivante est un exemple pour n = 7(ne montrant qu'une zone de 60 degrés par souci de commodité, le point A étant l'origine):

Cas de test

Input | Output
---------------
    0 |       1
    1 |       7
    2 |      19
    3 |      37
    4 |      61
    5 |      91
    6 |     127
    7 |     187
    8 |     241
    9 |     301
   10 |     367
   11 |     439
   12 |     517
   13 |     613
   14 |     721
   15 |     823
   16 |     931
   17 |    1045
   18 |    1165
   19 |    1303
   20 |    1459
   40 |    5815
   60 |   13057
   80 |   23233
  100 |   36295
  200 |  145051
  500 |  906901
 1000 | 3627559

Astuce : Cette séquence n'est pas OEIS A003215 .

Règles

Les règles standard pour le golf de code s'appliquent. La soumission la plus courte gagne.

Veuillez inclure comment vous avez résolu le problème dans votre soumission.

code-golf math geometry Barboteur
la source

7

OEIS A053416 est la séquence du nombre de points contenus dans un cercle de diamètre plutôt que de rayon n. Vous avez donc deux fois plus de termes que vous le souhaitez.

Neil

Wikipédia et Mathworld pertinents . Contient la formule de xnor et non une preuve.

user202729

4

C'est la somme des premiers n^2+1termes d' OEIS A004016 .

Alephalpha

49

Python 2 , 43 octets

f=lambda n,a=1:n*n<a/3or n*n/a*6-f(n,a+a%3)

Essayez-le en ligne!

C'est de la magie noire.

~~Offrir 250 représentants pour une preuve écrite.~~ Voirla réponse de Lynnpour une preuve et une explication.

Xnor
la source

7

Comment cela marche-t-il? Cela fait 30 bonnes minutes que je me pose des questions ... Cela a l'air si simple mais je ne trouve pas de lien entre cette récursion et les cercles ...

JungHwan Min

7

@JungHwanMin Ma preuve est un voyage épique à travers la géométrie plane, les entiers d'Eisenstein, la factorisation en champs numériques, la réciprocité quadratique, les progressions arithmétiques et les sommations interchangeables, le tout pour une expression aussi simple. Écrire tout cela serait une entreprise majeure pour laquelle je n'ai pas le temps, alors j'espère que quelqu'un d'autre donnera une preuve, probablement plus simple que la mienne, qui rend le lien plus clair.

XNOR

14

Preuve . C'est plus long que celui de Lynn mais plus autonome: il ne fait pas usage d'affirmations non prouvées sur la factorisation sur les entiers d'Eisenstein.

Peter Taylor

2

@PeterTaylor Cheddar Moine? Comme dans Darths & Droids?

Neil

3

@Neil, félicitations d'être la première personne à demander! J'ai enregistré le domaine pour l'utiliser comme monnaie d'échange pour la négociation, niveau 1 de l'académie.

Peter Taylor

30

Haskell , 48 octets

f n=1+6*sum[(mod(i+1)3-1)*div(n^2)i|i<-[1..n^2]]

Essayez-le en ligne!

Utilise la formule "magie noire" de xnor:

F (n) = 1 + 6 Σ_{une = 0}^{\infty} ⌊ \frac{n^{2}}{3 une + 1} ⌋ - ⌊ \frac{n^{2}}{3 une + 2} ⌋

$f(n)=1+6\sum_{a=0}^\infty \left\lfloor \frac{n^2}{3a+1}\right\rfloor - \left\lfloor \frac{n^2}{3a+2}\right\rfloor$

Une preuve de sa justesse, et une explication de la façon dont xnor a réussi à exprimer dans 43 octets de Python, peuvent être trouvés ici .

$1 \le N \le n^2$ $N = (x+y\omega)(x+y\omega^*)$ $(x,y)$

$6 \times ((Nombre de diviseurs de N \equiv 1 (mod 3)) - (Nombre de diviseurs de N \equiv 2 (mod 3)))$ $6 \times ((\text{# of divisors of }N \equiv 1\space(\text{mod }3)) - (\text{# of divisors of }N \equiv 2\space(\text{mod }3)))$
$1$ $n^2$

Lynn
la source

4

Je ne m'attendais certainement pas à cela lorsque xnor a déclaré: "Il existe des connaissances mathématiques profondes à l'origine du problème".

Bubbler

29

Wolfram Language (Mathematica) , 53 51 50 octets

^{-1 octet grâce à @miles}

Sum[Boole[x(x+y)+y^2<=#^2],{x,-2#,2#},{y,-2#,2#}]&

Essayez-le en ligne!

Comment?

Au lieu de penser à ceci:

Pensez-y comme ceci:

Nous appliquons donc la matrice [[sqrt(3)/2, 0], [1/2, 1]]de transformation pour transformer le deuxième chiffre en premier.

Ensuite, il faut trouver le cercle dans la grille triangulaire en termes de coordonnées cartésiennes.

(sqrt(3)/2 x)^2 + (1/2 x + y)^2 = x^2 + x y + y^2

Donc, nous trouvons des points de réseau x, ytels quex^2 + x y + y^2 <= r^2

Par exemple, avec r = 3:

JungHwan Min
la source

1

Pour votre information, la formule x^2+x y+y^2peut également être dérivée de la loi des cosinus à 120 degrés.

Bubbler

3

x^2+x y+y^2-> x(x+y)+y^2enregistre un octet

miles

La formule x^2 + xy + y^2peut également être dérivée de la norme d’un nombre entier d’Eistenstein, qui est a^2 - ab + b^2. Notez que le signe de aet bn'est pas pertinent sauf dans le terme, de absorte qu'il a le même nombre de solutions.

Orlp

9

Wolfram Language (Mathematica) , 48 octets

Basé sur OEIS A004016 .

1+6Sum[DivisorSum[i,#~JacobiSymbol~3&],{i,#^2}]&

Essayez-le en ligne!

Alephalpha
la source

7

CJam (24 octets)

{_*_,f{)_)3%(@@/*}1b6*)}

Il s'agit d'un bloc anonyme (fonction) qui prend un argument sur la pile et laisse le résultat sur la pile. Suite de tests en ligne . Notez que les deux plus gros cas sont trop lents.

Explication

Alephalpha a noté dans un commentaire sur la question que

C'est la somme des n premiers ^ 2 + 1 termes d' OEIS A004016

F (n) = 1 + 6 Σ_{une = 0}^{\infty} ⌊ \frac{n^{2}}{3 une + 1} ⌋ - ⌊ \frac{n^{2}}{3 une + 2} ⌋

$f(n) = 1 + 6 \sum_{a=0}^\infty \left\lfloor\frac{n^2}{3a+1}\right\rfloor - \left\lfloor\frac{n^2}{3a+2}\right\rfloor$

Ma preuve de l'exactitude de cette formule est basée sur des informations tirées du lien OEIS d'Alephalpha:

Gf: 1 + 6 * Somme_ {n> = 1} x ^ (3 * n-2) / (1-x ^ (3 * n-2)) - x ^ (3 * n-1) / (1- x ^ (3 * n-1)). - Paul D. Hanna, 03 juillet 2011

$x^a$

Π_{k = 0}^{\infty} (1 - q^{k + 1}) (1 + X q^{k + 1}) (1 + X^{- 1} q^{k}) = \underset{k \in Z}{Σ} q^{k (k + 1) / 2} X^{k}

$\prod_{k=0}^\infty (1-q^{k+1})(1 + xq^{k+1})(1 + x^{-1}q^k) = \sum_{k\in \mathbb{Z}} q^{k(k+1)/2}x^k$

\underset{m, n \in Z}{Σ} ω^{m - n} q^{m^{2} + m n + n^{2}} = Π_{k = 1}^{\infty} \frac{(1 - q^{k})^{3}}{1 - q^{3 k}}

$\sum_{m,n \in \mathbb{Z}} \omega^{m-n} q^{m^2+mn+n^2} = \prod_{k=1}^\infty \frac{(1-q^k)^3}{1-q^{3k}}$

ω

$\omega$

\underset{m, n \in Z}{Σ} q^{m^{2} + m n + n^{2}} = 1 + 6 \underset{k \geq 0}{Σ} (\frac{q^{3 k + 1}}{1 - q^{3 k + 1}} - \frac{q^{3 k + 2}}{1 - q^{3 k + 2}})

$\sum_{m,n \in \mathbb{Z}} q^{m^2+mn+n^2} = 1 + 6 \sum_{k \ge 0} \left(\frac{q^{3k+1}}{1-q^{3k+1}} - \frac{q^{3k+2}}{1-q^{3k+2}} \right)$

Dissection de code

{          e# Define a block. Stack: ... r
  _*       e#   Square it
  _,f{     e#   Map with parameter: invokes block for (r^2, 0), (r^2, 1), ... (r^2, r^2-1)
    )      e#     Increment second parameter. Stack: ... r^2 x with 1 <= x <= r^2
    _)3%(  e#     Duplicate x and map to whichever of 0, 1, -1 is equal to it (mod 3)
    @@/*   e#     Evaluate (r^2 / x) * (x mod 3)
  }
  1b6*     e#   Sum and multiply by 6
  )        e#   Increment to count the point at the origin
}

Peter Taylor
la source

4

J , 27 octets

[:+/@,*:>:(*++&*:)"{~@i:@+:

Essayez-le en ligne!

Basé sur la méthode de JungHwan Min .

Explication

[:+/@,*:>:(*++&*:)"{~@i:@+:  Input: n
                         +:  Double
                      i:     Range [-2n .. 2n]
                  "{~        For each pair (x, y)
                *:             Square both x and y
              +                Add x^2 and y^2
             +                 Plus
            *                  Product of x and y
        >:                   Less than or equal to
      *:                     Square of n
     ,                       Flatten
  +/                         Reduce by addition

milles
la source

4

APL (Dyalog Classic) , 23 octets

{1+6×+/-/⌊⍵÷1+3⊥¨⍳⍵2}×⍨

Essayez-le en ligne!

hommage à son xnor et de lynn réponses

le dernier test est commenté car il a besoin de plus de mémoire, par exemple MAXWS=200Mdans env

ngn
la source

3

Gelée , 14 octets

ḤŒR+²_×ʋþ`F½»ċ

Utilise la méthode de @ JungHwanMin .

Essayez-le en ligne!

Dennis
la source

3

Gelée , 15 à 13 octets

-2 grâce à Dennis (incrémentez simplement le carré pour éviter la concaténation d'un zéro; évitez la tête en utilisant une tranche modulo post-différence plutôt qu'une tranche pré-différence)

^{Utilise la méthode de "magie noire" pour préciser la réponse exposée par xnor dans sa réponse en Python , mais utilise l'itération plutôt que la récursion (et un peu moins de calcul)}

²:Ð€‘$Im3S×6C

Un lien monadique acceptant un entier non négatif et renvoyant un entier positif.

Essayez-le en ligne! Ou voir la suite de tests .

Comment?

²:Ð€‘$Im3S×6C - Main Link: non-negative integer, n     e.g. 7
²             - square                                     49
     $        - last two links as a monad:
    ‘         -   increment                                50
  Ð€          -   map across (implicit range of) right with:
 :            -     integer division                       [49,24,16,12,9,8,7,6,5,4,4,4,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]
      I       - incremental differences                    [-25,-8,-4,-3,-1,-1,-1,-1,-1,0,0,-1,0,0,0,-1,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1]
       m3     - every third element                        [-25,-3,-1,0,0,-1,0,0,0,0,0,0,0,0,0,0,-1]
         S    - sum (vectorises)                           -31
          ×6  - multiply by six                           -186
            C - complement (1-X)                           187

Jonathan Allan
la source

2

JavaScript (ES6), 65 octets

Ceci est un port de la solution de @ JungHwanMin .

f=(n,y=x=w=n*2)=>y-~w&&(x*x+x*y+y*y<=n*n)+f(n,y-=--x<-w&&(x=w,1))

Essayez-le en ligne!

Réponse originale (ES7), 70 octets

Il suffit de parcourir la grille et de compter les points correspondants.

f=(n,y=x=n*=2)=>y+n+2&&(x*x*3+(y-x%2)**2<=n*n)+f(n,y-=--x<-n&&(x=n,2))

Essayez-le en ligne!

Arnauld
la source

La réponse de xnor au portage est plus courte: 42 octets (sorties trueau lieu de 1; 46 si on le divise également en entier). Et je ne connais pas assez bien JavaScript pour jouer au golf dans les divisions entières ~~(a/b), mais je suis sûr qu'il existe un moyen plus court pour celles-ci aussi.

Kevin Cruijssen Le

1

Java 8, 65 octets

n->f(n,1)int f(int n,int a){return n*n<a/3?1:n*n/a*6-f(n,a+a%3);}

Port de la réponse Python 2 de @xnor .

Essayez-le en ligne.

Kevin Cruijssen
la source

1

Paris / GP , 42 octets

En utilisant le intégré qfrep.

n->1+2*vecsum(Vec(qfrep([2,1;1,2],n^2,1)))

qfrep (q, B, {flag = 0}): vecteur de (moitié) le nombre de vecteurs de normes de 1 à B pour la forme quadratique intégrale et définie q. Si flag est égal à 1, compter les vecteurs de même norme de 1 à 2B.

Essayez-le en ligne!

Alephalpha
la source

0

C # (compilateur interactif Visual C #) , 68 octets

n=>{int g(int x,int y)=>x*x<y/3?1:x*x/y*6-g(x,y+y%3);return g(n,1);}

Essayez-le en ligne!

Comme tout le monde, malheureusement. Je sais qu’il ya probablement une meilleure façon d’écrire cela, mais déclarer et appeler un lambda en même temps en c # n’est pas exactement quelque chose que je fais, enfin, jamais. Bien que dans ma défense, je ne peux pas penser à une bonne raison (en dehors du code golf, bien sûr) de le faire. Néanmoins, si quelqu'un sait comment vous pouvez faire cela, laissez-moi savoir et / ou voler le crédit, je suppose.

Andrew Baumher
la source

0

Wolfram Language (Mathematica) , 39 octets

Length@Solve[x(x+y)+y^2<=#^2,Integers]&

Essayez-le en ligne!

Utiliser la transformation de coordonnées de JungHwan Min et compter simplement les solutions sur les entiers.

romain
la source

0

05AB1E , 15 octets

nD>L÷¥ā3%ÏO6*±Ì

La réponse du port de @JonathanAllan Jelly , qui est elle-même un dérivé de la formule de «magie noire» de @ xnor .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

n                # Square the (implicit) input-integer
 D>              # Duplicate it, and increase the copy by 1
   L             # Create a list in the range [1, input^2+1]
    ÷            # Integer divide input^2 by each of these integers
     ¥           # Take the deltas
      ā          # Push a list in the range [1, length] without popping the deltas itself
       3%        # Modulo each by 3
         Ï       # Only leave the values at the truthy (==1) indices
          O      # Take the sum of this list
           6*    # Multiply it by 6
             ±   # Take the bitwise NOT (-n-1)
              Ì  # And increase it by 2
                 # (after which the result is output implicitly)

Kevin Cruijssen
la source

Points de treillis triangulaires proches de l'origine

Contexte

Défi

Exemple

Cas de test

Règles

Réponses:

Python 2 , 43 octets

Haskell , 48 octets

Wolfram Language (Mathematica) , 53 51 50 octets

Comment?

Wolfram Language (Mathematica) , 48 octets

CJam (24 octets)

Explication

Dissection de code

J , 27 octets

Explication

APL (Dyalog Classic) , 23 octets

Gelée , 14 octets

Gelée , 15 à 13 octets

Comment?

JavaScript (ES6), 65 octets

Réponse originale (ES7), 70 octets

Java 8, 65 octets

Paris / GP , 42 octets

C # (compilateur interactif Visual C #) , 68 octets

Wolfram Language (Mathematica) , 39 octets

05AB1E , 15 octets