Suba um passo até o ponto mais alto

24

O título do vídeo mais recente de Numberphile , 13532385396179 , é um ponto fixo da seguinte função f nos números inteiros positivos:

Seja n um número inteiro positivo. Escreva a fatoração primária da maneira usual, por exemplo, 60 = 2 2 · 3 · 5, na qual os números primos são escritos em ordem crescente, e os expoentes de 1 são omitidos. Em seguida, traga expoentes para a linha e omita todos os sinais de multiplicação, obtendo um número f (n). [...] por exemplo, f (60) = f (2 2 · 3 · 5) = 2235.

(A definição acima é retirada do Problema 5 de Cinco Problemas de $ 1.000 - John H. Conway )

Observe que f (13532385396179) = f (13 · 53 2 · 3853 · 96179) = 13532385396179.

Tarefa

Tome um número inteiro composto positivo ncomo entrada e saída f(n).

Outro exemplo

48 = 2 4 · 3, então f (48) = 243.

Casos de teste

Mais casos de teste estão disponíveis aqui .

   4 -> 22
   6 -> 23
   8 -> 23
  48 -> 243
  52 -> 2213
  60 -> 2235
 999 -> 3337
9999 -> 3211101
Freira Furada
fonte
11
+1 Ainda estou surpreso que alguém tenha encontrado 13532385396179 como uma refutação da conjectura. Eu acho que o prêmio de US $ 1000 valeria a pena pagar pela eletricidade usada! :)
Wossname
7
Sem seguir o link, não ficou claro que a conjectura é que aplicações repetidas de f (n) sempre atingirão um primo (e, é claro, f (p) = p se p for primo). 13532385396179 nega a conjectura porque é composta e uma impressão fixa.
Chris H

Respostas:

16

Python, 166 162 159 bytes

Vocês são muito melhores. Isto é o que eu usei! (o algoritmo que resolveu chama isso)

from primefac import*
def c(n):
 x=factorint(n)
 a=''
 for i in range(len(x)):
  l=min(x.keys())
  a+=str(l)
  if x[l]>1:a+=str(x[l])
  x.pop(l)
 return int(a)
jchd
fonte
2
Por que alguém votou contra um novato em vez de ajudá-lo a melhorar sua resposta como o @LeakyNun? :(
Salsicha
3
Desculpe, isso é realmente o que eu usei (encontrei o número). Eu apenas pensei que o código ruim seria engraçado. Você pode derrubar.
jchd
9
Bem-vindo ao site. É muito bom ter você compartilhando conosco sua solução. (para pessoas que não sabem, Jim Davis é quem resolveu esse problema em primeiro lugar). No entanto, as respostas aos desafios precisam seguir algumas regras. Se você seguir as sugestões de @LeakyNun, a resposta será válida. (talvez ter um olhar para as outras respostas para ver como eles normalmente se parecem)
Dada
4
Oh meu Deus, eu não esperava que o próprio Jim Davis para aparecer neste local, e para responder ao meu desafio ... Eu me sinto tão honrada agora ...
Leaky Nun
2
ehh, não é um troll a propósito. Meu endereço de e-mail está em gladhoboexpress.blogspot.ca/2014/10/climb-to-prime.html ... Eu deixei a postagem, ninguém o enche de e-mail sobre matemática.
jchd
9

Braquilog , 8 bytes

ḋoọc;1xc

Experimente online!

Explicação

Example input: 60

ḋ          Prime decomposition: [5,3,2,2]
 o         Order: [2,2,3,5]
  ọ        Occurences: [[2,2],[3,1],[5,1]]
   c       Concatenate: [2,2,3,1,5,1]
    ;1x    Execute 1s: [2,2,3,5]
       c   Concatenate: 2235

Você pode usar ℕ₂ˢ( selecione todos os números inteiros maiores ou iguais a 2 ) em vez de ;1x, o que provavelmente é mais legível e mais no espírito do Brachylog.

Fatalizar
fonte
9

Gelatina , 6 bytes

ÆFFḟ1V

Experimente online!

Explicação

ÆF      Get prime factorisation of input as prime-exponent pairs.
  F     Flatten.
   ḟ1   Remove 1s.
     V  Effectively flattens the list into a single integer.
Martin Ender
fonte
V= "concatenar com uma única string e avaliar como Jelly"
Erik, o Outgolfer
@EriktheOutgolfer Sim, portanto, "efetivamente".
Martin Ender
@MartinEnder Alguma razão específica para você não usar (Converter de decimal para inteiro)?
scatter
@ Christian Porque a lista pode conter números inteiros com vários dígitos.
Martin Ender
@MartinEnder Ah, inteligente. Eu usei FḌno passado - essa é uma boa dica!
scatter
5

Mathematica, 43 36 Bytes

Row@Flatten@FactorInteger@#/. 1->""&

Experimente online!

J42161217
fonte
2
DeleteCasesé longo, você pode usar /.1->""ou /.1->##&[](forma alternativa de/.1->Nothing
user202729 9/17/17
3
@ user202729 Todos esses precisam de um espaço na frente do 1para impedir que ele analise como ... / (0.1).
Martin Ender
Você está certo! corrigido
J42161217 9/0917
4

CJam , 8 bytes

limF:~1-

Experimente online!

Explicação

li  e# Read input and convert to integer.
mF  e# Get prime factorisation as prime-exponent pairs.
:~  e# Flatten.
1-  e# Remove 1s.
    e# Implicitly print a flattened representation of the list.
Martin Ender
fonte
Eu costumava e_achatar, já que é para isso que existe, mas isso não altera a pontuação.
Peter Taylor
11
@ PeterTaylor Hm, sim, eu nunca consigo decidir qual usar, mas tendem a e_usar apenas o achatamento profundo e a usar :~sempre que é apenas um nível.
Martin Ender
4

05AB1E , 10 bytes

Òγʒ¬?gDië?

Experimente online!

Ò          # Push list of prime factors with duplicates
 γ         # Break into chunks of consecutive elements
  ʒ        # For each
   ¬?      #   Print the first element
     gD    #   Push the length of this chunk twice
       ië  #   If not 1
         ? #     Print the length
Riley
fonte
3

05AB1E , 12 11 bytes

Òγvy¬sgD≠×J

Experimente online!

Explicação

Ò            # calculate prime factors with duplicates
 γ           # group consecutive equal elements
  vy         # for each group
    ¬        # get the head without popping
     sg      # push the length of the group
       D≠×   # repeat the length (length != 1) times
          J  # join
Emigna
fonte
Falha em 48.
Freira vazada
2

Pitão, 12 bytes

smjk_>hddr8P

Tente!

alternativa, 12 bytes

smjk<_AdGr8P

Tente isso!

explicação

smjk_>hddr8P
           PQ  # prime factorization (already in correct order) of the implicit input: [3, 3, 11, 101]
         r8    # length encode: [[2, 3], [1, 11], [1, 101]]
 m             # map over the length encoded list (lambda variable: d)
     >hdd      # take the d[0] last elements of d (so only the last for d[0]==1 and all else)
    _          # reverse that list
  jk           # join into a string
s              # conatenate the list of strings
KarlKastor
fonte
2

Python 2 , 99 bytes

n=input()
r=''
p=2
while~-n:
 e=0
 while n%p<1:e+=1;n/=p
 r+=str(p)*(e>0)+str(e)*(e>1);p+=1
print r

Experimente online!

Se as entradas estiverem restritas a ficar abaixo 2147483659, ambas str(...)poderão ser substituídas `...`salvando 6 bytes (este programa será muito lento para os números afetados de qualquer maneira!).

Jonathan Allan
fonte
2

Ohm , 11 bytes

o:_]D2<?O;J

Experimente online!

Explicação

o:_]D2<?O;J
o           # Push prime factors with powers from input (Format [[prime,power],...]
 :          # For each...
  _          # Push current element
   ]         # flatten
    D        # Duplicate power
     2<? ;   # Is the power smaller than 2?
        O     # Delete top of stacks
          J  # Join
Datboi
fonte
1

Japonês , 19 bytes

k ó¥ ®¯1 pZlÃc fÉ q

Teste online!

Explicação

 k ó¥  ®   ¯  1 pZlà c fÉ  q
Uk ó== mZ{Zs0,1 pZl} c f-1 q  // Ungolfed
                              // Implicit: U = input number
Uk                            // Break U into its prime factors.
   ó==                        // Group into runs of equal items.
       mZ{         }          // Map each item Z in this to
          Zs0,1               //   Z.slice(0, 1) (the array of the first item),
                pZl           //   with Z.length added at the end.
                              // This returns an array of prime-exponent pairs (Jelly's ÆF).
                     c        // Flatten.
                       f-1    // Filter to the items X where X - 1 is truthy (removes '1's).
                           q  // Join the resulting array into a single string.
                              // Implicit: output result of last expression
ETHproductions
fonte
1

PHP , 88 bytes

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i+!++$r[$i];foreach($r as$k=>$v)echo$k,$v<2?"":$v;

Experimente online!

Jörg Hülsermann
fonte
0

C #, 206 100 bytes

n=>{var r="";for(int d=1,c;++d<=n;){c=0;while(n%d<1){c++;n/=d;}r+=c>0?d+(c>1?c+"":""):"";}return r;}

Versão completa / formatada:

using System;

class P
{
    static void Main()
    {
        Func<int, string> func = n =>
        {
            var r = "";
            for (int d = 1, c; ++d <= n;)
            {
                c = 0;
                while (n % d < 1)
                {
                    c++;
                    n /= d;
                }

                r += c > 0 ? d + (c > 1 ? c + "" : "") : "";
            }

            return r;
        };

        Console.WriteLine(func(4));
        Console.WriteLine(func(6));
        Console.WriteLine(func(8));
        Console.WriteLine(func(48));
        Console.WriteLine(func(52));
        Console.WriteLine(func(60));
        Console.WriteLine(func(999));
        Console.WriteLine(func(9999));

        Console.ReadLine();
    }
}
TheLethalCoder
fonte
0

Javascript - 91 bytes

(x,r='',i=1,n)=>{while(x>i++){for(n=0;x%i<1;n++)x/=i;r+=(n>0?i+'':'')+(n>1?n:'')}return r}

Explicação

(x,r='',i=1,n)=>(          // input x is the number to process, r, i, n are default values only
    while(x>i++){          // iterate over i until x
        for(n=0;x%i<1;n++) // iterate over n until i is not a factor of x
            x/=i;          // factor i out of x
        r+=(n>0?i+'':'')   // append i to r if n > 0
            +(n>1?n:'')    // append n to r if n > 1
                           // i+'' prevents adding i and n before appending to r
    }
    return r               // return r by comma-operator and arrow function syntax
)
asgallant
fonte
0

Java 8, 103 caracteres

Solução bastante simples.

n->{String r="";int d=2,c;while(n>1){c=0;while(n%d<1){c++;n/=d;}if(c>0)r+=d;if(c>1)r+=c;d++;}return r;}

Ungolfed:

private static Function<Integer, String> f = n->{
    String result = "";
    int divisor = 2, count;
    while (n>1) {
        count = 0;
        while (n % divisor < 1) {
            count++;
            n /= divisor;
        }
        if (count > 0) result += divisor;
        if (count > 1) result += count;
        divisor++;
    }
    return result;
};
Computronium
fonte
91 bytes
ceilingcat
0

Oitava , 69 bytes

@(a)printf('%d',(f=[[~,c]=hist(b=factor(a),d=unique(b));d](:))(f~=1))

Experimente online!

Acabou sendo bastante longo, mas isso gerará a saída desejada.

Basicamente, usamos a função histograma para contar o número de ocorrências dos valores únicos na fatoração primária do valor de entrada.

  • O resultado da factor()função fornece os fatores primos em ordem crescente
  • então encontramos unique()valores nessa matriz
  • hist() retorna o número de ocorrências

Depois de termos as duas matrizes (uma para fatores únicos, uma para contagens), concatenamos as matrizes verticalmente (uma em cima da outra) e depois achatamos. Isso intercala os fatores com contagens.

Finalmente, exibimos o resultado como uma string, garantindo pular qualquer 1 na matriz final. A única vez que 1 pode aparecer é se a contagem for 1, porque 1 nunca será um fator primordial. Essa eliminação é feita antes da conversão para uma string, para que não afete coisas como o número 10.

Tom Carpenter
fonte
0

Ruby , 45 + 7 bytes

Requer a bandeira -rprime.

->n{(n.prime_division.flatten-[1]).join.to_i}

Experimente online!

canhascodez
fonte
0

Pitão - 16 bytes

V{PQpNK/PQNItKpK

Tente

Outra solução:

sm`d-.nm(d/PQd){PQ1
Maria
fonte
11
Pode-se substituir FN por V.
Leaky Nun
11
Além disso, r8 (codificação de comprimento de execução) parece ser útil.
Leaky Nun
0

R , 72 bytes

x=rle(pracma::factors(scan()));x$l[x$l<2]='';paste0(x$v,x$l,collapse='')

Requer o pracmapacote, que não está instalado no TIO.

Giuseppe
fonte