Números con poderes similares

17

Dado un número entero p> 1 , encuentre el número entero más pequeño q> p tal que la lista de exponentes en la factorización prima de q sea ​​la misma que la de p , sin importar el orden o el valor de los factores primos.

Ejemplos

La factorización prima de p = 20 es 2 2 x 5 1 . El entero más pequeño mayor que p con exponentes idénticos en su factorización prima es q = 28 = 2 2 x 7 1 .

La factorización prima de p = 2500 es 2 2 x 5 4 . El entero más pequeño mayor que p con exponentes idénticos en su factorización prima es q = 2704 = 2 4 x 13 2 .

Reglas

  • Se garantiza que la entrada sea un número entero mayor que 1.
  • Este es el , por lo que gana la respuesta más corta en bytes.

Casos de prueba

Input | Output
------+-------
2     | 3
20    | 28
103   | 107
256   | 6561
768   | 1280
2500  | 2704
4494  | 4510
46552 | 46584
75600 | 105840
Arnauld
fuente
2
Solo como referencia, este es A081761 en el OEIS.
Jonathan Frech

Respuestas:

9

Casco , 10 bytes

§ḟ¤≡ȯÖLgp→

Pruébalo en línea!

Explantacion

§ḟ       →     Find the first number starting from the input + 1 such that...
        p        The prime factorisation
       g         with equal elements grouped together
    ȯÖL          and sorted by length of groups
  ¤≡             has the same shape as the above applied to the input.
H.PWiz
fuente
5

Mathematica, 61 bytes

(f[x_]:=Sort[Last/@FactorInteger@x];s=#;While[f@++s!=f@#];s)&  

Pruébalo en línea!

-4 bytes de @Misha Lavrov

J42161217
fuente
Una forma más concisa de escribir tal Whileciclo es s=#;While[f@++s!=f@#];s.
Misha Lavrov
1
Puede reemplazar f[x_]con f@x_para guardar un byte.
numbermaniac
1
O incluso ir a la ruta de composición-ensalada de definición f=Last/@#&@*FactorInteger/*Sort.
Misha Lavrov
4

Pyth , 15 bytes

fqFmShMrPd8,QTh

Pruébalo aquí! o Verificar todos los casos de prueba.

¿Como funciona esto?

fqFmShMrPd8,QTh   ~ Full program. Q = first input.

f             h   ~ First input where the condition is truthy over [Q+1, Q+2, ...]
           ,QT    ~ The two element list [Q, current value (T)].
   m              ~ Map over ^ with d.
       Pd         ~ The prime factorization of d.
      r  8        ~ Run-Length encode ^.
    hM            ~ Get the first element of each.
 qF               ~ Check if the values are equal.
                  ~ Output implicitly.

Alternativas

Otro 15 byter:

LShMrPb8fqyQyTh

Y un par de alternativas (más largas):

fqFmSlM.gkPd,QTh
LSlM.gkPbfqyQyTh
LS/LPb{PbfqyQyTh
f!-FmlM.gkPd,QTh
Sr. Xcoder
fuente
4

Brachylog , 13 bytes

<.;?{ḋḅlᵐ}ᵐ=∧

Pruébalo en línea!

Ha pasado mucho tiempo desde que publiqué una respuesta ...

Explicación

<.               Input < Output
 .;?             The list [Output, Input]
    {    }ᵐ      Map on [Output, Input]:
     ḋ             Prime decomposition
      ḅ            Group into sublists of consecutive equal elements
       lᵐ          Take the length of each sublist
           =∧    The result of the map must be the same for the Output and the Input
Fatalizar
fuente
4

Python 2 , 176 179 171 170 169 bytes

  • Se agregaron tres bytes a medida que la pregunta cambió de un conjunto de exponentes a una lista de exponentes ; set(f)fue cambiado a sorted(f).
  • Guardado ocho bytes gracias a los ovs ; Golfing el bloque if / else hasta la multiplicación.
  • Guardado un byte; golf (n!=r)a (n>r).
  • Guardado un byte; golf while N>1a while~-N.
N=input();n=-~N
def F(N):
 r,f=0,[]
 while~-N:
	for n in range(2,-~N):
	 if N%n<1:f+=[1]*(n>r);f[-1]+=n==r;r=n;N/=n;break
 return sorted(f)
while F(N)!=F(n):n+=1
print n

Pruébalo en línea!

Jonathan Frech
fuente
3

Haskell , 107 bytes

import Data.List
import Data.Numbers.Primes
p=sort.map(1<$).group.primeFactors
f x=until((==p x).p)(+1)$x+1

Pruébalo en línea! Ejemplo de uso: f 2500rendimientos 2704.

Gracias a nimi por señalar una falla y guardar un montón de bytes.


Sin primeFactorsincorporado (117 bytes)

import Data.List
1%n=[]
x%n|0<-mod x n=n:div x n%n|m<-n+1=x%m
p=sort.map(1<$).group.(%2)
f x=until((==p x).p)(+1)$x+1

Pruébalo en línea!

Laikoni
fuente
2

Python - 141 bytes

def s(n):
 i=1;d={}
 while n-1:
  i+=1
  if n%i<1:d[i]=d.get(i,0)+1;n/=i;i=1
 return d.values()
a=input()
j=a+1
while s(a)!=s(j):j+=1
print j
Maltysen
fuente
Su programa parece generar el valor incorrecto 2500como entrada; 4624en lugar de 2704.
Jonathan Frech
while n-1:puede ser while~-n:.
Jonathan Frech
2

05AB1E , 15 bytes

XµN‚εÓ0K{}ËNI›&

Pruébalo en línea!

Explicación

Xµ                # Loop over N in [0 ...] until 1 match is found
  N‚              # pair N with input
    ε    }        # apply to each
     Ó            # list prime exponents
      0K          # remove zeroes
        {         # sort
          Ë       # check that they are equal
              &   # and
           NI›    # that N is greater than the input
Emigna
fuente