Un entier positif kest un nombre de Loeschian si

• kpeut être exprimé comme i*i + j*j + i*jpour i, jentier.

Par exemple, les premiers nombres loeschiens positifs sont: 1( i=1, j=0); 3( i=j=1); 4( i=2, j=0); 7( i=2, j=1); 9( i=-3, j=3); ... Notez que i, jpour une donnée, kne sont pas uniques. Par exemple, 9peut également être généré avec i=3, j=0.

Les autres caractérisations équivalentes de ces nombres sont:

• kpeuvent être exprimés sous forme i*i + j*j + i*jde i, jentiers non négatifs. (Pour chaque paire d'entiers i, jil y a une paire d'entiers non négatifs qui donne le même k)

• Il y a un ensemble d' khexagones contigus qui forment une tesselation sur une grille hexagonale (voir les illustrations pour k = 4et pour k = 7). (En raison de cette propriété, ces numéros trouvent une application dans les réseaux de communication cellulaires mobiles .)

• Voir plus de caractérisations dans la page OEIS de la séquence.

Le défi

Étant donné un nombre entier positif , la sortie d' un résultat truthy si elle est un nombre Loeschian , ou un résultat falsy autrement.

Le programme ou la fonction doit gérer (par exemple en moins d’une minute) les entrées jusqu’à 1000ou jusqu’à des limites de types de données.

Code de golf. Le plus court gagne.

Cas de test

Les nombres suivants devraient donner un résultat vrai:

1, 4, 7, 12, 13, 108, 109, 192, 516, 999

Les nombres suivants devraient donner un résultat faux:

2, 5, 10, 42, 101, 102, 128, 150, 501, 1000

Gelée , 11 à 9 octets

ÆF‘%3,2ḄȦ

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

Contexte

Dans Résultats élémentaires sur la forme quadratique binaire a² + ab + b² , l'auteur prouve le théorème suivant sur les nombres löschiens.

Théorème 16. La condition nécessaire et suffisante de tout nombre entier non négatif pour être sous la forme a² + ab + b² est que, dans sa factorisation première, tous les nombres premiers autres que 3 qui ne sont pas sous la forme (6k + 1) ont même exposants.

Comme indiqué sur la page OEIS correspondante , tous les entiers étant congruents à 0 , 1 ou 2 modulo 3 , le nombre 3 est le seul nombre premier congru à 0 et tous les nombres de la forme (6k + 1) sont congruents. 1 , le théorème peut être énoncé alternativement comme suit.

Un entier non négatif n est un nombre de Löschian si et seulement si tous les facteurs premiers de n congruants à 2 modulo 3 ont même des exposants.

Comment ça marche

ÆF‘%3,2ḄȦ  Main link. Argument: n (integer)

ÆF         Yield the prime factorization of n, as prime-exponent pairs.
  ‘        Increment all primes and exponents, turning primes of the form 3k - 2
           into multiples of 3 and odd exponents into multiples of 2.
   %3,2    Reduce all incremented primes/exponents modulo 3/2.
           n is Löschian if and only if this does not result in a [0, 0] pair.
           Due to Jelly's form of vectorization, this yields [3, 2] if n = 1.
       Ḅ   Unbinary; convert each pair from base 2 to integer.
           Note that [x, y] = [0, 0] if and only if 2x + y = 0.
        Ȧ  All; return 1 if the result contains no zeroes, 0 otherwise.

Retina , 66 63 45 43 36 octets

^()(\1(?<1>.\1))+(\1(.(?(4).\4)))*$

Malgré le titre disant Retina, il s’agit simplement d’une expression rationnelle .NET qui accepte les représentations unaires des nombres de Loeschian.

Les entrées 999 et 1000 prennent bien moins d'une seconde.

Essayez-le en ligne! (La première ligne active une suite de tests séparée par des sauts de ligne et les deux suivantes traitent de la conversion en unaire pour des raisons de commodité.)

Explication

La solution est basée sur la classification selon laquelle l'entrée peut être écrite de manière i*i + j*(i + j)positive iet non négative j(puisque nous n'avons pas à gérer l'entrée 0), et c'est n*nsimplement la somme des premiers nentiers impairs. Le golf était un exercice intéressant dans les références en avant.

Une "référence en aval" est une référence en arrière dans le groupe auquel elle fait référence. Bien sûr, cela ne fonctionne pas lorsque le groupe est utilisé pour la première fois, car il n’ya pas encore de référence en retour, mais si vous mettez cela dans une boucle, la référence en arrière obtient à chaque fois la capture de l’itération précédente. Cela vous permet d’accumuler une capture plus grande à chaque itération. Ceci peut être utilisé pour créer des motifs très compacts pour des choses comme des nombres triangulaires, des carrés et des nombres de Fibonacci.

Par exemple, en utilisant le fait que les carrés ne sont que la somme des premiers nentiers impairs, nous pouvons faire correspondre une entrée carrée comme celle-ci:

(^.|..\1)+$

À la première itération, ..\1ne peut pas fonctionner car il \1n'a pas encore de valeur. Nous commençons donc par ^.capturer un seul personnage dans un groupe 1. Lors des itérations suivantes, ^.ne correspond plus en raison de l'ancre, mais ..\1est maintenant valide. Il correspond à deux caractères de plus que l'itération précédente et met à jour la capture. De cette façon, nous faisons correspondre des nombres impairs croissants, en obtenant un carré après chaque itération.

Malheureusement, nous ne pouvons pas utiliser cette technique telle quelle. Après l’appariement i*i, nous devons iaussi obtenir le résultat pour pouvoir le multiplier par j. Un moyen simple (mais long) de faire cela consiste à utiliser le fait que l'appariement i*iprend des iitérations, de sorte que nous avons capturé des iéléments en groupe 1. Nous pourrions maintenant utiliser des groupes d'équilibrage pour extraire cela i, mais comme je l'ai dit, cela coûte cher.

Au lieu de cela, j'ai imaginé une manière différente d'écrire cette "somme d'entiers impairs consécutifs" qui aboutit également ià un groupe de capture à la fin. Bien sûr, le itroisième chiffre est juste 2i-1. Cela nous donne un moyen d'incrémenter la référence en avant uniquement de 1 à chaque itération. C'est cette partie:

^()(\1(?<1>.\1))+

Cela ()pousse simplement une capture vide sur le groupe 1(initialisation ià 0). Ceci est à peu près équivalent à la ^.|solution simple ci-dessus, mais l’utilisation |dans ce cas serait un peu plus délicate.

Ensuite, nous avons la boucle principale (\1(?<1>.\1)). \1correspond au précédent i, (?<1>.\1)puis met à jour le groupe 1avec i+1. En termes de nouveauté i , nous venons d'associer des 2i-1personnages. Exactement ce dont nous avons besoin.

Lorsque nous avons terminé, nous avons identifié un carré i*iet le groupe 1contient toujours des ipersonnages.

La deuxième partie est plus proche de la simple correspondance carrée que j'ai montrée ci-dessus. Ignorons la référence arrière 1pour l'instant:

(.(?(4).\1))*

C'est fondamentalement la même chose (^.|..\4)*, sauf que nous ne pouvons pas utiliser ^car nous ne sommes pas au début de la chaîne. Au lieu de cela, nous utilisons un conditionnel, pour faire correspondre le complément .\1uniquement lorsque nous avons déjà utilisé le groupe 4. Mais en réalité, c'est exactement la même chose. Cela nous donne j*j.

La seule chose qui manque, c'est le j*iterme. Nous combinons cela avec le j*jen utilisant le fait que le j*jcalcul prend encore des jitérations. Donc, pour chaque itération, nous faisons également avancer le curseur iavec \1. Nous devons simplement nous assurer de ne pas écrire cela dans le groupe 4, car cela gâcherait la correspondance de nombres impairs consécutifs. C'est comme ça qu'on arrive au:

(\1(.(?(4).\1)))*

CJam ( 16 15 octets)

{mF{~\3%2=&},!}

Démo en ligne

C'est un bloc (une "fonction anonyme") qui prend des entrées sur la pile et qui part 0ou 1sur la pile. Il utilise la caractérisation qu'un nombre est Loeschian ssi il n'a pas de facteur premier égal à 2 mod 3 avec une multiplicité impaire.

Merci à Dennis pour une économie d'un octet.

Python 2, 56 octets

lambda n:any(n==i*i%n+i/n*(i/n+i%n)for i in range(2*n*n))

Haskell, 42 octets

f k=or[k==i*i+j*j+i*j|i<-[0..k],j<-[0..i]]

Exemple d'utilisation: f 501-> False.

Essaye toutes les combinaisons de ipartir 0à ket jde 0à i. orretourne Truesi l'égalité k==i*i+j*j+i*jest valable pour au moins une des combinaisons.

@flawr a trouvé une version légèrement différente avec le même nombre d'octets:

f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]

Java 8, 81 octets

k->{for(int i=0,j;i<=k;i++)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

mise en œuvre simple et naïve. coïncidence même code que C # mais utilise ->plutôt que =>.

Python, 67 octets

lambda k,r=range:any(i*i+j*j+i*j==k for i in r(k+1)for j in r(k+1))

https://repl.it/Cj6x

Jelly , 15 14 13 12 octets

1 octet grâce aux miles.

²S+P
‘ṗ2’Ç€i

Essayez-le en ligne!

Vérifiez les plus petits cas de test .

Un conseil lorsque vous testez de grands nombres (plus de 50): ne le faites pas.

La vérité est un nombre positif. Falsey est zéro.

Explication

‘ṗ2’Ç€i   main chain, argument: z
‘ṗ2’      generate all pairs of numbers between 0 and z inclusive
    ǀ    apply the helper link to each pair
      i   find the index of z in the result

²S+P   helper link, argument: [x,y] (a pair of numbers)
²      compute [x*x, y*y]
 S     x*x+y*y
  +P   x*x+y*y+x*y

Méduse , 56 43 41 29 28 octets

2 octets grâce à Zgarb

p
n    <
+`/
`1*
/
+
&*r&;>i

Essayez-le en ligne!

Une fourchette de ma gelée répond .

MATL , 14 à 13 octets

t:0hU&+HM&*+m

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

Sorties 1ou 0.

Explication

t:    % Implicitly input number k. Duplicate. Generate vector [1 2 ...k]
0h    % Concatenate a 0. Gives [1 2 ... k 0]
U     % Square, element-wise. Gives [1 4 ... k^2 0]
&+    % Sum of all pairs from this vector. Gives a (k+1)×(k+1) matrix
HM    % Push [1 2 ... k 0] again
&*    % Product of all pairs from this vector. Gives a (k+1)×(k+1) matrix
+     % Add the two matrices
m     % True if k is a member of the resulting matrix. Implicitly display

Python, 49 octets

lambda n:0in[(n-3*i*i+0j)**.5%1for i in range(n)]

Utilise la forme quadratique équivalente donnée sur OEIS de n == 3*i*i+j*j. Vérifiez si n-3*i*iest un carré parfait pour tout ien prenant sa racine carrée et en vérifiant s'il s'agit d'un entier, c'est-à-dire égal à 0 modulo 1. Notez que Python calcule les racines carrées de carrés parfaits exactement, sans erreur de virgule flottante. Le +0jrend un nombre complexe pour éviter une erreur sur la racine carrée d'un négatif.

C (gcc), 71 69 octets

i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}

C #, 84 82 81 octets

k=>{for(int i=0,j;i<=k;++i)for(j=0;j<=k;)if(i*i+j*j+i*j++==k)return 1;return 0;};

Une solution naïve. 1 = vrai, 0 = faux

VBA, 68 67 octets

Function L(N):For a=0To N:For b=0To a:L=L+(N=a^2+a*b+b^2):Next b,a

Recherche naïve, commençant à ralentir légèrement pour n = 1000. Excel reconnaît le retour nul comme étant une fausseté, tous les autres comme une vérité.

Notez que l'investigation des valeurs négatives i et j n'est pas nécessaire, étant donné que i> j> = 0 :

(-i) ² + (-i) (- j) + (-j) ² = i ² + ij + j ²

(le même résultat que pour i et j )

(-i) ² + (-i) j + j ² = i ² - ij + j ²

i ² + i (-j) + (-j) ² = i ² - ij + j ²

(si on est négatif, peu importe lequel), puis

(ij) ² + (ij) j + j ² = (i ² - 2ij + j ² ) + (ij - j ² ) + j ² = i ² - ij + j ²

Et puisque les deux (ij) et j sont non négatifs, toute génération de nombres de Loeschian comportant un nombre négatif peut être obtenue à l’aide de nombres non négatifs.

Enregistré un octet, Next:Next-> Next b,agrâce à Taylor Scott.

Javascript (en utilisant une bibliothèque externe - Enumerable) (63 octets)

k=>_.Range(0,k+1).Any(i=>_.Range(0,k+1).Any(j=>i*i+j*j+i*j==k))

Lien vers la bibliothèque: https://github.com/mvegh1/Enumerable Explication de code: créez une plage d'entiers de 0 à k (appelez-la la plage "i") et testez si un quelconque "i" satisfait un prédicat donné. Ce prédicat crée une plage de 0 à k (appelez la plage "j") et teste si un "j" satisfait à un prédicat donné. Ce prédicat est la formule loeschienne

Perl 6 ,  52 51  50 octets

->\k{?first ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}
->\k{?grep ->(\i,\j){k==i*i+j*j+i*j},(0..k X 0..k)}

{?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

Explication:

{
  # Turn the following into a Bool
  # ( Technically not necessary as a list of 1 or more values is truthy )
  ?

  # find all where the code block returns a truthy value
  grep

  # pointy block that takes one value (list of 2 values)
  # and gives each of the values in it a name
  ->
    $ ( \i, \j )
  {
    # return true if the definition matches
    $_ == i*i + j*j + i*j
  },

  # a list of 2 element lists (possible i and j values)
  ( 0..$_ X 0..$_ )
}

Tester:

use v6.c;
use Test;

my @true = 0, 1, 4, 7, 12, 13, 108, 109, 192, 516, 999;
my @false = 2, 5, 10, 42, 101, 102, 128, 150, 501, 1000;

plan (@true + @false) * 2;

my &is-loeschian = {?grep ->(\i,\j){$_==i*i+j*j+i*j},(0..$_ X 0..$_)}

for |(@true X True), |(@false X False) -> ( $input, $expected ) {
  my ($result,$seconds) = $input.&time-it;
  is $result, $expected, ~$input;
  cmp-ok $seconds, &[<], 60, "in $seconds seconds"
}

sub time-it ( $input ) {
  my $start = now;
  my $result = $input.&is-loeschian;
  my $finish = now;
  return ( $result, $finish - $start )
}

1..42
ok 1 - 0
ok 2 - in 0.00111763 seconds
ok 3 - 1
ok 4 - in 0.00076766 seconds
...
ok 19 - 516
ok 20 - in 0.19629727 seconds
ok 21 - 999
ok 22 - in 0.1126715 seconds
ok 23 - 2
ok 24 - in 0.0013301 seconds
ok 25 - 5
ok 26 - in 0.00186610 seconds
...
ok 37 - 150
ok 38 - in 0.83877554 seconds
ok 39 - 501
ok 40 - in 9.2968558 seconds
ok 41 - 1000
ok 42 - in 37.31434146 seconds

PowerShell v2 +, 63 56 55 octets

param($k)(0..$k|%{0..($i=$_)|%{$i*($i+$_)+$_*$_}})-eq$k

Prend entrée $k, boucle deux fois vers le haut (boucle extérieure, boucle $i = 0 to $kintérieure $j = 0 to $i), chaque itération génère le résultat de i*i + j*j + i*j(raccourci à i*(i+j) + j*j). Ces résultats sont encapsulés dans des parenthèses et transmis sous forme de tableau à -eq$k. Cela agit comme un filtre pour ne sélectionner que les éléments qui sont égaux à l'entrée. Renvoie une valeur non nulle (le numéro précédent) pour la vérité ou rien (vide) pour Falsey. Traite 1000en 15 secondes environ sur ma machine.

Cas de test

PS C:\Tools\Scripts\golfing> (1,4,7,12,13,108,109,192,516,999|%{.\loeschian-numbers.ps1 $_})-join','
1,4,7,12,13,108,109,192,516,999

PS C:\Tools\Scripts\golfing> (2,5,10,42,101,102,128,150,501,1000|%{.\loeschian-numbers.ps1 $_})-join','

PS C:\Tools\Scripts\golfing>

Perl, 54 + 1 ( -ndrapeau) = 55 octets

for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}

Besoins -net -M5.010drapeaux à exécuter:

perl -nE 'for$i(0..$_){for$j(0..$_){$i*$i+$j*$j+$i*$j-$_?1:say}}'

Affiche des données si le nombre est un nombre loeschien et rien sinon.

Cette implémentation est assez ennuyeuse, donc en voici une autre, pour 87 octets, basée sur regex, juste pour les yeux:

perl -pE '$_=(1 x$_)=~/^(.*)(??{$1x(-1+length$1)})(.*)(??{$2x(-1+length$2)})(??{$1x length$2})$/'

Faites attention à celui-ci, car le retour en arrière consomme beaucoup de mémoire, alors n'essayez pas de tester des nombres trop gros! (surtout les nombres qui ne sont pas Loeschians)

Dyalog APL , 19 octets

⊢∊(∘.(×-⍨2*⍨+)⍨0,⍳)

Vérifie si k ∊ ( i + j ) ² - ij , pour tout 0 ≤ i , j ≤ k .

    ⊢k est
∊un membre de
    ∘.toutes les combinaisons de
        × i fois j
        -⍨ soustrait du
        2*⍨carré de
        + i plus j
    ⍨ pour tout i et j en
    0,zéro précédé
    ⍳des nombres entiers de 1 à k

1000 prend 3,3 secondes sur mon M540 et encore moins sur TryAPL .

Matlab, 53 52 octets

n=input('');[a b]=ndgrid(0:n);find((a+b).^2-a.*b==n)

Recherche simple sur toutes les possibilités.
Affiche un tableau vide en tant que falsy et un vecteur non vide en tant que valeur de vérité.

Considérant que la matrice tout-zéros est falsy et la matrice non-tout-zéros comme une vérité, nous pouvons nous débarrasser de la findfonction, ce qui donne une solution de 47 à 46 octets :

n=input('');[a b]=ndgrid(0:n);(a+b).^2-a.*b==n

Un octet enregistré grâce à @flawr

C, 66 octets

Appelez f()avec le numéro à tester. La fonction renvoie le nombre de solutions trouvées.

q,r;f(n){for(r=q=0;q++<n*n;r+=n==q%n*(q%n+q/n)+q/n*q/n);return r;}

Essayez sur ideone .

Mathematica, 44 octets

MemberQ[(+##)^2-##&@@@0~Range~#~Tuples~2,#]&

Fonction sans nom prenant un entier en entrée et renvoyant Trueou False. La commande 0~Range~#~Tuples~2crée toutes les paires ordonnées d'entiers entre 0l'entrée et l'entrée #. La fonction (+##)^2-##&calcule le carré de la somme de ses arguments moins le produit de ses arguments; lorsqu'il est appelé sur deux arguments iet j, c'est exactement i^2+j^2+ijcomme souhaité. Donc, cette fonction est appelée sur tous les n-uplets, puis MemberQ[...,#]vérifie si l'entrée est l'une des valeurs résultantes.

ASP, 39 + 4 = 43 octets

o:-k=I*I+J*J+I*J;I=1..k;J=1..k.:-not o.

Résultat: le problème est satisfaisable si et seulement si k est loeschien.

Answer Set Programming est un langage logique, similaire au prologue. J'utilise ici l' implémentation Potassco , Clingo .

L'entrée est prise à partir de paramètres ( -ck=4 octets de long). Exemple d'appel:

clingo -ck=999

Échantillon de sortie:

SATISFIABLE

Essayé avec 1000:

clingo -ck=1000

Échantillon de sortie:

UNSATISFIABLE

Vous pouvez l'essayer dans votre navigateur . Malheureusement, cette méthode ne gère pas les indicateurs d'appel, vous devez donc ajouter la ligne #const k=999pour que cela fonctionne.

Ungolfed & code expliqué:

v(1..k).  % predicate v(X) holds for any X in [1..k]
o:- k=I*I+J*J+I*J ; v(I) ; v(J).  % o holds if k is Loeschian.
:- not o.  % discard models where o doesn't holds (make problem unsatisfiable)

PHP, 70 octets

for(;$i++<$k=$argv[1];)for($j=$i+1;$j--;)$i*$i+$j*$j+$i*$j-$k?:die(1);

prend en charge l'argument de la ligne de commande sorties avec 1pour numéro Loeschian, avec 0else.
Courez avec -nr.

panne

for(;$i++<$k=$argv[1];)     # loop $i from 1 to $k
    for($j=$i+1;$j--;)      # loop $j from $i to 0
        $i*$i+$j*$j+$i*$j-$k?   # if $i,$j,$k do not satisfy the equation, do nothing
        :die(1);                # else exit with return code 1
                            # implicit: exit with code 0