Dado um número inteiro N > 1, produza todos os outros números cujas decomposições primárias tenham os mesmos dígitos que a decomposição primária deN .

Por exemplo, se N = 117, então a saída deve ser [279, 939, 993, 3313, 3331], porque

117 = 3 × 3 × 13

portanto, os dígitos disponíveis são 1, 3, 3e 3e temos

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

Esses são os únicos outros números possíveis, porque outra combinação desses dígitos gera números inteiros não primos, o que não pode ser o resultado da fatoração primária.

Se Né qualquer um 117, 279, 939, 993, 3313ou 3331, então a saída conterá os cinco outros números: são factores primários amigos.

Você não pode usar zeros à esquerda para obter números primos, por exemplo N = 107, pois , seu único amigo é 701( 017não é considerado).

Entradas e Saídas

• Os amigos de entrada e saída devem ser recebidos e retornados na base decimal.

• Nsempre será estritamente maior que 1.

• A saída pode ser formatada com bastante liberdade, desde que contenha apenas os elementos sintáticos de amigos e separadores / lista.

• A ordem da saída não é importante.

• Você pode inserir a entrada STDINcomo argumento de função ou algo semelhante.

• Você pode imprimir a saída STDOUT, retorná-la de uma função ou algo semelhante.

Casos de teste

Seu programa deve resolver qualquer um dos casos de teste abaixo em menos de um 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]

Pontuação

Isso é código-golfe , então a resposta mais curta em bytes vence.

Gelatina , 14 bytes

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

O tempo de execução pode ser reduzido pela metade, em DFvez de V, mas ainda conclui os casos de teste combinados em menos de trinta segundos.

Experimente online! ou verifique todos os casos de teste .

Como 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!

O PowerShell não possui nenhum recurso interno para verificação, fatoração ou permutações de primalidade, portanto, isso é feito manualmente. Eu trabalhei com um monte de truques de otimização para tentar reduzir a complexidade de tempo para algo que vai caber nas restrições de desafio, e eu estou feliz em dizer que eu finalmente conseguiu -

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

Explicação

Há muita coisa acontecendo aqui, então vou tentar explicar.

A primeira linha leva entrada $ne define um function, f. Essa função usa a divisão de teste acumulativo para criar uma lista dos fatores principais. É bastante rápido para entradas pequenas, mas obviamente atola se a entrada é grande. Felizmente, todos os casos de teste são pequenos, portanto isso é suficiente.

A próxima linha recebe os fatores $n, -splité-los em cada dígito ignorando qualquer resultado vazias (isto é necessário devido à forma como PowerShell faz correspondência regex e como ele se move o ponteiro através da entrada e é meio chato para fins de golfe), então sorté os resultados em ordem ascendente. Armazenamos essa matriz de dígitos $xe a usamos como entrada de um |?{...}filtro para extrair apenas aqueles que são primos. Esses dígitos primos são armazenados $ypara uso posterior.

Nós então dividimos $x em dois componentes. O primeiro dígito (ou seja, o menor) é armazenado $a, enquanto o restante é passado $b. Se $xtiver apenas um dígito, $bserá vazio / nulo. Precisamos, então, relançar $acomo uma matriz, para usar o operador de vírgula rapidamente.

Em seguida, precisamos construir todas as permutações possíveis dos dígitos. Isso é necessário, para que nossos testes de divisão posteriormente ignorem vários números e tornem as coisas mais rápidas em geral.

Enquanto houver um elemento $b, separamos o primeiro dígito $ze deixamos o restante $b. Então, precisamos acumular no $aresultado de algumas fatias e cubos de cordas. Tomamos $a+$ycomo concatenação de array e, para cada elemento, construímos uma nova string $c, em seguida passamos por $c's .lengthe inserimos $zem todas as posições, incluindo $z$canexos e anexos$c$z , selectincluindo apenas os -uelementos específicos. Isso é novamente concatenado $ae armazenado novamente em array$a . Sim, isso acabar tendo coisas patetas acontecer, como você pode obter 3333para a entrada117, que na verdade não é uma permutação, mas é muito mais curto do que tentar filtrá-las explicitamente, garante que obtemos todas as permutações e é apenas um pouco mais lento.

Portanto, agora $atem uma matriz de todas as permutações possíveis (e algumas) dos dígitos do fator. Precisamos redefinir $xpara ser nosso limite superior de possíveis resultados |sortinserindo os dígitos em-des ordem pendente e -joinjuntando-os novamente. Obviamente, nenhum valor de saída pode ser maior que esse número.

Montamos nossa matriz auxiliar $l como uma matriz de valores que vimos anteriormente. Em seguida, extraímos todos os valores $a(ou seja, aquelas permutações) que são primos e inserimos um loop que é o maior tempo gasto em todo o programa ...

A cada iteração, passamos 0para o limite superior $x, incrementando o elemento atual $j. Desde que o $ivalor que estamos considerando não seja um múltiplo de um valor anterior (essa é a 0-notin($l|%{$i%$_})seção), é um candidato potencial à saída. Se tomarmos os fatores $i, sorteles, e eles -equal $x, em seguida, adicione o valor para o pipeline. No final do loop, adicionamos nosso elemento atual$j em nossa $lmatriz para uso da próxima vez, pois já consideramos todos esses valores.

Finalmente, aderimos |?{$_-ne$n} para extrair aqueles que não são o elemento de entrada. Eles são todos deixados no pipeline e a produção está implícita.

Exemplos

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=},^}

Experimente online

Explicação

Concatenar dois números sempre dá um resultado maior do que multiplicá-los. Portanto, o maior número que precisamos considerar é o maior número que podemos formar a partir dos dígitos da fatoração primária da entrada, que são apenas todos os dígitos classificados em ordem decrescente. Para os números indicados, esse limite superior é facilmente pequeno o suficiente para que possamos verificar exaustivamente todos os números no intervalo, para saber se é um fator primordial:

_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¹Ê*–

Explicação:

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

Usa a codificação CP-1252 . Experimente online!

Pyth, 17

LSjkPb-fqyTyQSs_y

Conjunto de teste .

Usa a mesma observação do post de Martin .

Expansão:

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 bytes

Editar : Foi esclarecido que um primo como 23 deve retornar [6], em vez de um conjunto de resultados vazio. Economizou 5 bytes removendo uma regra agora inútil que, de propósito, impedia que isso acontecesse.

O último caso de teste é comentado para que esse trecho seja executado com rapidez suficiente, embora também seja concluído em menos de um 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

provavelmente poderia ser mais curto com um algoritmo que não é assim pelo livro.
(mas eu gosto da contagem atual de bytes)

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

demolir

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

Na verdade, 27 bytes

Isso usa o mesmo algoritmo usado por Martin , Adnan , FryAmTheEggman e Dennis . Sugestões de golfe são bem-vindas. Experimente online!

`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 (versão 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: O script resolve os últimos casos de teste em menos de 3 minutos no meu notebook local. Veja a solução "performance" abaixo.

Script de teste com menos golfe:

$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"
}

Saída:

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 (versão "Desempenho")

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: acredito que os requisitos de desempenho estão em conflito com o princípio GodeGolf. Mas como havia uma regra Your program should solve any of the test cases below in less than a minute, fiz duas alterações para satisfazer a regra:

• -split'(.)'-ne''em vez disso, o código curto |% t*y;
• uma hashtable para descontar cordas.

Cada alteração reduz o tempo da avaliação pela metade. Por favor, não pense que eu usei todos os recursos para melhorar o desempenho. Apenas esses foram suficientes para satisfazer a regra.

Script de teste com menos golfe:

$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"
}

Saída:

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

Japonês, 18 bytes

k –
Ôn õ f@¥Xk ¬ñ

Tente