Étant donné un entier N > 1, affichez tous les autres nombres dont les décompositions principales ont les mêmes chiffres que la décomposition principale de N.

Par exemple, si N = 117, alors la sortie doit être [279, 939, 993, 3313, 3331], car

117 = 3 × 3 × 13

Par conséquent, les chiffres disponibles sont 1, 3, 3et 3et nous avons

279  = 3 × 3 × 31
939  = 3 × 313
993  = 3 × 331
3313 = 3313
3331 = 3331

Ce sont les seuls autres nombres possibles, car une autre combinaison de ces chiffres donne des entiers non premiers, qui ne peuvent pas être le résultat d'une factorisation principale.

Si Nest l' un des 117, 279, 939, 993, 3313ou3331 , la sortie contiendra les cinq autres chiffres: ils sont copains premiers facteurs.

Vous ne pouvez pas utiliser de zéros non significatifs pour obtenir des nombres premiers, par exemple pour N = 107, son seul copain est 701( 017n'est pas pris en compte).

Entrées et sorties

• Les copains d'entrée et de sortie doivent être pris et renvoyés dans la base décimale.

• Nsera toujours strictement supérieur à 1.

• La sortie peut être formatée assez librement, tant qu'elle ne contient que les copains et les séparateurs / éléments syntaxiques de liste.

• L'ordre de la sortie est sans importance.

• Vous pouvez prendre l'entrée à travers STDIN, comme un argument de fonction ou quelque chose de similaire.

• Vous pouvez imprimer la sortie dans STDOUT, la renvoyer à partir d'une fonction ou quelque chose de similaire.

Cas de test

Votre programme devrait résoudre l'un des cas de test ci-dessous en moins d'une minute .

N        Buddies
2        []
4        []
8        []
15       [53]
16       []
23       [6]
42       [74, 146, 161]
126      [222, 438, 483, 674, 746, 851, 1466, 1631, 1679]
204      [364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547]

Notation

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

Gelée , 14 octets

ÆfVṢṚḌ
ÇÇ€=ÇTḟ

Le temps d'exécution pourrait être réduit de moitié avec DFau lieu de V, mais il complète toujours les cas de test combinés en moins de trente secondes.

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

Comment ça marche

ÆfVṢṚḌ   Helper link. Argument: k (integer)

Æf       Decompose k into an array of primes with product k.
  V      Eval. Eval casts a 1D array to string first, so this computes the integer
         that results of concatenating all primes in the factorization.
   Ṣ     Sort. Sort casts a number to the array of its decimal digits.
    Ṛ    Reverse. This yields the decimal digits in descending order.
     Ḍ   Undecimal; convert the digit array from base 10 to integer.


ÇÇ€=ÇTḟ  Main link. Argument: n (integer)

Ç        Call the helper link with argument n.
         This yields an upper bound (u) for all prime factorization buddies since
         the product of a list of integers cannot exceed the concatenated integers.
 ǀ      Apply the helper link to each k in [1, ..., u].
    Ç    Call the helper link (again) with argument n.
   =     Compare each result to the left with the result to the right.
     T   Truth; yield all 1-based indices of elements of [1, ..., u] (which match
         the corresponding integers) for which = returned 1.
      ḟ  Filter; remove n from the indices.

PowerShell v3 +, 450 octets

param($n)function f{param($a)for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$y=($x=@((f $n)-split'(.)'-ne''|sort))|?{$_-eq(f $_)}
$a,$b=$x
$a=,$a
while($b){$z,$b=$b;$a=$a+($a+$y|%{$c="$_";0..$c.Length|%{-join($c[0..$_]+$z+$c[++$_..$c.Length])};"$z$c";"$c$z"})|select -u}
$x=-join($x|sort -des)
$l=@();$a|?{$_-eq(f $_)}|%{$j=$_;for($i=0;$i-le$x;$i+=$j){if(0-notin($l|%{$i%$_})){if(-join((f $i)-split'(.)'|sort -des)-eq$x){$i}}}$l+=$j}|?{$_-ne$n}

Finalement!

PowerShell ne dispose d'aucun élément intégré pour la vérification de la primalité, la factorisation ou les permutations, donc cela est complètement roulé à la main. J'ai travaillé sur un tas de trucs d'optimisation pour essayer de réduire la complexité du temps à quelque chose qui s'adaptera aux restrictions du défi, et je suis heureux de dire que j'ai finalement réussi -

PS C:\Tools\Scripts\golfing> Measure-Command {.\prime-factors-buddies.ps1 204}

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 27
Milliseconds      : 114
Ticks             : 271149810
TotalDays         : 0.000313830798611111
TotalHours        : 0.00753193916666667
TotalMinutes      : 0.45191635
TotalSeconds      : 27.114981
TotalMilliseconds : 27114.981

Explication

Il se passe beaucoup de choses ici, donc je vais essayer de le décomposer.

La première ligne prend entrée $net définit un function, f. Cette fonction utilise la division d'essai cumulative pour obtenir une liste des facteurs premiers. C'est assez rapide pour les petites entrées, mais il est évident que le bourbier diminue si l'entrée est grande. Heureusement, tous les cas de test sont petits, c'est donc suffisant.

La ligne suivante obtient les facteurs de $n, -splits à chaque chiffre en ignorant les résultats vides (cela est nécessaire en raison de la façon dont PowerShell fait la correspondance des expressions rationnelles et de la façon dont il déplace le pointeur à travers l'entrée et est un peu ennuyeux à des fins de golf), puis sorts les résultats Dans l'ordre croissant. Nous stockons ce tableau de chiffres dans $x, et l'utilisons comme entrée d'un |?{...}filtre pour extraire uniquement ceux qui sont eux-mêmes premiers. Ces premiers chiffres sont stockés dans $ypour une utilisation ultérieure.

Nous avons ensuite divisé $xen deux volets. Le premier (c'est-à-dire le plus petit) chiffre est stocké dans $a, tandis que les autres sont transmis $b. S'il $xn'a qu'un seul chiffre, il $bsera vide / nul. Nous devons ensuite refaire la conversion $aen tableau, nous utilisons donc l'opérateur virgule comme pour le faire.

Ensuite, nous devons construire toutes les permutations possibles des chiffres. Cela est nécessaire pour que nos tests de division sautent plus tard un tas de chiffres et accélèrent les choses dans l'ensemble.

Tant qu'il reste un élément $b, nous décollons le premier chiffre $zet laissons le reste $b. Ensuite, nous devons accumuler dans $ale résultat de certains découpages et découpages de chaînes. Nous prenons $a+$ycomme concaténation de tableau, et pour chaque élément que nous construisons une nouvelle chaîne $c, puis boucle à travers $cl » .lengthet insérer $zdans toutes les positions, y compris préfixer $z$cet annexant $c$z, alors selecting que les -uéléments nique. C'est à nouveau concaténé avec le tableau $aet réenregistré dans $a. Oui, cela finit par se produire des choses loufoques, comme vous pouvez obtenir3333 une entrée117, qui n'est pas en fait une permutation, mais cela est beaucoup plus court que d'essayer de les filtrer explicitement, garantit que nous obtenons chaque permutation, et n'est que très légèrement plus lent.

Donc, a maintenant $aun tableau de toutes les permutations possibles (puis certaines) des chiffres du facteur. Nous devons redéfinir $xpour être notre limite supérieure des résultats possibles |sorten -desinsérant les chiffres dans l' ordre croissant et -joinen les regroupant. De toute évidence, aucune valeur de sortie ne peut être supérieure à ce nombre.

Nous avons défini notre tableau d'aide $lpour être un tableau de valeurs que nous avons vu précédemment. Ensuite, nous retirons toutes les valeurs $a(c'est-à-dire, ces permutations) qui sont premières, et entrons dans une boucle qui est le plus grand puits de temps de tout le programme ...

Chaque itération, nous bouclons de 0à notre limite supérieure $x, incrémentant par l'élément courant $j. Tant que la $ivaleur que nous considérons n'est pas un multiple d'une valeur précédente (c'est la 0-notin($l|%{$i%$_})section), c'est un candidat potentiel pour la sortie. Si nous prenons les facteurs $i, sorteux, et ils -equel $x, puis ajoutez la valeur à la canalisation. À la fin de la boucle, nous ajoutons notre élément actuel $jdans notre $ltableau pour une utilisation la prochaine fois, car nous avons déjà pris en compte toutes ces valeurs.

Enfin, nous nous attelons |?{$_-ne$n}à retirer ceux qui ne sont pas l'élément d'entrée. Ils sont tous laissés sur le pipeline et la sortie est implicite.

Exemples

PS C:\Tools\Scripts\golfing> 2,4,8,15,16,23,42,117,126,204|%{"$_ --> "+(.\prime-factors-buddies $_)}
2 --> 
4 --> 
8 --> 
15 --> 53
16 --> 
23 --> 6
42 --> 74 146 161
117 --> 279 939 993 3313 3331
126 --> 222 438 674 746 1466 483 851 1679 1631
204 --> 782 2921 3266 6233 3791 15833 2951 7037 364 868 8561 15491 22547 852 762 1626 692 548 1268 2654 3446 2474 5462 4742 5426 4274 14426 6542 6434 14642

CJam , 26 23 octets

{_mfs$:XW%i){mfs$X=},^}

Essayez-le en ligne

Explication

La concaténation de deux nombres donne toujours un résultat plus important que leur multiplication. Donc, le plus grand nombre que nous devons éventuellement considérer est le plus grand nombre que nous pouvons former à partir des chiffres de la factorisation principale de l'entrée, qui est juste tous les chiffres triés par ordre décroissant. Pour les nombres donnés, cette limite supérieure est facilement assez petite pour que nous puissions vérifier de manière exhaustive chaque nombre dans la plage pour savoir s'il s'agit d'un copain de facteur premier:

_mf    e# Duplicate input N and get a list of its prime factors.
s$     e# Convert the list to a (flattened) string and sort it.
:X     e# Store this in X for later.
W%     e# Reverse it. This is now a string repesentation of the largest 
       e# possible output M.
i)     e# Convert to integer and increment.
{      e# Get a list of all integers i in [0 1 ... M] for which the following
       e# block gives a truthy result.
  mf   e#   Get list of prime factors of i.
  s$   e#   Get a sorted list of the digits appearing in the factorisation.
  X=   e#   Check for equality with X.
},
^      e# Symmetric set difference: removes N from the output list.

05AB1E , 17 octets

Code:

ÒJ{©RƒNÒJ{®QN¹Ê*–

Explication:

Ò                  # Get the factorization with duplicates, e.g. [3, 3, 13]
 J                 # Join the array, e.g. 3313
  {©               # Sort and store in ©, e.g. 1333
    R              # Reverse the number, e.g. 3331. This is the upperbound for the range
     ƒ             # For N in range(0, a + 1), do...
      NÒ           # Push the factorization with duplicates for N
        J          # Join the array
         {         # Sort the string
          ®Q       # Check if equal to the string saved in ©
            N¹Ê    # Check if not equal to the input
               *   # Multiply, acts as a logical AND
                –  # If 1, print N

Utilise l' encodage CP-1252 . Essayez-le en ligne!

Pyth, 17

LSjkPb-fqyTyQSs_y

Suite de tests .

Utilise la même observation que celle du post de Martin .

Expansion:

LSjkPb        ##  Define a function y(b) to get the sorted string of digits
              ##  of the prime factors of b
    Pb        ##  prime factors
  jk          ##  join to a string with no separator
 S            ##  Sort

-fqyTyQSs_yQQ ##  Auto-fill variables
         _yQ  ##  get reversed value of y(input)
       Ss     ##  convert that string to a list [1 ... y(input)]
 fqyTyQ       ##  keep numbers T from the list that satisfy y(T)==y(input)
-           Q ##  remove the input from the result

JavaScript (ES6), 163 158 octets

Edit : Il a été précisé qu'un nombre premier tel que 23 devrait renvoyer [6] plutôt qu'un ensemble de résultats vide. 5 octets enregistrés en supprimant une règle désormais inutile qui empêchait - exprès - que cela se produise.

Le dernier cas de test est commenté afin que cet extrait de code s'exécute assez rapidement, bien qu'il devrait également se terminer en moins d'une minute.

let f =

n=>[...Array(+(l=(p=n=>{for(i=2,m=n,s='';i<=m;n%i?i++:(s+=i,n/=i));return s.split``.sort().reverse().join``})(n))+1)].map((_,i)=>i).filter(i=>i&&i-n&&p(i)==l)

console.log(JSON.stringify(f(2)));
console.log(JSON.stringify(f(4)));
console.log(JSON.stringify(f(8)));
console.log(JSON.stringify(f(15)));
console.log(JSON.stringify(f(16)));
console.log(JSON.stringify(f(23)));
console.log(JSON.stringify(f(42)));
console.log(JSON.stringify(f(126)));
//console.log(JSON.stringify(f(204)));

PHP 486 octets

pourrait probablement être plus court avec un algorithme qui n’est pas le cas dans le livre.
(mais j'aime le nombre d'octets actuel)

function p($n){for($i=1;$i++<$n;)if($n%$i<1&&($n-$i?p($i)==$i:!$r))for($x=$n;$x%$i<1;$x/=$i)$r.=$i;return $r;}function e($s){if(!$n=strlen($s))yield$s;else foreach(e(substr($s,1))as$p)for($i=$n;$i--;)yield substr($p,0,$i).$s[0].substr($p,$i);}foreach(e(p($n=$argv[1]))as$p)for($m=1<<strlen($p)-1;$m--;){$q="";foreach(str_split($p)as$i=>$c)$q.=$c.($m>>$i&1?"*":"");foreach(split("\*",$q)as$x)if(0===strpos($x,48)|p($x)!=$x)continue 2;eval("\$r[$q]=$q;");}unset($r[$n]);echo join(",",$r);

panne

// find and concatenate prime factors
function p($n)
{
    for($i=1;$i++<$n;)  // loop $i from 2 to $n
        if($n%$i<1      // if $n/$i has no remainder
            &&($n-$i    // and ...
                ?p($i)==$i  // $n!=$i: $i is a prime
                :!$r        // $n==$i: result so far is empty ($n is prime)
            )
        )
            for($x=$n;      // set $x to $n
                $x%$i<1;    // while $x/$i has no remainder
                $x/=$i)     // 2. divide $x by $i
                $r.=$i;     // 1. append $i to result
    return $r;
}

// create all permutations of digits
function e($s)
{
    if(!$n=strlen($s))yield$s;else  // if $s is empty, yield it, else:
    foreach(e(substr($s,1))as$p)    // for all permutations of the number w/o first digit
        for($i=$n;$i--;)            // run $i through all positions around the other digits
            // insert removed digit at that position and yield
            yield substr($p,0,$i).$s[0].substr($p,$i);
}

// for each permutation
foreach(e(p($n=$argv[1]))as$p)
    // create all products from these digits: binary loop through between the digits
    for($m=1<<strlen($p)-1;$m--;)
    {
        // and insert "*" for set bits
        $q="";
        foreach(str_split($p)as$i=>$c)$q.=$c.($m>>$i&1?"*":"");
        // test all numbers in the expression
        foreach(split("\*",$q)as$x)
            if(
                0===strpos($x,48)   // if number has a leading zero
                |p($x)!=$x          // or is not prime
            )continue 2; // try next $m
        // evaluate expression and add to results (use key to avoid array_unique)
        eval("\$r[$q]=$q;");
    }

// remove input from results
unset($r[$n]);

// output
#sort($r);
echo join(",",$r);

En fait, 27 octets

Cela utilise le même algorithme que Martin , Adnan , FryAmTheEggman et Dennis ont utilisé. Suggestions de golf bienvenues. Essayez-le en ligne!

`w"i$n"£MΣSR≈`╗╜ƒ;╝R`╜ƒ╛=`░

Ungolfing

          Implicit input n.
`...`╗    Define a function and store it in register 0. Call the function f(x).
  w         Get the prime factorization of x.
  "..."£M   Begin another function and map over the [prime, exponent] lists of w.
    i         Flatten the list. Stack: prime, exponent.
    $n        Push str(prime) to the stack, exponent times.
               The purpose of this function is to get w's prime factors to multiplicity.
  Σ         sum() the result of the map.
             On a list of strings, this has the same effect as "".join()
  SR≈       Sort that string, reverse it and convert to int.
╜ƒ        Now push the function stored in register 0 and call it immediately.
           This gives the upper bound for any possible prime factor buddy.
;╝        Duplicate this upper bound and save a copy to register 1.
R         Push the range [0..u]
`...`░    Filter the range for values where the following function returns a truthy.
           Variable k.
  ╜ƒ        Push the function in register 0 and call it on k.
  ╛=        Check if f(k) == f(n).
          Implicit return every value that is a prime factor buddy with n, including n.

Powershell, 147 octets (version CodeGolf)

param($n)filter d{-join($(for($i=2;$_-ge$i*$i){if($_%$i){$i++}else{"$i"
$_/=$i}}if($_-1){"$_"})|% t*y|sort -d)}2..($s=$n|d)|?{$_-$n-and$s-eq($_|d)}

Remarque: Le script résout les derniers cas de test de moins de 3 minutes sur mon ordinateur portable local. Voir la solution "performance" ci-dessous.

Script de test moins golfé:

$g = {

param($n)
filter d{                       # in the filter, Powershell automatically declares the parameter as $_
    -join($(                    # this function returns a string with all digits of all prime divisors in descending order
        for($i=2;$_-ge$i*$i){   # find all prime divisors
            if($_%$i){
                $i++
            }else{
                "$i"            # push a divisor to a pipe as a string
                $_/=$i
            }
        }
        if($_-1){
            "$_"                # push a last divisor to pipe if it is not 1
        }
    )|% t*y|sort -d)            # t*y is a shortcut to toCharArray method. It's very slow.
}
2..($s=$n|d)|?{                 # for each number from 2 to number with all digits of all prime divisors in descending order
    $_-$n-and$s-eq($_|d)        # leave only those who have the 'all digits of all prime divisors in descending order' are the same
}

}

@(
    ,(2   ,'')
    ,(4   ,'')
    ,(6   ,23)
    ,(8   ,'')
    ,(15  ,53)
    ,(16  ,'')
    ,(23  ,6)
    ,(42  ,74, 146, 161)
    ,(107 ,701)
    ,(117 ,279, 939, 993, 3313, 3331)
    ,(126 ,222, 438, 483, 674, 746, 851, 1466, 1631, 1679)
    ,(204 ,364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547)
) | % {
    $n,$expected = $_

    $sw = Measure-Command {
        $result = &$g $n
    }

    $equals=$false-notin(($result|%{$_-in$expected})+($expected|?{$_-is[int]}|%{$_-in$result}))
    "$sw : $equals : $n ---> $result"
}

Sortie:

00:00:00.0346911 : True : 2 --->
00:00:00.0662627 : True : 4 --->
00:00:00.1164648 : True : 6 ---> 23
00:00:00.6376735 : True : 8 --->
00:00:00.1591527 : True : 15 ---> 53
00:00:03.8886378 : True : 16 --->
00:00:00.0441986 : True : 23 ---> 6
00:00:01.1316642 : True : 42 ---> 74 146 161
00:00:01.0393848 : True : 107 ---> 701
00:00:05.2977238 : True : 117 ---> 279 939 993 3313 3331
00:00:12.1244363 : True : 126 ---> 222 438 483 674 746 851 1466 1631 1679
00:02:50.1292786 : True : 204 ---> 364 548 692 762 782 852 868 1268 1626 2474 2654 2921 2951 3266 3446 3791 4274 4742 5426 5462 6233 6434 6542 7037 8561 14426 14642 15491 15833 22547

Powershell, 215 octets (version "Performance")

param($n)$p=@{}
filter d{$k=$_*($_-le3e3)
($p.$k=-join($(for($i=2;!$p.$_-and$_-ge$i*$i){if($_%$i){$i++}else{"$i"
$_/=$i}}if($_-1){($p.$_,"$_")[!$p.$_]})-split'(.)'-ne''|sort -d))}2..($s=$n|d)|?{$_-$n-and$s-eq($_|d)}

Remarque: Je pense que les exigences de performances sont en conflit avec le principe GodeGolf. Mais puisqu'il y avait une règle Your program should solve any of the test cases below in less than a minute, j'ai fait deux changements pour satisfaire la règle:

• -split'(.)'-ne''à la place, le code court |% t*y;
• une table de hachage pour encaisser les chaînes.

Chaque changement réduit de moitié le temps d'évaluation. Veuillez ne pas penser que j'ai utilisé toutes les fonctionnalités pour améliorer les performances. Ces derniers étaient suffisants pour satisfaire à la règle.

Script de test moins golfé:

$g = {

param($n)
$p=@{}                          # hashtable for 'all digits of all prime divisors in descending order'
filter d{                       # this function returns a string with all digits of all prime divisors in descending order
    $k=$_*($_-le3e3)            # hashtable key: a large hashtable is not effective, therefore a key for numbers great then 3000 is 0
                                # and string '-le3e3' funny
    ($p.$k=-join($(             # store the value to hashtable
        for($i=2;!$p.$_-and$_-ge$i*$i){
            if($_%$i){$i++}else{"$i";$_/=$i}
        }
        if($_-1){
            ($p.$_,"$_")[!$p.$_] # get a string with 'all digits of all prime divisors in descending order' from hashtable if it found
        }
    )-split'(.)'-ne''|sort -d)) # split each digit. The "-split'(.)-ne''" code is faster then '|% t*y' but longer.
}
2..($s=$n|d)|?{                 # for each number from 2 to number with all digits of all prime divisors in descending order
    $_-$n-and$s-eq($_|d)        # leave only those who have the 'all digits of all prime divisors in descending order' are the same
}

}

@(
    ,(2   ,'')
    ,(4   ,'')
    ,(6   ,23)
    ,(8   ,'')
    ,(15  ,53)
    ,(16  ,'')
    ,(23  ,6)
    ,(42  ,74, 146, 161)
    ,(107 ,701)
    ,(117 ,279, 939, 993, 3313, 3331)
    ,(126 ,222, 438, 483, 674, 746, 851, 1466, 1631, 1679)
    ,(204 ,364,548,692,762,782,852,868,1268,1626,2474,2654,2921,2951,3266,3446,3791,4274,4742,5426,5462,6233,6434,6542,7037,8561,14426,14642,15491,15833,22547)
) | % {
    $n,$expected = $_

    $sw = Measure-Command {
        $result = &$g $n
    }

    $equals=$false-notin(($result|%{$_-in$expected})+($expected|?{$_-is[int]}|%{$_-in$result}))
    "$sw : $equals : $n ---> $result"
}

Sortie:

00:00:00.0183237 : True : 2 --->
00:00:00.0058198 : True : 4 --->
00:00:00.0181185 : True : 6 ---> 23
00:00:00.4389282 : True : 8 --->
00:00:00.0132624 : True : 15 ---> 53
00:00:04.4952714 : True : 16 --->
00:00:00.0128230 : True : 23 ---> 6
00:00:01.4112716 : True : 42 ---> 74 146 161
00:00:01.3676701 : True : 107 ---> 701
00:00:07.1192912 : True : 117 ---> 279 939 993 3313 3331
00:00:07.6578543 : True : 126 ---> 222 438 483 674 746 851 1466 1631 1679
00:00:50.5501853 : True : 204 ---> 364 548 692 762 782 852 868 1268 1626 2474 2654 2921 2951 3266 3446 3791 4274 4742 5426 5462 6233 6434 6542 7037 8561 14426 14642 15491 15833 22547

Japt, 18 octets

k –
Ôn õ f@¥Xk ¬ñ

Essayez-le