Un nombre Abondant est un nombre où la somme de ses diviseurs appropriés est supérieure au nombre original. Par exemple, les diviseurs appropriés de 12 sont:
1, 2, 3, 4, 6
Et en sommant ces résultats dans 16. Puisque 16 est plus grand que 12, 12 est abondant. Notez que cela n'inclut pas les "nombres parfaits", par exemple les nombres qui sont égaux à la somme de ses diviseurs propres, tels que 6 et 28.
Votre tâche pour aujourd'hui est d'écrire un programme ou une fonction qui détermine si un nombre est abondant ou non. Votre programme doit prendre un seul entier en entrée et générer une valeur vérité / fausseté selon qu’il est abondant ou non. Vous pouvez supposer que l'entrée sera toujours valide et supérieure à 0. Par conséquent, pour les mauvaises entrées, le comportement non défini convient.
Vous pouvez utiliser vos entrées et sorties dans n’importe quel format raisonnable. Par exemple, STDIN / STDOUT, des fichiers ou des arguments / valeurs de retour seraient tous acceptables.
Pour référence, voici les nombres abondants jusqu’à 100:
12,
18,
20,
24,
30,
36,
40,
42,
48,
54,
56,
60,
66,
70,
72,
78,
80,
84,
88,
90,
96,
100
Et plus peut être trouvé sur A005101
Puisqu'il s'agit de code-golf , les échappatoires standard sont refusées et essayez d'écrire le code le plus court possible dans la langue de votre choix!
la source
Réponses:
ECMAScript Regex,
1085855597536511508504 octetsLa correspondance de nombres abondants dans les expressions rationnelles ECMAScript est une bête totalement différente de celle utilisée dans pratiquement toute autre saveur de regex. L'absence de références arrière ou de récursion imbriquées / imbriquées signifie qu'il est impossible de compter directement ou de conserver un total cumulé. Le manque de repères rend souvent difficile le fait de disposer de suffisamment d’espace pour travailler.
De nombreux problèmes doivent être abordés sous un angle totalement différent, et vous vous demanderez s'ils sont résolus. Cela vous oblige à utiliser un réseau beaucoup plus large pour déterminer quelles propriétés mathématiques des nombres avec lesquels vous travaillez pourraient être utilisées pour résoudre un problème particulier.
En mars-avril 2014, j'ai construit une solution à ce problème dans les expressions rationnelles ECMAScript. Au début, j’avais toutes les raisons de penser que le problème était complètement impossible, mais le mathématicien Teukon a ensuite esquissé une idée encourageante, mais il a clairement indiqué qu’il n’avait pas l’intention de construire la regex (il avait concurrencé / coopéré avec mon sur la construction / le golfing regex précédents, mais a atteint sa limite à ce point et était content de restreindre ses contributions ultérieures à la théorisation).
Comme dans mon regex posté il y a quelques jours, je tiens à vous avertir: je vous recommande vivement d'apprendre à résoudre des problèmes mathématiques unaires dans ECMAScript regex. Ce voyage a été fascinant pour moi et je ne veux pas le gâter pour ceux qui voudraient éventuellement l'essayer eux-mêmes, en particulier ceux qui s'intéressent à la théorie des nombres. Voir ce post pour une liste de problèmes recommandés consécutivement étiquetés spoiler à résoudre un par un.
Donc , ne lisez pas plus loin si vous ne voulez pas que la magie des regex unaires profondes vous soit gâtée . Mon post précédent était juste un petit goût. Si vous voulez vraiment essayer de comprendre cette magie, je vous recommande vivement de commencer par résoudre certains problèmes de la regex ECMAScript, comme indiqué dans l'article ci-dessus.
Avant de poster mon ECMAScript regex, je pensais que ce serait intéressant d'analyser Martin Ender solution .NET regex pur ,
^(?!(1(?<=(?=(?(\3+$)((?>\2?)\3)))^(1+)))*1$)
. Il est très facile de comprendre cette expression rationnelle et elle est élégante dans sa simplicité. Pour démontrer le contraste entre nos solutions, voici une version commentée et joliment imprimée (mais non modifiée) de sa regex:Essayez la regex .NET en ligne
Revenons maintenant à ma regex ECMAScript. Premièrement, le voici en format brut, sans espace ni commentaire:
^(?=(((?=(xx+?)\3+$)(x+)\4*(?=\4$))+(?!\3+$)(?=(xx(x*?))\5*$)x)(x+))(?=\1(x(x*))(?=\8*$)\6\9+$)(?=(.*)((?=\8*$)\5\9+$))(?=(x*?)(?=(x\11)+$)(?=\12\10|(x))(x(x*))(?=\15*$)(?=\11+$)\11\16+$)(?=(x(x*))(?=\17*$)\7\18+$)((?=(x*?(?=\17+$)(?=\17+?(?=((xx(x*))(?=\18+$)\22*$))(x+).*(?=\17$)\24*(?=\24$)(?!(xx+)\25*(?!\22+$)\25$)\22+$)((?=(x\7)+$)\15{2}\14|)))(?=.*(?=\24)x(x(x*))(?=\28*$)\23\29*$)(?=.*(x((?=\28*$)\22\29+$)))(.*(?!\30)\20|(?=.*?(?!x\20)(?=\30*$)(x(x*))(?=\33*$)(?=\31+$)\31\34+$).*(?=\33\21$)))+$
(remplacez
\14
par\14?
pour la compatibilité avec PCRE, .NET et pratiquement tous les autres goûts de regex autres que ECMAScript)Essayez-le en ligne!
Essayez-le en ligne! (version plus rapide de la regex avec 537 octets)
Et maintenant, un bref résumé de l'histoire derrière elle.
Au début, il était très peu évident, du moins pour moi, qu'il était même possible de faire correspondre des nombres premiers dans le cas général. Et après avoir résolu cela, la même chose s’appliquait aux puissances de 2. Et ensuite aux puissances des nombres composés. Et puis des carrés parfaits. Et même après avoir résolu ce problème, une multiplication généralisée semblait impossible au début.
Dans une boucle ECMAScript, vous ne pouvez suivre qu'un seul numéro qui change. ce nombre ne peut pas dépasser l'entrée et doit diminuer à chaque étape. Mon premier regex de travail pour faire correspondre les instructions de multiplication correctes A * B = C était de 913 octets et fonctionnait en factorisant A, B et C en leurs puissances principales - pour chaque facteur premier, diviser à plusieurs reprises la paire de facteurs de puissance premiers de A et C par leur base première jusqu'à ce que celui correspondant à A atteigne 1; celle qui correspond à C est ensuite comparée au facteur de puissance premier de B. Ces deux puissances du même nombre premier ont été "multiplexées" en un seul nombre en les additionnant; cela serait toujours séparable sans ambiguïté à chaque itération suivante de la boucle, pour la même raison que les systèmes de numération positionnelle fonctionnent.
La multiplication a été réduite à 50 octets en utilisant un algorithme complètement différent (auquel teukon et moi avons pu arriver indépendamment, bien que cela ne lui prenne que quelques heures et qu'il passe directement à cela, alors que cela m’a pris porté à mon attention qu’une méthode courte existait): pour A≥B, A * B = C le cas échéant uniquement si C est le plus petit nombre qui satisfait C≡0 mod A et CB mod A-1. (De manière pratique, l'exception de A = 1 ne nécessite aucune manipulation particulière dans regex, où 0% 0 = 0 donne une correspondance.) Je ne peux vraiment pas comprendre à quel point il est évident qu'une telle manière élégante de multiplier existe dans une telle saveur regex minimale. (Et l'exigence de A≥B peut être remplacée par une exigence voulant que A et B soient des puissances premières de même puissance. Pour le cas de A≥B, cela peut être prouvé à l'aide du théorème du reste chinois.)
S'il s'était avéré qu'il n'existait pas d'algorithme plus simple pour la multiplication, le nombre abondant regex serait probablement de l'ordre de dix mille octets ou plus (même en tenant compte du fait que j'ai utilisé l'algorithme de 913 octets jusqu'à 651 octets). Il fait beaucoup de multiplication et de division, et la regex ECMAScript n'a pas de sous-programmes.
Le 23 mars 2014, j'ai commencé à travailler sur le problème de l'abondance de nombres de manière tangentielle, en élaborant une solution à ce qui semblait être à l'époque un sous-problème: Identifier le facteur premier de la multiplicité la plus élevée, afin de pouvoir le diviser en N au début, laisser de la place pour faire les calculs nécessaires. À l'époque, cela semblait être une voie prometteuse. (Ma solution initiale a finalement été assez importante, à 326 octets, puis à 185 octets.) Mais le reste de la méthode esquissée par Teukon aurait été extrêmement compliquée, de sorte que j’ai pris un chemin assez différent. Il s'est avéré suffisant de séparer le plus grand facteur de puissance N, correspondant au plus grand facteur premier de N; faire cela pour le nombre le plus élevé de multiplicité aurait ajouté une complexité et une longueur inutiles à la regex.
Il restait à traiter la somme des diviseurs comme un produit de sommes au lieu d’une somme simple. Comme expliqué par teukon le 14 mars 2014:
Cela m'a coupé l'esprit de voir cela. Je n'avais jamais pensé à factoriser la somme aliquote de cette manière, et c'est cette formule plus que toute autre chose qui a rendu plausible la solvabilité de l'appariement de nombres abondants dans la regex ECMAScript.
En fin de compte, au lieu de rechercher un résultat d'addition ou de multiplication supérieur à N ou de vérifier qu'un résultat ainsi divisé par M est supérieur à N / M, je me suis tourné vers le test si le résultat de la division est inférieur à 1. Je suis arrivé à la première version de travail le 7 avril 2014.
L'historique complet de mes optimisations de golf de cette regex est sur github. À un moment donné, une optimisation a fini par ralentir considérablement la regex. À partir de ce moment, j'ai donc conservé deux versions. Elles sont:
regex pour faire correspondre les nombres abondants.txt
regex pour faire correspondre les nombres abondants - shortest.txt
Ces expressions rationnelles sont entièrement compatibles avec ECMAScript et PCRE, mais une optimisation récente impliquait l’utilisation d’un groupe de capture potentiellement non participant
\14
. Ainsi, en abandonnant la compatibilité PCRE et en passant\14?
à la modification,\14
elles peuvent toutes deux être réduites d’un octet.Voici la plus petite version, avec cette optimisation appliquée (le rendant uniquement ECMAScript), reformatée pour tenir dans un bloc de code StackExchange avec (généralement) aucun défilement horizontal requis:
la source
Python 2 ,
41 à40 octetsLa sortie s'effectue via le code de sortie , donc 0 est la vérité et 1 est la fausseté.
Essayez-le en ligne!
Comment ça marche
Après avoir réglé tous n , k et j à l'entrée de STDIN, nous entrons dans la en boucle. Ladite boucle se cassera dès que -k - 1 = ~ k ≥ 0 , c’est-à-dire que k ≤ -1 / k <0 .
Dans chaque itération, nous décrémentons d'abord j pour ne considérer que les diviseurs appropriés de n . Si j est un diviseur de n , on
n%j
obtient 0 et j >> n% j * n = j / 2 0 = j est soustrait de k . Cependant, si j ne divise pas n , iln%j
est positif, il enn%j*n
est de même pour n> log 2 j et j >> n% j * n = j / 2 n% j * n = 0 est soustrait de k .Pour les nombres abondants, k atteindra une valeur négative avant ou lorsque j devient 1 , car la somme des diviseurs appropriés de n est strictement supérieure à n . Dans ce cas, nous sortir de la en boucle et le programme se termine normalement.
Cependant, si n n’est pas abondant, j finit par atteindre 0 . Dans ce cas,
n%j
génère une erreur ZeroDivisionError et le programme se termine avec une erreur.la source
~k<0
est chic, mais je pense-1<k
aussi fait le tour;)Brachylog , 5 octets
Essayez-le en ligne!
Explication
la source
Gelée , 3 octets
Essayez-le en ligne!
Comment ça marche
la source
Python , 44 octets
Essayez-le en ligne!
la source
range(n)
. Ce module embêtant à zéroMathematica, 17 octets
Explication
la source
AbundantNumberQ
, cela permettrait d'économiser quelques octets :)05AB1E ,
54 octets-1 octet grâce à scottinet
Essayez-le en ligne! ou essayez de 0 à 100
la source
Retina ,
50 à45 octetsEntrée unaire , sortie
1
pour les nombres abondants,0
sinon.Il n'y a rien de spécifique à Retina dans cette solution. Ce qui précède est une regex .NET pure qui ne correspond qu’à des nombres abondants.
Essayez-le en ligne! (Suite de tests filtrant les entrées décimales avec la regex ci-dessus.)
la source
Retina , 34 octets
Le nombre d'octets suppose un codage ISO 8859-1.
Entrée unaire , sortie
1
pour les nombres abondants,0
sinon.Essayez-le en ligne!
Explication
Nous commençons par obtenir tous les diviseurs de l’entrée. Pour ce faire, nous revenons (
!
) tout chevauchement (&
correspondances) (M
) de l'expression rationnelle(1+)$(?<=^\1+)
. L'expression régulière correspond à un suffixe de l'entrée, à condition que toute l'entrée soit un multiple de ce suffixe (ce que nous garantissons en essayant d'atteindre le début de la chaîne en utilisant uniquement des copies du suffixe). En raison de la façon dont le moteur des expressions rationnelles recherche les correspondances, une liste de diviseurs par ordre décroissant (séparés par des sauts de ligne) apparaîtra.La scène elle-même correspond simplement à linefeeds (
¶
) et les supprime. Cependant, le1>
est une limite, qui saute le premier match. Cela ajoute donc efficacement tous les diviseurs, à l'exception de l'entrée elle-même. Nous nous retrouvons avec l'entrée sur la première ligne et la somme de tous les diviseurs appropriés sur la deuxième ligne.Enfin, nous essayons d’aligner au moins un de plus
1
sur la deuxième ligne que sur la première. Si c'est le cas, la somme des diviseurs appropriés dépasse l'entrée. Retina compte le nombre de correspondances de cette expression rationnelle, qui seront1
pour des nombres abondants et0
autres.la source
8086 Assemblée,
23282524 octetsNon assemblé:
Exemple de programme de test, test N = [12..1000]:
Sortie [2..1000]
Sortie [12500..12700]
Sortie [25100..25300]
Mises à jour:
la source
JLE
parJBE
doubler la plage de nombres que ceci peut tester avant que les débordements ne commencent à le faire donner des faux négatifs. Ensuite, au lieu de commencer à échouer à 12600 (somme aliquot 35760), il échouera à 25200 (somme aliquot 74744). Mieux encore, il faudrait également détecter l'indicateur de portage et le traiter comme un nombre abondant sans avoir à calculer la somme réelle> 16 bits.JC
ouJNC
pour déterminer si le nombre est abondant ou non.En fait , 5 octets
Essayez-le en ligne!
la source
05AB1E , 4 octets
Essayez-le en ligne!
Comment ça marche
Désolé de poster dans l'ancienne question, je parcourais simplement d'anciens posts pour m'entraîner et j'ai remarqué que ma solution était plus courte que la meilleure solution suivante 05AB1E.
la source
Sorry to post in old question
Ne t'inquiète pas pour ça! Je suis toujours heureux de voir des réponses à mes anciens défis, et c'est vraiment encourageant ici . :)PARI / GP , 15 octets
La variante
n->sigma(n,-1)>2
est malheureusement plus longue.la source
Java 8, 53 octets (beaucoup plus si vous incluez le code de cérémonie)
Essayez-le en ligne
Explication:
la source
return
si je ne me trompe pas, alors ce sera encore plus court:n->IntStream.range(1,n).filter(e->n%e<1).sum()>n
(pas à 100% si cela est correct, je ne programme presque jamais en Java 8). Bienvenue chez PPCG!n->java.util.stream.IntStream.range(1,n).filter(e->n%e<1).sum()>n
de 65 octets (en supposant que le paquet me soitPowershell,
51 à49 octetsJ'aimerais pouvoir enlever quelques crochets.
-2 grâce à AdmBorkBork, au lieu de ne pas compter l'entrée dans la plage initiale, nous en tenons compte lors de la vérification finale.
Boucle à travers gamme de
1..
la$i
nput, moins 1, trouver où (?
) modulo inverse de l' entrée par le nombre actuel est$true
(alias seulement 0) - alors-join
tous ces chiffres ensemble avec+
etiex
la chaîne résultante pour le calculer, puis voir si le la somme de ces parties est supérieure à l'entrée.la source
param($i)((1..$i|?{!($i%$_)})-join"+"|iex)-gt2*$i
MATL, 6 octets
Sorties 1 pour les nombres abondants, 0 sinon.
Comment ça marche
la source
QBIC , 22 octets
Ceci est une adaptation au test de primalité QBIC . Au lieu de compter les diviseurs et de vérifier s’il s’agit de moins de trois, cela fait la somme des diviseurs appropriés. Cela ne concerne que la moitié des cas
1 to n
, où le test de primalité est1 to n
complètement effectué.Explication:
la source
JavaScript (ES6), 33 octets
la source
Japt ,
9 76 octets2 octets sauvés grâce à ETHproductions. Sauvé 1 octet grâce à obarakon.
Essayez-le en ligne!
la source
â
est de 1 octet, au moins en Unicode (0xE2).â
consiste en un seul octet.â
un argument de vérité est donné, cela supprimera le nombre réel de la liste restante, vous pourrezâ1 x >U
donc sauvegarder quelques octets :-)<Uâ1 x
pour sauvegarder un octet. Japt ajoute leU
devant du programme.Cubix , 38 octets
Essayez-le ici
0I:
- établit la pile avec 0, n, n (s, n, d)^
- commence la boucle)?
- décrémente d et teste pour 0. 0 quitte la boucle%?
- mod contre n et teste. 0 provoque la;rrw+s;rU
rotation de s vers le haut et l'ajout de d, la rotation de s vers le bas et rejoint la boucle;<
- Nettoyez et rejoignez la boucle.En boucle de sortie
;<
- Enlevez d de la pile et redirigez-?
- Enlevez n de s et testez,LOU@
tournez à gauche, sorties et sorties, les négatifs0O@
poussent à zéro, sortez et sortez . les positifs;O
éliminent la différence et sortent n. Le chemin passe ensuite à gauche et mène à la@
sortie.la source
Pure Bash, 37 octets
Merci à @Dennis d’avoir réorganisé le code, ce qui a permis d’économiser 6 octets et d’éliminer toute sortie accessoire vers stderr.
L'entrée est passée en argument.
La sortie est renvoyée dans le code de sortie: 0 pour abondant, 1 pour non abondant.
La sortie vers stderr doit être ignorée.
Tests effectués:
la source
RProgN , 8 octets
A expliqué
Essayez-le en ligne!
la source
Lot, 84 octets
Sorties
-1
pour un nombre abondant,0
sinon. Fonctionne en soustrayant tous les facteurs de2n
, puis en décalant le résultat 31 endroits pour extraire le bit de signe. Formulation alternative, également 84 octets:Sorties
1
pour un nombre abondant. Fonctionne en soustrayant tous les facteurs den
, puis en comparant le résultat à-n
. (set/a
C’est la seule façon pour Batch de faire de l’arithmétique, je ne peux donc pas régler facilement la boucle.)la source
Perl 6,
7224 octets1..a
.a
.a
.Merci à @ b2gills.
la source
$^a
après le premier peut être réduite à juste$a
. mais il est même plus court si vous l'écrivez ainsi:{$_ <sum grep $_%%*,^$_}
[+](LIST)
J, 19 octets
Merci à Conor O'Brien de l'avoir coupé à 19 octets!
<[:+/i.#~i.e.]%2+i.
Précédent: (34 octets)
f=:3 :'(+/((i.y)e.y%2+i.y)#i.y)>y'
Retourne 1 s'il est abondant et 0 s'il ne l'est pas.
Sortie:
la source
f=:
dans le nombre d'octets. En outre, vous pouvez descendre à 19 en convertissant en un verbe tacite:<[:+/i.#~i.e.]%2+i.
(f g h) y' is the same as
(fy) g (hy). When
f` est une casquette,([: g h) y
est à peu près la même chose queg h y
. En ce qui concerne~
, cela change les arguments gauche et droit. Il est important de savoir qu’il~
ne s’agit pas d’un verbe mais bien d’un adverbe. Cela modifie un verbe. Par exemple, nous pourrions avoir quelque chose comme2 %~ 8
. Ici,~
modifie%
pour changer ses arguments, donc l'expression est équivalente à8 % 2
.#~
est évalué après que les verbes à sa droite sont exécutés, donc l'argument de gauche devient le résultat à droitePyth, 11 octets
Vieux:
Je ne peux pas l'utiliser
!%
comme un pfn#
, parce que c'est deux fonctions. Me rend triste :(.la source
>sPf!%QTS
k ,
19 1615 octetsRetourne
1
pour vrai et0
pour faux.Essayez-le en ligne!
la source
PowerShell , 43 octets
Essayez-le en ligne!
la source
Common Lisp, 63 octets
Essayez-le en ligne!
la source
F #, 51 octets
Essayez-le en ligne!
Filtre tous les nombres qui ne se divisent pas de manière égale
n
, puis les additionne et les comparen
.la source