Déterminer la surabondance

21

Un nombre surabondant est un entier n qui définit une nouvelle borne supérieure pour son rapport avec la fonction de somme des diviseurs σ. En d'autres termes, n est surabondant si et seulement si, pour tous les entiers positifs x inférieurs à n :

σ(n)n>σ(x)x

Pour quelques-unes des valeurs:

n   σ(n)   σ(n)/n   superabundant
1   1      1.0000   yes
2   3      1.5000   yes
3   4      1.3333   no
4   7      1.7500   yes
5   6      1.2000   no
6   12     2.0000   yes
7   8      1.1429   no
8   15     1.8750   no
9   13     1.4444   no

Une liste plus longue de ceux-ci (pour les cas de test) peut être consultée sur OEIS A004394 .

Un cas de test négatif fortement recommandé (si votre interprète peut le gérer) est 360360, car il est lié au dernier numéro surabondant.

Défi

Votre programme doit prendre un seul entier positif et produire une valeur true ou falsey indiquant si cet entier est surabondant.

Comme il s'agit de code-golf , la réponse la plus courte en octets l'emporte.

code-golf number-theory decision-problem factoring Nissa
la source

Réponses:

7

Gelée , 7 octets

Æs÷$ÞṪ=

Essayez-le en ligne!

Gelée , 8 octets

Æs÷$ÐṀ⁼W

Essayez-le en ligne!

Suite de tests!

Explication

Æs ÷ $ ÐṀ⁼W ~ Programme complet (monadique).

    ÐṀ ~ Gardez les éléments avec une valeur de lien maximale (auto-rangifie).
Æs ~ Somme du diviseur.
  ÷ $ ~ Diviser par l'élément courant.
      ⁼W ~ Vérifiez l'égalité avec l'entrée enveloppée dans un singleton.
         ~ (pour des entiers comme 360360)
M. Xcoder
la source
Je pense que vous pouvez le faire Æs÷$ÐṀ=pour 7 octets. Je ne me suis pas rendu compte ÐṀrangifié, c'est utile de savoir.
dylnan
@dylnan Non, je ne peux pas. Bien qu'il ne puisse pas être testé en ligne, il échoue 360360. En fait, c'était ma version initiale
M. Xcoder
Pourquoi cela échouerait-il 360360?
dylnan
@dylnan 360360est le premier nombre pour lequel il échouerait (je pense), car c'est le premier nombre à égaler un résultat qui s'est produit auparavant. (et notre résultat serait [0, 1])
M. Xcoder
@ Mr.Xcoder je vois, merci
dylnan
5

Haskell , 73 octets

-1 octet merci à M. Xcoder. -7 octets grâce à Laikoni.

r=read.show
s n=sum[r i|i<-[1..n],n`mod`i<1]/r n
f n=all((s n>=).s)[1..n]

Essayez-le en ligne!

Le système de caractères de Haskell n'est pas très golfique ...

totalement humain
la source
4

Octave , 41 octets

@(n)([~,p]=max((x=1:n)*~mod(x,x')./x))==n

Essayez-le en ligne!

Explication

@(n)                                       % Define anonymous function of n
                x=1:n                      % Range from 1 to n. Call that x
                        mod(x,x')          % n×n matrix of all pair-wise moduli
                       ~                   % Logical negate. True means it's a divisor
               (     )*                    % Matrix-multiply x times the above matrix
                                           % (gives the dot product of vector x times
                                           % each column of the matrix)
                                 ./x       % Divide each column by each entry in x
     [~,p]=max(                     )      % Index of first occurrence of maximum
    (                                )==n  % Does it equal n?
Luis Mendo
la source
3

J , 35 octets

Merci à Mr.Xcoder pour avoir trouvé le problème et à cole pour le corriger!

[:([:*/{:>}:)@(%~>:@#.~/.~&.q:)1+i.

Essayez-le en ligne!

Galen Ivanov
la source
1
Cela échoue 360360(voir le défi pour plus de détails: un cas de test négatif fortement recommandé est 360360, car il est lié au dernier nombre surabondant. ).
M. Xcoder
1
Corrigé pour +3 octets. Essayez-le en ligne . Travailler sur le golf. J'aime beaucoup l'utilisation #.~(honnêtement, toute la fonction de somme des diviseurs est vraiment sympa). Ce qui n'allait pas, c'est que, bien que l'idée de faire {:=>./soit intelligente, elle ne satisfait pas la partie «supérieure à» de la question.
cole
1
Voici ce que je suis venu avec pour remplacer la fonction sigma, qui est à la même longueur actuellement: (1#.{:(]*0=|~)])\ . Quelque chose ne va pas, cependant, vous avez peut-être des idées?
cole
1
@cole Les crédits pour la fonction somme des diviseurs vont à Roger Hui, dans cet essai . J'ai également commencé à écrire une autre fonction sigma, mais j'ai arrêté après avoir atteint 9 octets et décidé qu'elle ne serait pas plus courte que celle avec la factorisation principale. Merci d'avoir résolu le problème!
Galen Ivanov,
@cole L'autre verbe le plus court pour la somme des diviseurs que j'ai trouvé est celui-ci: (1#.]*0=|~)1+i.c'est un crochet et ne rentre pas aussi facilement en place cependant :)
Galen Ivanov
3

Julia 0,6 , 52 octets

n->indmax(sum(x for x=1:m if m%x<1)//m for m=1:n)==n

Essayez-le en ligne!

Cette solution utilise des nombres rationnels pour garantir l'exactitude en cas d'égalité. (Le test du 360360 a pris près de 10 minutes.)

En virgule flottante, 2 octets peuvent être enregistrés avec la division de gauche:

n->indmax(m\sum(x for x=1:m if m%x<1)for m=1:n)==n
LukeS
la source
3

Pyth , 14 octets

( FryAmTheEggman a enregistré 1 octet)

qh.Mcs*M{yPZZS

Essayez-le ici! ou voir plus de cas de test.

Juste ma soumission Pyth obligatoire qui est très probablement jouable au golf.

Comment?

qh.Mcs * M {yPZZS ~ Programme complet. Q = entrée.

             S ~ Les entiers dans la plage [1, Q].
  .M ~ Récupère les éléments avec la valeur de fonction maximale.
    cs * M {yPZZ ~ Fonction clé: utilise une variable Z.
         yPZ ~ L'ensemble de puissance des facteurs premiers de Z.
        {~ Dédupliqué.
      * M ~ Produit de chacun.
     s ~ Et résumé.
    c Z ~ divisé par Z.
 h ~ Premier élément.
q ~ Vérifiez l'égalité avec l'entrée. Génère True ou False.
M. Xcoder
la source
3

05AB1E , 10 octets

LÑOā/ZQ¨_P

Essayez-le en ligne! ou comme suite de tests

Explication

L            # push range [1 ... input]
 Ñ           # divisors of each
  O          # sum of each
   ā/        # divide each by its 1-based index
     Z       # get max
      Q      # compare to each
       ¨     # remove the last element
        _    # logical negation
         P   # product
Emigna
la source
Je pense (bien que je ne sois pas sûr) que cela échoue 360360(voir le défi pour plus de détails: un cas de test négatif fortement recommandé est 360360, car il est lié au dernier nombre surabondant. ).
M. Xcoder
@ Mr.Xcoder: Vrai. Corrigé, mais il peut y avoir une meilleure façon de le faire maintenant.
Emigna
3

Python 3 , 77 octets

-1 octet grâce à Rod. -3 octets grâce à Dennis.

lambda n:max(range(1,n+1),key=lambda k:sum((k%i<1)/i for i in range(1,k)))==n

Essayez-le en ligne!

totalement humain
la source
2

R utilisant numbers, 59 octets

f=function(n)which.max(sapply(1:n,numbers::Sigma)/(1:n))==n
Joseph Wood
la source
2

Mathematica, 53 50 octets

a=Tr@Divisors@#/#&;AllTrue[a@#-Array[a,#-1],#>0&]&

Fonction pure. Prend un entier comme entrée et retourne Trueou Falsecomme sortie.

LegionMammal978
la source
Souhaitez-vous que quelque chose Tr@Divisors@#fonctionne?
user202729
1

Japt v2.0a0, 12 16 octets

Le cerveau privé de sommeil ne semble pas pouvoir encore améliorer cela!

Retourne 1pour véridique ou 0pour falsey.

Æâ x÷U >Xâ x÷XÃ×

Essayez-le

Sacrifié 4 octets à gérer 360360.

Explication

  • Saisie implicite d'entier U.
  • Æ Ãcrée un tableau d'entiers de 0à U-1et passe chacun par la fonction suivante en tant que X.
  • âobtient les diviseurs de U.
  • ÷Udivise chacun de ceux-ci par U.
  • x résume les résultats.
  • Xâobtient les diviseurs de X.
  • ÷Xdivise chacun de ceux-ci par X.
  • x résume les résultats.
  • > vérifie si le premier résultat est supérieur au second.
  • × réduit le tableau résultant de booléens par multiplcation.
Hirsute
la source
1
Si votre approche actuelle correspond à votre explication, elle échoue pour 360360ou d'autres tels entiers: Un cas de test négatif fortement recommandé (si votre interprète peut le gérer) est 360360, car il est lié au dernier nombre surabondant
M. Xcoder
@ Mr.XCoder: Noix, vous avez raison! Ça va probablement me coûter quelques octets quand j'aurai un moment pour le réparer.
Shaggy
@ Mr.Xcoder: corrigé pour l'instant, devra revenir plus tard pour voir si je peux l'améliorer.
Shaggy
0

APL + WIN, 37 octets

 ↑1=⍒⌽(+/¨((0=(⍳¨n)|¨n)×⍳¨n)~¨⊂0)÷n←⍳⎕

Invite à saisir l'écran.

Graham
la source
0

C (gcc), 99 octets

s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;n=k;}f(n,i,r){for(i=r=0;++i<n;)r=1.*s(n)/n<1.*s(i)/i?:r;r=!r;}

Essayez-le en ligne!

C, 108 octets

float s(n,j,k){for(j=k=0;j++<n;)k+=n%j?0:j;return k;}f(n,i,r){for(i=r=0;++i<n;)s(n)/n<s(i)/i&&++r;return!r;}

Essayez-le en ligne!

Steadybox
la source
Alors, pourquoi sfaut-il retourner un flotteur?
Nissa
@StephenLeppik Pour utiliser la division flottante au lieu de la division entière lors de la comparaison s(n)/navec s(i)/i.
Steadybox
0

Swift , 120 118 bytes

let s={n in Float((1...n).reduce(0){n%$1>0 ?$0:$0+$1})}
{n in(1..<n).reduce(0){max($0,s($1)/Float($1))}<s(n)/Float(n)}

Il faut un certain temps (environ 6 secondes sur TIO) pour compiler en raison des déclarations de type implicites dans Swift.

Essayez-le en ligne!

Herman L
la source
0

Funky , 79 octets

d=n=>fors=i=0i<=n i++s+=i*!n%i
f=n=>{forc=1c<n c++if(d(n)/n)<=d(c)/c return0 1}

Expliqué

Cela définit d'abord la fonction dqui est la σfonction, et ceci est la version golfée de

function d(n){
    var s = 0;
    for(var i=0; i<n; i++){
        if(n%i == 0){
            s += i;
        }
    }
    return s;
}

Nous pouvons mettre i à 0, car i*n%0sera toujours égal 0*..., donc 0.

La moitié suivante définit la fonction f, qui est la fonction Superabandunce, et ce n'est que la forme jouée au golf de

function f(n){
    for(var c=1; c<n; c++){
        if( (d(n)/n) <= (d(c)/c) ){
            return 0;
        }
    }
    return 1;
}

Et cela vérifie simplement, comme le suggère la spécification de défi, que tous les entiers de 1 à n-1 ont un d(n)/nde moins que l'entrée.

Essayez-le en ligne!

ATaco
la source
0

Coque , 9 octets

εü<m§ṁ/Ḋṫ

Essayez-le en ligne! Trop lent pour le cas de test 360360.

Explication

εü<m§ṁ/Ḋṫ  Implicit input, say n=6.
        ṫ  Decreasing range: [6,5,4,3,2,1]
   m       Map this function (example argument k=4):
       Ḋ    Divisors of k: [1,2,4]
    §ṁ      Map and sum
      /     division by k: 7/4
           Result: [2,6/5,7/4,4/3,3/2,1]
 ü         Remove duplicates by
  <        strict comparison. This greedily extracts a non-decreasing subsequence: [2]
ε          Is it a singleton list? Yes.
Zgarb
la source
J'ai compris £ü¤<§ṁ/ḊN. Création de la liste complète des nombres surabondants
H.PWiz
0

Perl 5, 84 octets

say!grep$a[-1]<=$a[$_],0..(@a=map{$i=$_;my$j;map{$i%$_ or$j+=$_/$i}1..$i;$j}1..<>)-2

a besoin -E (gratuit)

une mise en œuvre simple de la spécification, golfé

msh210
la source
0

APL (NARS), 61 caractères, 122 octets

r←f w;m;k
r←m←0
r+←1⋄k←r÷⍨11πr⋄→3×⍳r≥w⋄→2×⍳∼m<k⋄m←k⋄→2
r←k>m

11π est la fonction somme des facteurs

  (⍳9),¨ f¨1..9
1 1  2 1  3 0  4 1  5 0  6 1  7 0  8 0  9 0 
  f 360360
0
RosLuP
la source