Échangez les principaux exposants avec leurs voisins

13

(Suivi de ma question sur l' échange de bits avec leurs voisins .)

Tâche

Étant donné un entier positif x = (2 a  · 3 b ) · (5 c  · 7 d ) · (11 e  · 13 f ) ·… , imprimer l'entier obtenu en échangeant les exposants de cette factorisation pour chaque paire successive de nombres premiers, y = (2 b  · 3 a ) · (5 d  · 7 c ) · (11 f  · 13 e ) ·…

A061898 dans l'OEIS. Il s'agit de , donc le programme le plus court (en octets) gagne!

Cas de test

1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871
Lynn
la source
Pouvons-nous retourner True au lieu de 1 ?
Dennis
@Dennis Après mûre réflexion, j'ai décidé que ma réponse était non. La sortie doit au moins ressembler à un nombre.
Lynn

Réponses:

6

Gelée , 10 octets

ÆE;0s2UFÆẸ

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

Comment ça fonctionne

ÆE;0s2UFÆẸ  Main link. Argument: n

ÆE          Yield the exponents of n's prime factorization.
  ;0        Append a zero.
    s2      Split into pairs.
      U     Upend; reverse each pair.
       F    Flatten the resulting list of pairs.
        ÆẸ  Convert the prime exponents to integer.
Dennis
la source
4

Gelée, 17 16 11 octets

5 octets grâce à Dennis.

ÆfÆC’^1‘ÆNP

Essayez-le en ligne!

Explication

ÆfÆC’^1‘ÆNP   Main monadic chain. Argument: n

Æf            Yield the prime factors of n.
  ÆC          For each factor, count the number of primes below it.
              This effectively yields their indices.
    ’         Decrement [each] by 1.
     ^1       Xor with 1
       ‘      Increment [each] by 1.
        ÆN    Find their corresponding primes.
          P   Yield their product.

Version précédente de 16 octets

ÆnÆRiЀÆf’^1‘ÆNP

Essayez-le en ligne!

Explication

ÆnÆRiЀÆf’^1‘ÆNP   Main monadic chain. Argument: n

Æn                 Yield the next prime from n.
  ÆR               Yield all primes from 2 to it.
       Æf          Yield prime factors of n
    iЀ            Yield their index in the prime list.
         ’         Decrement [each] by 1.
          ^1       Xor with 1
            ‘      Increment [each] by 1.
             ÆN    Find their corresponding primes.
               P   Yield their product.

Version précédente de 17 octets:

ÆnÆR©iЀÆf’^1‘ị®P

Essayez-le en ligne!

Explication

ÆnÆR©iЀÆf’^1‘ị®P   Main monadic chain. Argument: n

Æn                  Yield the next prime from n.
  ÆR                Yield all primes from 2 to it.
    ©               Store to register.
        Æf          Yield prime factors of n
     iЀ            Yield their index in the prime list.
          ’         Decrement [each] by 1.
           ^1       Xor with 1
             ‘      Increment [each] by 1.
              ị®    Find their corresponding primes in
                    the list in register.
                P   Yield their product.
Leaky Nun
la source
3

Mathematica, 70 69 octets

1##&@@(Prime[BitXor[PrimePi@#+1,1]-1]^#2&)@@@FactorInteger@#/._@_->1&

Une fonction sans nom qui prend et retourne un entier. Il renvoie une erreur en entrée 1mais calcule toujours le résultat correct.

Explication

Comme d'habitude, en raison de tout le sucre syntaxique, l'ordre de lecture est un peu drôle. Un &sur les définit à droite une fonction sans nom et ses arguments sont désignés par #, #2, #3, etc.

...FactorInteger@#...

Nous commençons par factoriser l'entrée. Cela donne une liste de paires, {prime, exponent}par exemple l'entrée 12donne {{2, 2}, {3, 1}}. Un peu gênant, 1donne {{1, 1}}.

(...&)@@@...

Cela applique la fonction de gauche à la liste des entiers au niveau 1, c'est-à-dire que la fonction est appelée pour chaque paire, en passant le premier et l'exposant en tant qu'arguments séparés, puis renvoie une liste des résultats. (Cela revient à mapper la fonction sur la liste, mais recevoir deux arguments distincts est plus pratique que recevoir une paire.)

...PrimePi@#...

Nous calculons le nombre de nombres premiers jusqu'à et y compris l'entrée (principale) à l'aide de la fonction intégrée PrimePi. Cela nous donne l'indice du premier.

...BitXor[...+1,1]-1...

Le résultat est incrémenté, XOR avec 1et décrémenté à nouveau. Ces swaps 1 <-> 2, 3 <-> 4, 5 <-> 6, ..., c'est-à-dire tous les indices basés sur 1. Notez que l'entrée 1donnera 0pour PrimePilaquelle est ensuite mappé -1dans ce processus. Nous y reviendrons plus tard.

 ...Prime[...]^#2...

Nous obtenons maintenant le n ème premier (où n est le résultat du calcul précédent), qui est le premier correctement échangé, et le portons à la puissance du premier original dans la factorisation de l'entrée. À ce stade Prime[-1], une erreur sera lancée, mais elle se renverra sans évaluation. Dans ce cas, la puissance est 1telle que l'ensemble du processus jusqu'à présent donne {Prime[-1]}une entrée 1et une liste de puissances principales correctes pour toutes les autres entrées.

 1##&@@...

Ensuite, nous multiplions simplement tous les pouvoirs principaux. 1##&est une astuce de golf standard pour la Timesfonction. Voir cette astuce (section "Séquences d'arguments") pour savoir comment cela fonctionne.

Enfin, nous devons prendre soin de la contribution 1pour laquelle tout ce qui précède a abouti Prime[-1]. Nous pouvons facilement résoudre ce problème avec une simple règle de remplacement. N'oubliez pas que f@xc'est court pour f[x]. Nous voulons juste faire correspondre n'importe quelle expression de cette forme (puisque tous les autres résultats seront des entiers, c'est-à-dire des expressions atomiques), et le remplacer par un 1:

.../._@_->1

Ici, /.est l'abréviation de ReplaceAll, _@_est un modèle pour n'importe quoi de la forme f[x](c'est-à-dire toute expression composée avec un seul enfant) et ->1dit "remplacer par 1".

Martin Ender
la source
3

Python 2, 149 139 octets

10 octets grâce à Dennis.

n=input()
p=f=1;w=[2]
while w[-1]<=n:f*=p;p+=1;w+=[p]*(-~f%p<1)
r=p=1;w=w[1:]
while n>1:
    p+=1
    while n%p<1:n/=p;r*=w[w.index(p)^1]
print r
Leaky Nun
la source
input()fonctionne en Python 2?
NoOneIsHere
@NoOneIsHere Oui, c'est l'équivalent de eval(input())Python 3.
Mego
2

MATL , 17 octets

EZqGYfy&mt2\Eq+)p

Essayez-le en ligne!

Explication

Cela n'utilise pas directement les exposants. Au lieu de cela, il échange chaque facteur premier (éventuellement répété) par le premier suivant ou le premier précédent.

EZq    % Implicit input. Multiply by 2
Zq     % Array with sequence of primes up to that (this is more than enough)
GYf    % Prime factors of input, with possible repetitions
y      % Duplicate array with sequence of primes
&m     % Indices of prime factors in the sequence of primes
t2\    % Duplicate, modulo 2. Gives 0 for even indices, 1 for odd
Eq     % Multiply by 2, add 1. Transforms 0 / 1 into -1 / 1 
+      % Add. This modifies the indices to perform the swapping
)      % Apply the new indices into the sequence of primes
p      % Product. Implicit display
Luis Mendo
la source
2

Julia, 64 octets

~=primes
!n=prod(t->(~3n)[endof(~t[1])+1$1-1]^t[2],factor(2n))/3

Essayez-le en ligne! Le dernier cas de test nécessite trop de mémoire pour TIO, mais je l'ai vérifié localement.

Comment ça fonctionne

Pour éviter l'entrée de casse spéciale 1 - le produit d'un dictionnaire vide n'est pas défini - nous multiplions l'entrée n par 2 et divisons le résultat final par sa paire 3 .

factor(2n)donne tous les exposants positifs des facteurs premiers de 2n comme dictionnaire. Lors de l'itération sur le dictionnaire, nous obtiendrons des paires clé-valeur / exposant principal. La fonction prodprendra ces paires, appliquera la fonction anonymet->... et retournera le produit des résultats.

Pour chaque paire t = (p, e) , endof(~t[1])ou endof(primes(t[1]))renvoie k , le nombre de nombres premiers inférieurs ou égaux à p , ce qui signifie que p est le k ème premier.

+1$1-1incrémentera k , XOR k + 1 avec 1 et décrémentera le résultat. Si k est impair, k + 1 est pair, donc le XOR augmente et le résultat final est k + 1 . Si k est pair, k + 1 est impair, donc le XOR diminue et le résultat final est k - 1 .

Enfin, nous calculons tous les nombres premiers inférieurs ou égaux à 3n avec (~3n)ou primes(3n)(le facteur premier le plus élevé de 2n est inférieur ou égal à n si n> 2 , et il y a toujours un premier entre n et 2n ), sélectionnez celui à l'indice k + 1 ou k - 1 , et élevez-le à la e e puissance avec ^t[2].

Dennis
la source
2

Python 2, 112 109 108 95 94 octets

f=lambda n,k=4,m=6,p=[3,2]:1/n or n%p[1]and f(n,k+1,m*k,m*m%k*[k]+p)or p[len(p)*2%4]*f(n/p[1])

Testez-le sur Ideone .

Comment ça fonctionne

Lorsque f est appelé, il calcule d'abord 1 / n . Si le résultat n'est pas nul, n est 1 et f renvoie 1 .

Si n> 1 , ce qui suit se produit.

  • Si n n'est pas divisible par p [1] (initialement 2 ), n%p[1]donne une valeur vraie et

    f(n,k+1,m*k,m*m%k*[k]+p)

    est appelé.

    Cette branche génère un nombre premier jusqu'à ce que l'avant-dernier divise également n . Pour ce faire, il utilise le corollaire suivant du théorème de Wilson .

    corollaire du théorème de Wilson

    À tout moment, m est égal à la factorielle de k - 1 (initialement 6 = 3! Et 4. À chaque itération, le résultat de m*m%k*[k]est ajouté à la liste des nombres premiers p . Par le corollaire, m*m%kest 1 si k est premier et 0 sinon, ceci ajoute k à p si et seulement si k est un nombre premier.

  • Si n est divisible par p [1] , n%p[1]donne 0 et

    p[len(p)*2%4]*f(n/p[1])

    est exécuté.

    Si p contient un nombre pair de nombres premiers, len(p)*2%4donnera 0 et le premier multiplicande prendra la valeur de p [0] . Si p contient un nombre impair de nombres premiers, len(p)*2%4donnera 2 et le premier multiplicande prendra la valeur de p [2] .

    Dans les deux cas, c'est le nombre premier dont les exposants doivent être échangés avec celui de p [1] , nous divisons donc n par p [1] (en diminuant l'exposant par 1 ) et en multipliant le résultat f(n/p[1])par le nombre premier correspondant (augmentant l'exposant par 1 ).

    Notez que f(n/p[1])réinitialise k , m et p à leurs valeurs par défaut. f(n/p[1],k,m,p)améliorerait l'efficacité, au prix de six octets supplémentaires.

Dennis
la source
1

Pyth, 25 octets

JfP_TSfP_ThQ*F+1m@Jx1xJdP

Suite de tests.

Explication

JfP_TSfP_ThQ*F+1m@Jx1xJdP

           Q    get input
          h     add one
      fP_T      find the first prime after it
     S          range from 1 to that prime
 fP_T           filter for the primes
J               assign to J

                        P  prime factorize input
                m      d   for each factor
                     xJ    find its index in J
                   x1      xor with 1
                 @J        find the corresponding entry in J
            *F+1           product of the whole list
Leaky Nun
la source
1

Julia, 155 131 127 octets

n->(x=[sort([merge([p=>0for p=primes(n+1)],factor(n))...]);1=>0];prod([x[i-1][1]^x[i][2]*x[i][1]^x[i-1][2]for i=2:2:endof(x)]))

Il s'agit d'une fonction anonyme qui accepte un entier et renvoie un entier. Pour l'appeler, affectez-le à une variable. Il nécessite une version Julia <0.5 car la fonctionnalité principale a été supprimée de Base en 0.5.

Non golfé:

function f(n::Int)
    # Create an array of pairs by merging the Dict created from factoring n
    # with all primes less than n+1 with a 0 exponent. Append an extra pair
    # to account for 1 and situations where x would otherwise have odd length.
    x = [sort([(merge([p=>0 for p in primes(n+1)], factor(n))...]); 1=>0]

    # Compute a^d * c^b, where a and c are primes with b and d as their
    # respective exponents.
    prod([x[i-1][1]^x[i][2] * x[i][1]^x[i-1][2] for i = 2:2:endof(x)])
end

Essayez-le en ligne! (Comprend tous les cas de test)

Alex A.
la source
1

En fait, 15 octets

w`i;r♂Pí1^Pn`Mπ

Essayez-le en ligne!

Explication:

w`i;r♂Pí1^Pn`Mπ
w                prime factorization
 `          `M   map (for (p,e) in factorization):
  i;               flatten, make a copy of p
    r♂P            [prime[i] for i in range(p)]
       í           index (essentially the 0-based prime index of p)
        1^         XOR with 1
          P        prime[n]
           n       repeat e times
              π  product
Mego
la source
1

05AB1E, 22 octets

Ó¾‚˜2ô€R˜DgL<Ø)øvy`smP

Expliqué

Ó¾‚˜                    # list of primeexponents with a 0 appended: n=10 -> [1,0,1,0] 
    2ô                  # split into pairs: [[1,0],[1,0]]
      €R˜               # reverse each pair and flatten: [0,1,0,1]
         DgL<Ø          # get list of primes corresponding to the exponents: [2,3,5,7]
              )ø        # zip lists: [[0,2],[1,3],[0,5],[1,7]]
                vy`sm   # raise each prime to its new exponent: [1,3,1,7]
                     P  # product: 21

Essayez-le en ligne

Emigna
la source
0

J, 21 octets

([:,_2|.\,&0)&.(_&q:)

Obtient les principaux exposants de n en tant que puissances principales avec des zéros. Ensuite, partitionnez-les en sous-listes non superposées de taille 2 tout en remplissant avec un zéro supplémentaire. Inversez ensuite chaque sous-liste et aplatissez-les dans une liste. Enfin, reconvertissez des exposants principaux en nombre.

Usage

   f =: ([:,_2|.\,&0)&.(_&q:)
   (,.f"0) 1 2 3 10 37 360 12345
    1     1
    2     3
    3     2
   10    21
   37    31
  360   756
12345 11578
   f 67895678x
125630871

Explication

([:,_2|.\,&0)&.(_&q:)  Input: n
                _&q:   Obtain the list of prime exponents
(           )&.        Apply to the list of prime exponenets
         ,&0           Append a zero to the end of the list
    _2  \              Split the list into nonoverlapping sublists of size 2
      |.               Reverse each sublist
 [:,                   Flatten the list of sublists into a list
             &.(    )  Apply the inverse of (Obtain the list of prime exponents)
                       to convert back to a number and return it
miles
la source