Dado un número entero N > 1, genera todos los demás números cuyas descomposiciones primarias tienen los mismos dígitos que la descomposición primaria de N.

Por ejemplo, si N = 117, entonces la salida debe ser [279, 939, 993, 3313, 3331], porque

117 = 3 × 3 × 13

Por lo tanto, las cifras disponibles son 1, 3, 3y 3y tenemos

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

Esos son los únicos otros números posibles, porque otra combinación de estos dígitos produce enteros no primos, que no pueden ser el resultado de la factorización prima.

Si Nes cualquiera de 117, 279, 939, 993, 3313o 3331, a continuación, la salida contendrá los otros cinco números: son factores primos amigos.

No puede usar ceros a la izquierda para obtener primos, por ejemplo N = 107, porque su único amigo es 701( 017no se considera).

Entradas y salidas

• Los compañeros de entrada y salida deben tomarse y devolverse en la base decimal.

• Nsiempre será estrictamente mayor que 1.

• La salida puede formatearse con bastante libertad, siempre y cuando solo contenga los elementos sintácticos de lista y separadores / lista.

• El orden de la salida no es importante.

• Puede tomar la entrada STDIN, como un argumento de función o algo similar.

• Puede imprimir el resultado STDOUT, devolverlo desde una función o algo similar.

Casos de prueba

Su programa debe resolver cualquiera de los casos de prueba a continuación en menos de un minuto .

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]

Tanteo

Este es el código de golf , por lo que gana la respuesta más corta en bytes.

Jalea , 14 bytes

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

El tiempo de ejecución podría reducirse a la mitad en DFlugar de V, pero aún así completa los casos de prueba combinados en menos de treinta segundos.

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

Æ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 bytes

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}

¡Finalmente!

PowerShell no tiene funciones integradas para la comprobación de primalidades, la factorización o las permutaciones, por lo que esto se realiza completamente a mano. Trabajé en un montón de trucos de optimización para intentar reducir la complejidad del tiempo a algo que se ajuste a las restricciones del desafío, y estoy feliz de decir que finalmente lo logré:

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

Explicación

Están sucediendo muchas cosas aquí, así que intentaré analizarlo.

La primera línea toma la entrada $ny define una function, f. Esta función utiliza la división de prueba acumulativa para obtener una lista de los factores primos. Es bastante rápido para entradas pequeñas, pero obviamente se atasca si la entrada es grande. Afortunadamente, todos los casos de prueba son pequeños, por lo que es suficiente.

La siguiente línea obtiene los factores de $n, -splitson ellos en todos los dígitos ignorando ningún resultado vacíos (esto es necesario debido a la forma en PowerShell hace comparaciones de expresiones regulares y cómo se mueve el puntero a través de la entrada y es un poco molesto para jugar al golf propósitos), entonces sorts los resultados en orden ascendente. Almacenamos esa matriz de dígitos $xy la usamos como entrada para un |?{...}filtro para extraer solo aquellos que son primos. Esos dígitos primos se almacenan $ypara su uso posterior.

Luego nos dividimos $xen dos componentes. El primer dígito (es decir, el más pequeño) se almacena en $a, mientras que el resto se pasa a $b. Si $xsolo tiene un dígito, $bestará vacío / nulo. Luego tenemos que volver a emitir $acomo una matriz, por lo que utilizamos el operador de coma rápido para hacerlo.

Luego, necesitamos construir todas las permutaciones posibles de los dígitos. Esto es necesario para que nuestras pruebas de división luego se salten un montón de números y agilicen las cosas en general.

Mientras quede un elemento $b, quitamos el primer dígito $zy dejamos el resto $b. Luego, necesitamos acumular $ael resultado de un corte y corte de cadenas. Tomamos $a+$ycomo concatenación de matriz, y para cada elemento construimos una nueva cadena $c, luego hacemos un bucle a través de $c's' .lengthy la insertamos $zen cada posición, incluso antes $z$cy $c$zdespués, agregando selectsolo los -uelementos nique. Eso nuevamente se concatena con el conjunto $ay se vuelve a almacenar $a. Sí, esto termina teniendo cosas tontas, como si pudieras obtener 3333información117, que en realidad no es una permutación, pero esto es mucho más corto que intentar filtrarlos explícitamente, asegura que obtengamos cada permutación y es solo un poco más lento.

Entonces, ahora $atiene una matriz de todas las permutaciones posibles (y luego algunas) de los dígitos del factor. Necesitamos reestablecer $xpara ser nuestro límite superior de resultados posibles colocando |sortlos dígitos en -desorden descendente y -joinvolviéndolos a juntar. Obviamente, ningún valor de salida puede ser mayor que este número.

Configuramos nuestra matriz auxiliar $lpara que sea una matriz de valores que hemos visto anteriormente. A continuación, extraemos todos los valores de $a(es decir, esas permutaciones) que son primos, y entramos en un ciclo que es el mayor sumidero de tiempo de todo el programa ...

Cada iteración, estamos pasando 0a nuestro límite superior $x, incrementándonos por el elemento actual $j. Mientras el $ivalor que estamos considerando no sea un múltiplo de un valor anterior (esa es la 0-notin($l|%{$i%$_})sección), es un candidato potencial para la producción. Si tomamos los factores de $i, sortellos, y -eqUAL $x, a continuación, añadir el valor a la tubería. Al final del ciclo, agregamos nuestro elemento actual $jen nuestra $lmatriz para usar la próxima vez, ya que ya hemos considerado todos esos valores.

Finalmente, añadimos |?{$_-ne$n}aquellos que no son el elemento de entrada. Todos se quedan en la tubería y la salida es implícita.

Ejemplos

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 bytes

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

Pruébalo en línea

Explicación

Concatenar dos números siempre da un resultado mayor que multiplicarlos. Entonces, el número más grande que posiblemente debamos considerar es el número más grande que podemos formar a partir de los dígitos de la factorización prima de la entrada, que es solo todos los dígitos ordenados en orden descendente. Para los números dados, este límite superior es fácilmente lo suficientemente pequeño como para que podamos verificar exhaustivamente cada número en el rango para saber si es un amigo de factor primo:

_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 bytes

Código:

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

Explicación:

Ò                  # 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

Utiliza la codificación CP-1252 . Pruébalo en línea!

Pyth, 17

LSjkPb-fqyTyQSs_y

Banco de pruebas .

Utiliza la misma observación de la publicación de Martin .

Expansión:

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), 163158 bytes

Editar : Se ha aclarado que una prima como 23 debería devolver [6] en lugar de un conjunto de resultados vacío. Ahorró 5 bytes al eliminar una regla ahora inútil que, a propósito, evitaba que eso sucediera.

Se comenta el último caso de prueba para que este fragmento se ejecute lo suficientemente rápido, aunque también debería completarse en menos de un minuto.

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 bytes

probablemente podría ser más corto con un algoritmo que no es así según el libro.
(pero me gusta el conteo de bytes actual)

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);

Descompostura

// 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 realidad, 27 bytes

Esto usa el mismo algoritmo que Martin , Adnan , FryAmTheEggman y Dennis han estado usando. Sugerencias de golf bienvenidas. Pruébalo en línea!

`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 bytes (versión 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)}

Nota: El script resuelve los últimos casos de prueba en menos de 3 minutos en mi cuaderno local. Consulte la solución de "rendimiento" a continuación.

Menos guión de prueba de 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"
}

Salida:

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 bytes (versión "Rendimiento")

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)}

Nota: Creo que los requisitos de rendimiento están en conflicto con el principio de GodeGolf. Pero como había una regla Your program should solve any of the test cases below in less than a minute, hice dos cambios para satisfacer la regla:

• -split'(.)'-ne''en cambio el código corto |% t*y;
• una tabla hash para cobrar cadenas.

Cada cambio reduce el tiempo de evaluación a la mitad. No piense que he usado todas las funciones para mejorar el rendimiento. Solo esos fueron suficientes para satisfacer la regla.

Menos guión de prueba de 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"
}

Salida:

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 bytes

k –
Ôn õ f@¥Xk ¬ñ

Intentalo