Déterminez si un nombre est friable en 2017 sans nombres premiers dans votre code source

41

Sur toutes les années où je fais ce défi, 2017 est la première année qui a été un nombre premier. La question portera donc sur les nombres premiers et leurs propriétés.

Votre tâche consiste à créer un programme ou une fonction prenant un nombre entier positif arbitrairement élevé en entrée et en sortie ou en renvoyant, que le nombre soit ou non friable de 2 017 , c'est-à-dire que le plus grand facteur premier de ce nombre soit de 2 017 ou moins.


Quelques exemples d'entrées et leurs sorties:

1 (has no prime factors)
true

2 (= 2)
true

80 (= 2 x 2 x 2 x 2 x 5)
true

2017 (= 2017)
true

2019 (= 3 x 673)
true

2027 (= 2027)
false

11111 (= 41 x 271)
true

45183 (= 3 x 15061)
false

102349 (= 13 x 7873)
false

999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true

1234567 (= 127 x 9721)
false

4068289 (= 2017 x 2017)
true

Votre programme n'a pas à produire littéralement trueet false- toutes les valeurs de vérité ou de fausseté, et en fait, deux résultats différents qui sont cohérents entre les cas vrais et les cas faux sont acceptables.


Cependant, vous ne pouvez pas utiliser les nombres premiers dans votre code source. Les primes sont de deux types:

  • Caractères, ou séquences de caractères, qui représentent des littéraux en nombres premiers.

    • Les personnages 2, 3, 5et 7sont illégales dans les langues où les nombres sont des jetons valides.

    • Le nombre 141est illégal car il contient 41, même si 1et 4sont par ailleurs valables.

    • Les caractères Bet D(ou bet d) sont illégaux dans les langues où ils sont généralement utilisés comme 11 et 13, tels que CJam ou Befunge.

  • Caractères comportant des valeurs Unicode à valeurs principales ou contenant des octets dans leur codage.

    • Les caractères %)+/5;=CGIOSYaegkmqsont illégaux en ASCII, ainsi que le caractère de retour chariot.

    • Le caractère óest illégal en UTF-8 car son encodage en contient 0xb3. Cependant, dans ISO-8859-1, son codage est simple 0xf3, composite et donc correct.

Le code le plus court pour faire ce qui précède dans n'importe quelle langue gagne.

Joe Z.
la source
Note secondaire: "friable" est une amélioration adoptée par rapport au vieux "lisse" dans ce contexte.
Greg Martin
1
Les valeurs de vérité et de fausseté doivent-elles être cohérentes? Ou peuvent-ils varier aussi longtemps qu'ils sont la vérité ou la fausseté?
Luis Mendo
10
Le manque de =règles sur la plupart des langages standard ...
Neil
4
-1 pour un défi X sans Y. C'est vraiment assez trivial caché derrière un ensemble de restrictions de caractères plutôt inutiles
Downgoat
1
Je n'aime pas le fait qu'ils soient arbitrairement grands. Ce serait mieux s'ils montaient à 2 ^ 31-1.
Bijan

Réponses:

37

Gelée , 8 octets

44‘²!*ḍ@

Essayez-le en ligne! Notez que les cas de test 11111 et supérieurs sont un peu trop difficiles pour TIO.

Vérification

$ source="34,34,fc,82,21,2a,d5,40"
$ xxd -ps -r > 2017.jelly <<< $source
$ xxd -g 1 2017.jelly
0000000: 34 34 fc 82 21 2a d5 40                          44..!*.@
$ eval printf '"%d "' 0x{$source}; echo # Code points in decimal
52 52 252 130 33 42 213 64
$ test_cases="1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289"
$ for n in $test_cases; do printf "%11d: %d\n" $n $(jelly f 2017.jelly $n); done
      1: 1
      2: 1
     80: 1
   2017: 1
   2019: 1
   2027: 0
  11111: 1
  45183: 0
 102349: 0

Le cas de test 999999 a duré 13 heures. Je suis pessimiste à propos de l'informatique 2025! 4068289 ...

Comment ça marche

44‘²!*ḍ@  Main link. Argument: n

44        Yield 44.
  ‘       Increment to yield 45.
   ²      Square to yield 2025.
          Note that no integers in [2018, ..., 2025] are prime numbers.
    !     Take the factorial of 2025.
     *    Raise it to the n-th power.
          This repeats all prime factors in 2025! at least n times, so the result
          will be divisible by n if (and only if) all of its prime factors fall
          in the range [1, ..., 2025].
      ḍ@  Test the result for divisibility by n.
Dennis
la source
22
Vous êtes cruel envers les chiffres. :)
Greg Martin
3
@ GregMartin bah. J'ai vu une réponse (dans une langue différente) dans laquelle une entrée de taille 6 accaparerait la mémoire pendant plusieurs heures, puis se bloquerait. Je vais juste dire: (2^n)!. Cela nécessite également des entrées de six tailles, mais au moins les entrées sont dans un alphabet décimal plutôt que dans un alphabet binaire.
John Dvorak
N'est-ce pas 13 octets? Dennis, vous avez tellement de réputation que je suis sûr que c'est moi qui ai commis une erreur ici hahah 😬
Albert Renshaw
7
@AlbertRenshaw Il s'agirait bien de 13 octets dans UTF-8, mais Jelly utilise une page de code personnalisée qui code tous les caractères qu’elle comprend sous la forme d’un octet unique.
Dennis
3
@Dennis savait qu'il y aurait une explication; très cool d'apprendre, merci!
Albert Renshaw
11

Gelée , 8 caractères, 14 octets de UTF-8

Æf½ṀḤ<90

Essayez-le en ligne!

Jelly utilise normalement sa propre page de codes pour les programmes. Cependant, la plupart de ses composants principaux liés commencent par le Æcode 13; pas très utile. Heureusement, l'interprète prend également en charge UTF-8, qui offre un codage plus convivial.

Vérification

Ce programme, en UTF-8, hexdumps ressemble à ceci:

00000000: c386 66c2 bde1 b980 e1b8 a43c 3930  ..f........<90

Vérification que tous les octets sont composites:

$ for x in c3 86 66 c2 bd e1 b9 80 e1 b8 a4 3c 39 30; do factor $((0x$x)); done
195: 3 5 13
134: 2 67
102: 2 3 17
194: 2 97
189: 3 3 3 7
225: 3 3 5 5
185: 5 37
128: 2 2 2 2 2 2 2
225: 3 3 5 5
184: 2 2 2 23
164: 2 2 41
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

Vérification que tous les points de code Unicode sont composites:

$ perl -Mutf8 -E '$a = ord, print `factor $a` for split //, "Æf½ṀḤ<90"'
198: 2 3 3 11
102: 2 3 17
189: 3 3 3 7
7744: 2 2 2 2 2 2 11 11
7716: 2 2 3 643
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

Le seul jeton analysé en tant que nombre est 90. Aucun de 9, 0et 90sont premiers.

Explication

L’intérêt mathématique principal ici est que 45² correspond à 2025, ce qui se situe clairement entre 2017 (l’année en cours) et 2027 (le prochain nombre premier). Ainsi, nous pouvons prendre la racine carrée de chaque facteur premier du nombre et voir s'il en existe plus de 45. Malheureusement, nous ne pouvons pas écrire à 45cause du littéral 5, nous devons donc le doubler et comparer à 90 à la place.

Æf½ṀḤ<90
Æf        In the list of prime factors,
  ½       taking the square root of each element
   Ṁ      then taking the largest element
    Ḥ     and doubling it
     <90  produces a result less than 90.

la source
2
Jelly n’a-t-elle pas besoin d'un drapeau (1 octet) pour utiliser UTF-8?
Luis Mendo
@LuisMendo: l'interpréteur de ligne de commande le fait, mais l'interprète de Try It Online! est configuré différemment et ne l'exige pas. Il ne s'agit donc que de choisir l'interprète qui interprétera votre programme comme vous le souhaitez. (Dans tous les cas, le drapeau en question, uest composite, il s'agirait simplement de changer le score plutôt que de l'invalider.)
10

Mathematica, 62 58 55 octets

Les trois derniers octets enregistrés sont entièrement dus à Martin Ender!

#4<4||#<44*46&&#6[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&

Fonction sans nom prenant un argument entier positif et renvoyant Trueou False.

Algorithme récursif, avec #4<4être le cas de base de la vérité (nous n’avons besoin que de revenir Truesur l’imput 1, mais les cas de base supplémentaires sont corrects). Sinon, nous calculons le deuxième plus petit diviseur (qui est nécessairement premier) de l'entrée avec Divisors[#][[6-4]]; si elle est supérieure à 2024 ( 44*46) alors nous sortons avec False, sinon nous appelons la fonction récursive (en utilisant #6set to #0) sur l'entrée divisée par ce petit facteur premier #(que nous devons exprimer en tant que #^-1fois l'entrée #4, car non /autorisée).

Structurellement, la première moitié #4<4||#<44*46&&#6[#^-1#4]&est une fonction anonyme de six arguments, appelée avec des arguments Divisors[#][[6-4]], Null, Null, #, Null, et #0; est de contourner l'interdiction sur les personnages 2, 3et 5.

La version précédente, qui économisait quatre octets en remplaçant 8018-6000par 44*46, inspirée par la réponse de jelly d’ ais523 (Martin Ender semblait également inspirée par un commentaire d’ais523):

#<4||Divisors[#][[6-4]]<44*46&&#0[Divisors[#][[6-4]]^-1#]&

C'était assez méchant: je ne connais toujours pas le moyen de définir une variable dans Mathematica avec ces restrictions! Les deux =et le edans Setsont interdits. Éviter +et )était également un problème, mais pas trop difficile à contourner au détriment de plus d'octets.

Greg Martin
la source
Vous pourriez peut-être définir un paramètre lambda plutôt qu'une variable. (Cela dit, cela #2serait également interdit, vous devrez donc faire attention à la façon dont vos lambdas sont imbriqués, et le manque de parenthèses pourrait rendre cela difficile.)
La mise en œuvre de la suggestion de @ ais523 économise trois octets: elle #4<4||#<44*46&&#6[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&envoie une série d'avertissements, car elle tente maintenant de Divisors[#][[2]]s'assurer que l'entrée est supérieure à 1 (ou 3), mais le résultat est toujours correct.
Martin Ender
Oh mec, c'est de la ruse.
Greg Martin
7

Haskell, 48 à 47 octets

\n->[snd$[product[1..44*46]^n]!!0`divMod`n]<[1]

Fondamentalement, une traduction de la réponse de Dennis 'Jelly . xnor a sauvegardé un octet.

Utilise […]!!0entre parenthèses car )est interdit, et snd+ divModparce que mdans modet remest interdit.

Lynn
la source
Belle astuce avec le divMod! Je pense que vous pouvez remplacer le !!0<1avec <[1]. Mais il semble qu'il est court - circuité ce à l' utilisation divcomme [\p n->p^n`div`n*n>p^n-1]!!0$product[1..44*46].
xnor
Il y a aussi \n->[0|p<-[product[1..44*46]^n],0<-[p,p-n..0]], qui utilise que les sorties doivent seulement être cohérentes.
xnor
@xnor N'hésitez pas à les poster en tant que réponses séparées, je pense qu'elles sont suffisamment différentes des miennes ^^
Lynn
6

Pyke, 10 8 7 9 octets

P_Z|hwMX<

Essayez-le ici!

Sauvé 1 octet en utilisant la manière de Dennis de générer 2025

P         -     factors(input)
 _        -    reversed(^)
  Z|      -   ^ or 0
    h     -  ^[0] or 1
        < - ^ < V
     wM   -  ⁴45 (ord("M")-32)
       X  -  ^**2
Bleu
la source
5

Brachylog , 9 à 10 octets

*$ph$r*<90

Essayez-le en ligne!

Fondamentalement, en utilisant le même algorithme que mon autre réponse. $phtrouve le premier ( h) premier facteur ( $p); c'est le facteur le plus important, car les listes de facteurs premiers de Brachylog vont du plus grand au plus petit. Ensuite, je prends la racine carrée ( $r), double ( *) et teste pour voir si elle est inférieure à 90 ( <90).

J'ai dû doubler l'entrée en premier parce que 1 n'a pas de facteurs premiers (et donc pas de premier facteur premier). Cela ajoute un facteur premier supplémentaire de 2, qui n'affecte pas le fait qu'un nombre soit friable pour 2017, mais empêche une défaillance lors de la manipulation 1.


la source
5

En fait , 9 octets

τyM:44u²≥

Merci à Dennis pour beaucoup d'octets!

Essayez-le en ligne!

Explication:

τyM:44u²≥
τyM        largest prime factor of 2*input (doubled to deal with edge case of n = 1)
   :44u²   2025 (2027 is the next prime after 2017, so any number in [2017, 2026] can be used here - 2025 is very convenient)
        ≥  is 2025 greater than or equal to largest prime factor?
Mego
la source
5

Mathematica, 66 74 octets

Merci à Dennis pour avoir signalé que U+F4A1c'est interdit.

Fold[Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]],0<1,Divisors@#]&

Explication:

Divisors@#: Liste des diviseurs entiers du premier argument #.

0<1: Golf pour True(évite également l'utilisation de la lettre e).

Divisors@d^0: Liste des formulaires {1, 1, ..., 1}de longueur égale au nombre de diviseurs de d.

Tr: Pour une liste plate, Trretourne la somme de cette liste. Ainsi Tr[Divisors@d^0]retourne le nombre de diviseurs de d.

Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]: Fonction anonyme avec deux arguments xet d. L'idée est que dc'est un diviseur de #et nous testons pour voir si il est composite ou inférieur ou égal à 2017(inclus). 2017-fiabilité est équivalente à tous les diviseurs satisfaisant cette condition. Comme ais523 l’a découvert, être premier inférieur ou égal à 2017équivaut à être inférieur à premier 2025. Comme l’a souligné Greg Martin , il suffit de vérifier si elle est inférieure à 2024=44*46. L'argument xagit comme un accumulateur pour déterminer si tous les diviseurs rencontrés jusqu'ici satisfont cette propriété. Nous avons ensuite quitté Foldcette fonction à travers tous les diviseurs de #avec valeur initialeTrue, puisque nous n’avons accès ni à Mapni /@.

ngenisis
la source
1
Façon de se battre à travers les restrictions!
Greg Martin
2

05AB1E , 10 octets

fθ46n99-›È

Retourne 1 si vrai, 0 sinon.

Essayez-le en ligne!

Explication

f          # Push the list of prime factors (ordered)
 θ         # Get the last element
  46n99-   # Push 2017 (46² - 99)
        >  # Push 1 if the last prime factor is greater than 2017, 0 otherwise
         È # Is the resulting number even ? Transforms 1 to 0 and 0 to 1.
           # Implicit display
Kaldo
la source
Bienvenue chez PPCG!
Martin Ender
1

MATL , 15 octets

t:\~ftZp*44QU<A

Sorties 0pour non-2017-friables ou 1pour 2017-friables.

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

Ce programme vérifie que tous les octets sont composites.

Explication

t       % Implicit input n. Duplicate
:       % Range [1 2 ... n]
\       % Modulo. Gives 0 for divisors of n
~f      % Indices of zero values
t       % Duplicate
Zp      % Is-prime. Gives 1 for primes, 0 for composites
*       % Multiply
44QU    % 44, add 1, square: 2025
<       % Less than, element-wise
A       % True (1) if all entries are nonzero
Luis Mendo
la source
1

Bash, 144 octets

Codage ASCII:

{
printf '[ '
`tr D-Z _-z <<<KFH`tor $1|tr -d :|`tr B-Z _-z <<<JUH`p -o '[0-9]*$'
printf ' -lt $[24*86-46] ]'
}|tr \\n \ |`tr B-Z _-z <<<EDVK`

Comme d'habitude pour le shell, le code de sortie indique succès (0) ou échec (non-0).

C’est effectivement une orthographe différente de

[ factor $1|tr -d :|grep -o '[0-9]*$' -lt 2018 ]

Nous obtenons le facteur le plus important avec factor $1|grep -o '[0-9]*$'; le tr -d :est à cas particulier pour l'entrée = 1.

L'expression est $[6*6*69-466]évaluée à 2018.

Il était délicat à utiliser trpour les noms de commande et utilisait toujours la substitution de commande - je ne pouvais pas utiliser le formulaire d'imbrication $( ), alors j'ai fini par rediriger vers un autre Bash pour évaluer le résultat.

Résultats de test:

$ for i in 1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289; do printf '%d %s\n' $i `./105241.sh $i  && echo true || echo false`; done
1 true
2 true
80 true
2017 true
2019 true
2027 false
11111 true
45183 false
102349 false
999999 true
1234567 false
4068289 true

Confirmation des codes de caractères:

$ grep -v '^#' ./105241.sh | perl -n -Mutf8 -E '$a = ord, print `factor $a` for split //, $_' | grep -v ': .* ' | wc -l
0
Toby Speight
la source
0

Japt , 14 octets

k æ¨44*46 ?0:1

Retourne 1 si vrai, 0 si faux.

Essayez ici .

Oliver
la source
ka une valeur primordiale
Incarnation de l'Ignorance
0

Braingolf , 11 octets [très non compétitif]

VRp#ߢ-?0:1

Essayez-le en ligne!

Illisible en raison de la ߢvis avec les chiffres, fonctionne toujours dans un interprète.

Je n'ai même pas remarqué les restrictions de caractères lorsque j'ai écrit cela, mais tout ce que j'avais à faire, c'était de changer le caractère unicode étrange de 2017 à 2018.

2018 n’est pas un nombre premier, tout nombre <= 2018est également<= 2017

Explication

VRp#ߢ-?0:1  Implicit input from command-line args
VR            Create stack2, return to stack1
  p           Split last item into prime factors, push each one to stack in asc order
   #ߢ         Push 2018
     -      Subtract last 2 items (highest prime factor - 2017)
      ?     If last item > 0..
       0    ..push 1
        :   Else..
         1  ..Push 1
            Implicit output of last item on stack
Skidsdev
la source